Algoritmo de Ordenação por Inserção – Concurso BB (TI)

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:

• Entendendo o algoritmo de ordenação por inserção: etapas
• Pseudocódigo do algoritmo de ordenação por inserção
• Exemplo (passo a passo)
• Análise de complexidade do algoritmo de ordenação por inserção
• Resumo
• Vamos praticar!

Entendendo o algoritmo de ordenação por inserção: etapas

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:

1. Primeiramente, defina a primeira posição da lista como ordenada.
   
2. Em seguida, pegue o primeiro elemento da lista não ordenada e coloque-o na posição correta na lista ordenada.
   
3. Por fim, repita o passo 2 até que todos os elementos da lista não ordenada sejam inseridos na lista ordenada.

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.

Pseudocódigo do Algoritmo de Ordenação por Inserção

Abaixo está o pseudocódigo do algoritmo de ordenação por inserção e, logo após, a explicação de cada linha:

Pseudocódigo ordenação por inserção:

Explicação do pseudocódigo:

• Linha 1: o algoritmo inicia recebendo o vetor não ordenado com n elementos, considerando o primeiro elemento na posição 0 (zero).
  
• Linha 2: o algoritmo realiza um loop que percorrerá a lista de elementos. A variável ‘i’ é utilizada como contador e começará com o valor ‘1’, indicando que o primeiro elemento, o da posição zero, já está ordenado. O loop seguirá até que a variável ‘i’ atinja o valor ‘n – 1’, indicando que todos os elementos da lista foram comparados.
  
• Linha 3: esta linha atribui o valor do elemento atual (vetor[i]) à variável ‘atual’.
  
• Linha 4: esta linha inicializa a variável ‘j’ com o valor ‘i – 1’, o que indica que o último elemento à esquerda já está ordenado.
  
• Linha 5: aqui é definido o início de um loop que percorrerá os elementos já ordenados à esquerda do elemento atual. O loop continuará enquanto ‘j >= 0’ (ou seja, enquanto ainda houver elementos à esquerda para comparar) e ‘vetor[j] > atual’ (ou seja, enquanto o elemento atual for menor que o elemento comparado).
  
• Linha 6: desloca o elemento comparado (‘vetor[j]’) uma posição à direita (‘vetor[j + 1]’).
  
• Linha 7: decrementa o valor de ‘j’ em ‘1’, o que indica que o próximo elemento à esquerda será comparado na próxima iteração deste loop.
  
• Linha 8: finaliza o loop que compara os elementos já ordenados à esquerda do elemento atual.
  
• Linha 9: insere o elemento ‘atual’ na posição correta, deslocando os elementos maiores à direita.
  
• Linhas 10 e 11: depois que todos os elementos são percorridos e ordenados, o vetor estará ordenado.
  

Exemplo de ordenação com o algoritmo de ordenação por inserção: passo a passo

Para exemplificar, iremos considerar o seguinte vetor: [8, 4, 2, 5, 3]. Inicialmente, consideramos o primeiro elemento já ordenado.

Primeira iteração

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].

Segunda iteração

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].

Terceira iteração

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].

Quarta iteração

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:

Análise de Complexidade do Algoritmo de Ordenação por Inserçã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:

• Primeira iteração: 1 comparação e 2 movimentações.
• Segunda iteração: 2 comparações e 3 movimentações.
• Terceira iteração: 2 comparações e 2 movimentações.
• Quarta iteração: 4 comparações e 4 movimentações.

Portanto, ao final, o algoritmo realizou 9 comparações e 11 movimentações.

Resumo com os principais pontos do algoritmo de ordenação por inserção

• O algoritmo de ordenação por inserção funciona selecionando o primeiro elemento da parte não ordenada de uma lista e colocando-o na posição correta dentro da parte ordenada. Isso é repetido para cada posição subsequente até a lista inteira estar ordenada.
  
• É um algoritmo simples, mas não muito eficiente. No entanto, para listas já ordenadas é rápido, diferente do que ocorre na ordenação por seleção.
  
• A complexidade do algoritmo é quadrática, ou seja, n², para o médio e pior casos, e linear para o melhor caso.
  
• O algoritmo de ordenação por inserção é estável, ou seja, preserva a ordem original dos elementos iguais.

Vamos Praticar!

Questão 1:

Questão 2:

Questão 3:

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.

Se preparando para o concurso do Banco do Brasil? Então, confira nossos cursos:

Pacote para o cargo Agente de Tecnologia

Pacotaço (Conteúdo + Passo estratégico) para o cargo Agente de Tecnologia

Quer saber tudo sobre concursos previstos?
Confira nossos artigos!

Concursos abertos

Concursos 2023