Insertion Sort

Por
| 

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.

Algoritmo de ordenação por inserção Insertion 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.

Ir para o índice

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.

Ir para o índice

Códigos

Os códigos em Java, C e em JavaScript do Insertion Sort podem ser obtidos nos links a seguir

Ir para o índice

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.

Gráfico de comparativo de desempenho entre Bubble Sort, Selection Sort e Insertion Sort.
O gráfico compara o tempo de execução do Bubble Sort, Selection Sort e Insertion Sort para ordenar vetores aleatorizados. Os dados são experimentais. Em cada teste, os algoritmos ordenaram os mesmos vetores (ampliar).

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.

Ir para o índice

Referências

Siga o blog

Redes sociais: Facebook, Twitter, Google+, YouTube, Pinterest, Instagram

Receba notificações de novas postagens e novidades do blog por e-mail.

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário