Ordenação por inserção
A ordenação por inserção é a forma como a maioria das pessoas ordena as cartas na mão: pegar na carta seguinte e encaixá-la no lugar certo entre as cartas já ordenadas. É lenta em listas longas e aleatórias, mas muito rápida em listas curtas ou quase ordenadas, e é por isso que as bibliotecas de ordenação reais ainda a usam.
A ideia
Mantenha o início da lista ordenado. No começo, essa parte ordenada é só o primeiro valor. Pegue no valor seguinte e compare-o com o anterior. Se o anterior for maior, troque-os e compare de novo, uma posição mais atrás. Pare quando o anterior não for maior, ou quando o valor chegar ao início. A parte ordenada cresceu um valor. Repita com cada valor até ao fim.
Um exemplo
Pegue em 5, 1, 4, 2, 8. A passagem 1 pega no 1: 5 é maior, por isso trocam, e o 1 chega ao início: 1, 5, 4, 2, 8. A passagem 2 pega no 4: troca com o 5 e depois para no 1: 1, 4, 5, 2, 8. A passagem 3 pega no 2: troca com o 5 e com o 4, e depois para no 1: 1, 2, 4, 5, 8. A passagem 4 pega no 8, que já é maior do que 5, por isso basta uma comparação. São 7 comparações e 4 trocas. O bubble sort precisa de 9 comparações na mesma lista, a ordenação por seleção de 10.
As trocas são as inversões
Uma inversão é um par de valores pela ordem errada. Trocar dois vizinhos fora de ordem elimina exatamente uma inversão, e a ordenação por inserção só troca vizinhos assim. Por isso faz exatamente tantas trocas quantas as inversões da lista inicial, o mesmo número que o bubble sort. Cada passagem também faz no máximo uma comparação que não leva a uma troca: a que a termina. Assim, as comparações são as inversões mais, no máximo, n − 1.
Adaptativa: rápida quando a lista está quase ordenada
Como o trabalho é o número de inversões mais cerca de n, a ordenação por inserção é rápida sempre que há poucas inversões. Uma lista ordenada precisa de n − 1 comparações e nenhuma troca. Uma lista em que cada valor está a poucas posições do seu lugar demora um tempo próximo de n. Só uma lista longe de estar ordenada, como uma invertida com n(n − 1)/2 inversões, demora um tempo proporcional a n². Numa lista aleatória, a média é de cerca de n²/4 trocas.
Onde é usada
A ordenação por inserção é estável, não precisa de memória extra e tem muito pouco custo adicional. Em listas curtas, bate algoritmos que são mais rápidos no papel. Muitas ordenações de bibliotecas, como o Timsort em Python e Java e o introsort usado em C++, passam para a ordenação por inserção nos pedaços pequenos da lista, normalmente até algumas dezenas de valores. Também serve para dados que chegam um valor de cada vez, porque cada valor novo pode ser inserido assim que chega.
Experimente
Abra a aplicação e prima Reproduzir, ou prima Avançar para ir uma comparação de cada vez. O valor a inserir tem a sua própria cor, o valor com que é comparado fica destacado, e a parte ordenada fica verde. Ao contrário do bubble sort e da ordenação por seleção, a parte verde não é definitiva: um valor mais pequeno que venha depois ainda pode entrar nela. Experimente uma lista quase ordenada para ver como as passagens são curtas, e depois uma invertida.
Perguntas frequentes
Qual é a complexidade temporal da ordenação por inserção?
O(n²) no pior caso e no caso médio, e O(n) no melhor caso, uma lista já ordenada. Mais precisamente, demora um tempo proporcional a n mais o número de inversões. Precisa só de O(1) de memória extra.
Qual é a diferença entre a ordenação por inserção e a ordenação por seleção?
A ordenação por seleção percorre toda a parte não ordenada para encontrar o menor valor, por isso faz sempre n(n − 1)/2 comparações, mas poucas trocas. A ordenação por inserção pega no valor seguinte tal como vem e só o faz recuar o necessário, por isso faz menos comparações, sobretudo em listas quase ordenadas, mas mais trocas.
O que é a ordenação por inserção binária?
Uma variante que encontra o lugar do novo valor com uma pesquisa binária na parte ordenada, o que exige cerca de log n comparações em vez de até n. Os valores continuam a ter de ser deslocados para abrir espaço, por isso o número de movimentos, e o pior caso O(n²), não mudam.
A ordenação por inserção é estável?
Sim. Um valor só recua para lá de valores estritamente maiores, por isso valores iguais mantêm a sua ordem original.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Experimentar a ordenação por inserção