Olá pessoal! Tudo bem? Para você que está se preparando para o concurso do Banco do Brasil, cargo Agente de Tecnologia, neste artigo estudaremos o algoritmo ordenação por inserção ou insertion sort.
Antes de mais nada, a ordenação de elementos consiste basicamente em colocá-los em ordem crescente ou decrescente. Alguns exemplos de ordenação são: ordenar alunos pelas suas notas; ordenar uma lista telefônica pelo nome das pessoas; ordenar pessoas por idade; ordenar clientes de acordo com a renda; entre outras.
Além disso, para ordenação dos elementos, utilizam-se diversos algoritmos de ordenação, dentre os quais, três deles constam no edital do concurso do Banco do Brasil: método da bolha, ordenação por seleção e ordenação por inserção.
Neste artigo, abordaremos os seguintes tópicos sobre o algoritmo de ordenação por inserção:
Antes de tudo, o algoritmo de ordenação por inserção, é um algoritmo estável que constrói aos poucos a lista ordenada. Ele inicia tomando o elemento da primeira posição da lista como ordenado e, em seguida, compara cada um dos elementos subsequentes com os elementos já ordenados, colocando-os em sua posição correta entre os ordenados.
Em suma, assim como o algoritmo de ordenação por seleção, o insertion sort divide a lista em duas partes, uma ordenada e a outra desordenada. Assim, ele vai pegando sempre o primeiro elemento da lista desordenada e colocando em sua posição correta na lista ordenada. Esse processo ocorre até que a lista esteja completamente ordenada.
Sendo assim, as etapas do algoritmo de ordenação por inserção são:
O que o algoritmo de ordenação por inserção faz, é percorrer cada elemento de uma lista e ir comparando-os com os elementos já ordenados à esquerda. Dessa forma, para cada iteração, ele pega o próximo elemento, compara com os elementos da esquerda até encontrar a posição correta, insere-o nesta posição e desloca os elementos maiores para a direita. Ao final, ou seja, quando o algoritmo percorrer toda a lista, esta estará ordenada.
Abaixo está o pseudocódigo do algoritmo de ordenação por inserção e, logo após, a explicação de cada linha:
Para exemplificar, iremos considerar o seguinte vetor: [8, 4, 2, 5, 3]. Inicialmente, consideramos o primeiro elemento já ordenado.
A imagem abaixo apresenta a primeira iteração do algoritmo:
Perceba que o loop do algoritmo se inicia da posição 1, ou seja, o primeiro elemento, o 8, já está considerado como ordenado. Então, o elemento atual inicia com valor 4, que está na segunda posição.
A ideia do algoritmo é comparar o elemento atual com todos os elementos que estão à sua esquerda, começando do mais próximo, para, assim, inserir ele na posição correta. Mas, inicialmente, como só tem um elemento à esquerda, valor 8, do elemento atual, o algoritmo irá fazer a comparação entre eles, e como o valor 8 é maior que 4, então o valor 8 adianta uma posição no vetor, e a primeira posição do vetor recebe o valor atual (4). Ao final da primeira iteração, temos a lista ordenada = [4, 8], e a lista desordenada = [2, 5, 3].
Em seguida, temos a segunda iteração:
Nesta iteração, o elemento atual está na posição 2, ou seja, é o elemento de valor 2. Olhando em uma visão global, já sabemos que devemos inserir o elemento atual antes de elemento de valor 4. No entanto, o algoritmo precisa percorrer a lista à esquerda do elemento atual e realizar as devidas comparações para poder inseri-lo na posição correta.
Sendo assim, inicialmente, o elemento imediatamente anterior ao elemento atual é comparado com este, e caso aquele seja maior, então ele se move uma posição para a direita, ou seja, como o 8 é maior que o 2 (elemento atual), então o 8, que está na posição 1, vai para a posição 2.
Após isso, comparamos com o elemento anterior, que é o 4, e como este também é maior que o 2, também se move uma posição à direita, ou seja, vai da posição 0 para a posição 1. Por fim, como não existem mais elementos a serem comparados, o elemento atual ficará na posição 0. Então, temos a parte ordenada com os elementos [2, 4, 8] e a não ordenada com os elementos [5, 3].
Em seguida, na próxima iteração temos:
Observe que a parte ordenada é [2, 4, 8], então o elemento atual, que é o 5, deverá ficar entre o 4 e o 8. Para isso, inicialmente é feita uma comparação do elemento atual com o elemento imediatamente anterior, que é o último da lista ordenada, ou seja, o algoritmo verifica se 8 é maior que 5, como o resultado é verdadeiro, então o elemento 8 é movido uma posição à direita, passando a ficar na posição 3.
Em seguida, o elemento anterior, que é o 4, é comparado com o elemento atual, que é o 5, como 4 não é maior que 5, então o elemento atual ficará na posição 2. Ao final da terceira iteração, temos a parte ordenada com os elementos [2, 4, 5, 8] e a parte não ordenada com o elemento [3].
Finalmente, temos a última iteração:
Nesta iteração, o elemento atual é o 3, e ele deverá ficar entre o elemento 2 e o 4. Para isso, o algoritmo precisará realizar comparações com todos os elementos, movendo os elementos maiores uma posição à direita. Assim, os elementos 8, 5, e 4 serão movidos uma posição para a direita no vetor. No final, como o elemento 2 é menor que o atual (3), o elemento 2 ficará em sua posição e o 3 na posição 1.
Finalmente, ao fim da quarta iteração, temos a lista ordenada. Vejamos, então, como a fica a lista ao final de cada iteração:
Este tópico aborda um dos pontos importantes no estudo e desenvolvimento de algoritmos, que é a análise de complexidade dos algoritmos. O que a análise de complexidade faz é basicamente calcular o desempenho de um algoritmo. Isso é feito obtendo o número de operações realizadas (como comparações, atribuições, etc.) à medida que o tamanho da entrada aumenta.
Com base nisso, calcula-se o tempo de execução. A análise de complexidade é importante pois permite que entendamos como o tamanho da entrada de um algoritmo afeta seu desempenho, possibilitando a escolha de algoritmos mais adequados de acordo com o problema.
De cara, podemos observar que no algoritmo de ordenação por inserção temos um laço de repetição dentro de outro, ou seja, de grosso modo, a lista é percorrida N * N, ou N², sendo N o tamanho da lista. Dessa forma, a complexidade do algoritmo de ordenação por seleção é quadrática, ou N², tanto no médio, quanto no pior caso.
No entanto, no melhor caso, o algoritmo tem complexidade linear, ou seja, N. Isso ocorre porque, se o algoritmo receber uma lista já ordenada, ele só fará N – 1 comparações, não realizando nenhuma movimentação.
Além disso, é importante saber o exato número de comparações e de movimentações realizadas, e para isso, precisamos fazer um passo a passo. Considerando o exemplo anterior, temos, então, a cada iteração as seguintes quantidades de comparações e movimentações:
Portanto, ao final, o algoritmo realizou 9 comparações e 11 movimentações.
Ano: 2011 Banca: CESGRANRIO Órgão: FINEP Prova: CESGRANRIO – 2011 – FINEP – Analista – Desenvolvimento de Sistemas
Considerando-se a análise assintótica (Notação Big O), qual é a complexidade do caso médio do algoritmo de ordenação chamado de Ordenação por Inserção?
a) O(n²)
b) O(1)
c) O(n)
d) O(n log n)
e) O(log n)
Gabarito: letra A.
A complexidade do algoritmo de ordenação por inserção é:
Portanto, a letra A é a alternativa correta.
Ano: 2021 Banca: CESGRANRIO Órgão: Banco do Brasil Prova: CESGRANRIO – 2021 – Banco do Brasil – Agente de Tecnologia
Dentre os problemas identificados pela gerência de um banco comercial, está a localização das contas dos seus titulares nas listagens e nos relatórios impressos em diferentes situações. Um especialista de TI sugeriu ordenar as contas por meio dos CPF dos seus n titulares antes das impressões.
Dentre alguns algoritmos pré-selecionados para essa ordenação, o especialista escolheu o algoritmo de ordenação por inserção, no qual o consumo de tempo é, no melhor caso, proporcional a
a) n log n
b) log n
c) n²
d) n
e) 1
Questão bem semelhante à anterior. A complexidade do algoritmo de ordenação por inserção é:
Portanto, a letra D é a alternativa correta.
Ano: 2021 Banca: CESGRANRIO Órgão: Banco do Brasil Prova: CESGRANRIO – 2021 – Banco do Brasil – Agente de Tecnologia
Um professor preparou uma série de experimentos para avaliar, juntamente com seus alunos, três algoritmos de ordenação: o da bolha, o de ordenação por inserção e o de ordenação por seleção. Para tal, ele escreveu três métodos Java, um para cada algoritmo. Todos eles recebem como único parâmetro um array de inteiros (int vet[ ] = {81,15,4,20,7,47,14,20,4}), que será ordenado em ordem crescente. Para acompanhar a evolução desse array sendo ordenado, cada um dos três métodos exibe a configuração dos elementos do array ao término de cada iteração do comando de repetição mais externo. Vale lembrar que esses três algoritmos de ordenação são compostos por dois comandos de repetição aninhados (dois comandos for ou dois comandos while).
Terminada a codificação, o professor executou os métodos relativos aos três algoritmos de ordenação e projetou no quadro as configurações do array relativas às três primeiras iterações de cada um dos algoritmos de ordenação, conforme mostrado a seguir.
As configurações 1, 2 e 3, exibidas acima, correspondem, respectivamente, aos algoritmos
a) da bolha, de seleção e de inserção
b) da bolha, de inserção e de seleção
c) de seleção, de inserção e da bolha
d) de seleção, da bolha e de inserção
e) de inserção, de seleção e da bolha
Para resolver rapidamente esta questão, temos as seguintes dicas:
Então, por estas dicas, já sabemos que o primeiro algoritmo é de seleção e o último é o da bolha. Portanto, a alternativa correta é a letra C.
Abaixo segue uma imagem com as trocas e movimentações realizadas em cada algoritmo, considerando o vetor informado na questão:
Na ordenação por seleção, o algoritmo vai selecionando os menores e colocando nas primeiras posições.
Na ordenação por inserção, o algoritmo vai selecionando o primeiro elemento da parte não ordenada e colocando-o na posição correta na entre os elementos da esquerda, que estão ordenados.
Por último, na ordenação por bolha, os elementos adjacentes (lado a lado) são comparados levando os maiores para o final.
Portanto, a resposta certa é a letra C: seleção, inserção e bolha, nesta ordem.
Bom pessoal, enfim, finalizamos por aqui este artigo, espero que tenham gostado e que seja útil para sua aprovação. Bons estudos e até a próxima.
Pacote para o cargo Agente de Tecnologia
Pacotaço (Conteúdo + Passo estratégico) para o cargo Agente de Tecnologia