Insertion Sort

• O quê é o Insertion Sort?
• Quais são as características do Insertion Sort?
• Qual é o algoritmo de Insertion Sort?
• Qual é o desempenho do Insertion Sort?
  • Pior Caso
  • Melhor Caso
• Como implementar o Insertion Sort?

O quê é o Insertion Sort?

O Insertion Sort (Ordenação por Inserção) é um algoritmo de ordenação que funciona de forma similar ao modo como algumas pessoas ordenam cartas de um baralho, quando estão jogando. Ao adicionar uma nova carta a uma mão de cartas ordenadas, o jogador compara a nova carta com todas as demais cartas em sua mão, para determinar o ponto de inserção adequado.

Quais são as características do Insertion Sort?

• O Insertion Sort é um algoritmo iterativo.
• O Insertion Sort é um algoritmo de ordenação por comparação.
• O Insertion Sort é um algoritmo de ordenação estável.
• O desempenho do algoritmo Insertion Sort é muito sensível aos dados de entrada.
• O Insertion Sort necessita de uma estrutura de dados auxiliar para funcionar.

Qual é o algoritmo de Insertion Sort?

1. Particione o arranjo de entrada em dois:
   • Um sub-arranjo A que inicialmente contém apenas o primeiro elemento do arranjo original.
   • Um sub-arranjo B que inicialmente contém todos os demais elementos.
2. Considere o primeiro elemento do sub-arranjo B. Denote este elemento x.
3. Procure no sub-arranjo A o ponto onde x deve ser inserido, da direita para a esquerda.
4. Desloque uma posição para a direita, todos os elementos no sub-arranjo A que estão à direita do ponto de inserção.
5. Insira o elemento x na posição de inserção encontrada no sub-arranjo A.
6. Se o sub-arranjo B não estiver vazio, volte ao Passo 2.
7. Retorne o sub-arranjo A, que contém os elementos da arranjo original ordenados.

Qual é o desempenho do Insertion Sort?

Pior Caso

O pior caso para o algoritmo Insertion Sort ocorre quando a lista de elementos está ordenada de forma inversa. Nessa situação, o algoritmo te um custo quadrático de comparações e de trocas, em função do número de elementos n a serem ordenados:

• O(n²) comparações
• O(n²) trocas

Melhor Caso

O melhor caso para o algoritmo Insertion Sort ocorre quando a lista de elementos já está ordenada. Nessa situação, o algoritmo tem um custo linear de comparações e um custo constante de trocas, em função do número de elementos n a serem ordenados:

• O(n) comparações
• O(1) trocas

Como implementar o Insertion Sort?

Veja o código completo no GitHub.