quarta-feira, julho 18, 2007

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 N1.25 e pior caso proporcional a N1.5. Memória adicional pode ser necessária para guardar os incrementos (se os calcularmos antecipadamente), a série sugerida possui log3(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.

2 comentários:

Anônimo disse...

Olá,

Existe um site em que há possibilidade de ver os métodos de organização funcionando, para um melhor exemplo , o site é:
http://cg.scs.carleton.ca/~morin/misc/sortalg/
fica aí a dica.

Muito bom o artigo também, aguardo as outras partes.
[]'s

Daniel Quadros disse...

BlackFalcon,

Legal o site. Um dos exemplos que vou postar no final da série é uma demonstração dos algorítmos para rodar sob Windows.