5.9. A Ordenação Por Inserção¶

A ordenação por inserção, embora seja \(O(n^{2})\), funciona de uma forma ligeiramente diferente. Ela sempre mantém uma sublista ordenada nas posições inferiores da lista. Cada novo item é “inserido” na sublista anterior de modo que a sublista ordenada fique com um item a mais. A Figura 4 mostra o processo de ordenação por inserção. Os itens sombreados representam as sublistas ordenadas conforme cada passagem feita pelo algoritmo.

Figure 4: insertionSort¶

Começamos pressupondo que uma lista com um único item (posição \(0\)) está ordenada. A cada passagem, do item 1 a \(n-1\), o item atual é comparado com os que já estão na sublista ordenada. Conforme vamos caminhando de trás pra frente na sublista já ordenada, movemos os itens que são maiores para a direita. Quando encontramos um item menor ou chegamos ao fim da sublista, o item atual é inserido.

A Figura 5 mostra a quinta passagem em detalhe. Nesse ponto do algoritmo, há uma sublista com cinco itens: 17, 26, 54, 77 e 93. Queremos inserir 31 nesse conjunto já ordenado. A primeira comparação faz com que o item 93 vá para a direita. Os itens 77 e 54 também são deslocados para frente. Quando o item 26 é encontrado, o processo de deslocamento para e o 31 é colocado na lacuna aberta. Temos agora uma sublista ordenada com seis itens.

Figura 5: Ordenação por Inserção: Quinta Passagem do Algoritmo¶

A implementação da ordenação por inserção (ActiveCode 1) mostra mais uma vez que há \(n-1\) passagens para ordenar n itens. A iteração começa na posição 1 e vai até a posição : math:n-1, uma vez que esses são os itens que precisam ser inseridos nas sublistas ordenadas. A linha 8 realiza a operação de deslocamento que move um valor uma posição à direita na lista, abrindo espaço para a inserção. Note que essa não é uma troca completa da mesma maneira que foi mostrada em algoritmos anteriores.

O número máximo de comparações para uma ordenação por inserção é a soma dos primeiros \(n-1\) inteiros. De novo, isso é \(O(n^{2})\). Contudo, no melhor caso, apenas uma comparação é necessária a cada passagem. Esse seria o caso de uma lista já ordenada.

Uma observação importante sobre a diferença entre deslocamento e troca: em geral, a operação de deslocamento requer aproximadamente um terço de processamento de uma troca, já que apenas uma atribuição é feita. Em estudos de desempenho, a ordenação por inserção costuma mostrar ótimos resultados.