O Insertion Sort (ordenação por inserção) é um dos algoritmos de ordenação quadráticos mais populares, ao lado do Selection Sort e do Bubble Sort.
Assim como seus "irmãos", o tempo de execução do Insertion Sort no pior caso e no caso médio é $O(n^2)$. Entretanto, o seu tempo no melhor caso é linear, que é um dos destaques do algoritmo.
Nesta postagem, analisaremos o Insertion Sort apresentado no livro "Algoritmos: teoria e prática". O algoritmo também será disponibilizado nas linguagens Java, C e JavaScript.
Índice
Funcionamento do Insertion Sort
O Insertion Sort inicia a ordenação dividindo o vetor em duas partições: uma ordenada à esquerda e outra não ordenada à direita. Inicialmente, a partição esquerda só terá um elemento (é o caso trivial da ordenação).
A inserção dos elementos na partição ordenada é realizada em duas etapas. Na primeira etapa, procuramos a posição de inserção. Na segunda etapa, deslocamos os elementos da esquerda para a direita para que a posição de inserção fique livre para que o elemento seja inserido.
Faremos essas duas etapas simultaneamente. O pseudocódigo é [1]
//algoritmo adaptado o livro "Algoritmos: teoria e prática" (Cormen et al) 01. insertionSort(A[0...n-1]) 02. | para i ← 1 até n-1 03. | | elemento ← A[i] 04. | | j ← i - 1 05. | | enquanto(j ≥ 0 E A[j] > elemento) 06. | | | A[j + 1] ← A[j] //deslocamento para a direita 07. | | | j ← j - 1 08. | | fim_enquanto 09. | | A[j + 1] = elemento //insere o elemento na parte ordenada 10. | fim_para 11. fim_insertionSort
O algoritmo é bem simples. Se você preferir, pode substituir o laço enquanto (while) por para (for)
//algoritmo adaptado o livro "Algoritmos: teoria e prática" (Cormen et al) 01. insertionSort(A[0...n-1]) 02. | para i ← 1 até n - 1 03. | | elemento ← A[i] 04. | | para(j ← i - 1; j ≥ 0 E A[j] > elemento; j ← j - 1) 05. | | | A[j + 1] ← A[j] //deslocamento para a direita 06. | | fim_para 07. | | A[j + 1] = elemento //insere o elemento na parte ordenada 08. | fim_para 09. fim_insertionSort
Os dois algoritmos são equivalentes.
Exemplo
Para exemplificar o uso do algoritmo, ordenaremos o seguinte vetor
Inicialmente, temos i = 1, j = 0 e elemento = 1. Queremos inserir elemento na parte ordenado à esquerda. Como 3 > 1, então deslocamos o 3 para direita e decrementamos j: j = 0 - 1 = -1
Como atingimos o início do vetor, então inserimos 1 em j + 1 = 0
Agora, i = 2, j = 1 e elemento = 9. Como 3 < 9, então o elemento já está na posição correta (na verdade, o algoritmo insere o elemento na própria posição onde ele está).
Na terceira iteração, i = 3, j = 2 e elemento = 5. Como 9 > 5, então deslocamos o 9 para direita e decrementamos j: j = 2 - 1 = 1
Como 3 < 5, então inserimos 5 em j + 1 = 2
Na quarta iteração, i = 4, j = 3 e elemento = 2. Como 9 > 2, então deslocamos o 9 para direita e decrementamos j: j = 3 - 1 = 2
Como 5 > 2, então deslocamos o 5 para direita e decrementamos j: j = 2 - 1 = 1
Como 3 > 2, então deslocamos o 3 para direita e decrementamos j: j = 1 - 1 = 0
Como 1 < 2, então inserimos 2 em j + 1 = 1
Na quinta e última iteração, i = 5, j = 4 e elemento = 8. Como 9 > 8, então deslocamos o 9 para direita e decrementamos j: j = 4 - 1 = 3
Como 5 < 8, então inserimos 8 em j + 1 = 4
Com isso, finalizamos a ordenação.
Complexidade assintótica
O pior caso do Insertion Sort ocorre quando os elementos do vetor estão em ordem decrescente, pois a condição A[j] > elemento sempre será verdadeira. Logo, o laço interno realizará a quantidade máxima de iterações. Nesse caso, o Insertion Sort terá complexidade no tempo de $O(n^2)$.
O melhor caso ocorre quando o vetor está ordenado, pois, ao contrário do pior caso, a condição A[j] > elemento sempre será falsa. Logo, o código do laço interno nunca será executado. Assim, teremos apenas as n - 1 iterações do laço externo, portanto a complexidade no tempo é $O(n)$.
O caso médio do Insertion Sort é $O(n^2)$. Lembrando que o caso médio é uma média entre todas as entradas possíveis. Isso significa que, em geral, ele terá tempo quadrático, estatisticamente falando.
Códigos
Os códigos em Java, C e em JavaScript do Insertion Sort podem ser obtidos nos links a seguir
Considerações finais
O gráfico a seguir foi retirado de um antigo trabalho meu de complexidade de algoritmos da época em que eu fazia faculdade. O gráfico faz um comparativo do tempo de execução do Bubble Sort, Selection Sort e Insertion Sort.
O desempenho do Insertion Sort o torna uma boa opção para realizar a ordenação de vetores pequenos. Entretanto, é sempre bom lembrar que a biblioteca padrão da maioria das linguagens de programação já possui métodos que ordenam vetores. É extremamente recomendado que você utilize esses métodos, pois os algoritmos implementados são otimizados para cada linguagem.
Referências
- [1] CORMEN, T. H. et al. Algoritmos: teoria e prática. 3 ed. Rio de Janeiro: Elsevier, 2012.
Nenhum comentário:
Postar um comentário