Will

4.5 - Métodos de ordenação Shellsort
É um método de ordenação cujo princípio de funcionamento é o mesmo utilizado para a ordenação por inserção. O método de inserção troca itens adjacentes quando está procurando o ponto de inserção na sequência destino. Se o menor item estiver na posição mais à direita no vetor então o número de comparações e movimentações é igual a (n-1) para encontrar o seu ponto de inserção.
O método shellsort contorna este problema permitindo trocas de registros que estão distantes um do outro. Os itens que estão separados h posições são re-arranjados de tal forma que todo h-ésimo item leva a uma sequência ordenada. Tal sequência é dita estar h- ordenada. A tabela abaixo mostra a sequência de ordenação usando os incrementos: 4, 2 e 1 com o valores de h. 1 2 3 4 5 6 Chave inicial O R D E N A h = 4 N A D E O R h = 2 D A N E O R h = 1 A D E N O R

Na primeira passada (h=4), a letra O é comparada com a letra N (posições 1 e 5) e trocados, a seguir o R é comparado com o A (posições 2 e 6) e trocados. Na segunda passada (h=2), as letras N, D e O nas posições 1, 3 e 5 são re-arranjadas para resultar em D, N e O nestas mesmas posições; da mesma forma as letras A, E e R nas posições 2, 4 e 6 são comparados e mantidos nos seus lugares. A última passada (h=1) corresponde ao algoritmo de inserção, entretanto nenhum item tem que se mover para posições muito distantes. Várias sequências para h tem sido experimentadas, Knuth mostrou