Algorítmos de Ordenação - Parte IV

Neste post vamos ver um algorítmo de ordenação um pouco esquisito e menos conhecido.

Ordenação por Incrementos Decrescentes - Shell Sort

Este algorítmo foi inventado por Donald L. Shell, e se baseia na idéia de que podemos ordenar mais rápido se começarmos movendo as chaves distâncias maiores, para que eles cheguem mais rapidamente nas posições finais.

Para usar o Shell Sort, você precisa ter ou gerar uma lista de incrementos decrescentes, onde o último é um. Iniciamos a ordenação ordenando os elementos espaçados pelo primeiro (e maior) incremento. Em seguida, ordenamos os elementos espaçados do segundo incremente e assim por diante. No último passo ordenamos os elementos espaçados de 1, ou seja, todos os elementos. Nos primeiros passos estamos ordenando conjuntos com poucas chaves mas bem diferentes, no final estamos ordenando conjuntos com muitas chaves mas quase totalmente ordenadas. Por este motivo podemos usar a inserção direta para a ordenação de cada conjunto.

Confuso? Vamos a um exemplo, ordenando 8 números usando os incrementos 4, 2 e 1. Vamos ter portanto 3 passos: no primeiro ordenamos 4 conjuntos de 2 chaves, no segundo 2 conjuntos de 4 chaves e no último um único conjunto com as 8 chaves. A figura abaixo mostra os dados originais e o resultado de cada passo.

Exemplo de ordenação por Incrementos Descrescentes

A análise do desempenho deste algorítmo é muito complexa. A escolha dos incrementos é um ponto chave, mas não é simples determinar qual seria uma boa escolha. Knuth sugere como razoável a série 1, 4, 14, 40, 121, etc, na qual cada número é igual a três vezes o anterior mais um. A série deve parar dois números antes de ultrapassar o número de itens a ordenar. Por exemplo, para ordenar 100 itens usaríamos 1, 4 e 13. Usando estes tempos, o tempo médio é proporcionala N^1.25 e pior caso proporcional a N^1.5. Memória adicional pode ser necessária para guardar os incrementos (se os calcularmos antecipadamente), a série sugerida possui log₃(N) incrementos. O Shell Sort não é estável.

Na próxima parte desta série vamos ver o algoritmo mais conhecido de ordenação (pelo menos no nome) - o Quicksort.

06/08/07: Acertados os subscripts e superscripts.