mauro

Introdução
Foi proposto por Shell em 1959, como uma extensão do algoritmo de ordenação por inserção para resolver o problema com o algoritmo de ordenação por inserção, trocando itens adjacentes para determinar o ponto de inserção e efetuando n-1 comparações e movimentações quando o menor item está na posição mais à direita no vetor, permitindo assim trocas de registros distantes um do outro. Shellsort é o mais eficiente algoritmo de classificação dentre os de complexidade quadrática. É um refinamento do método de inserção direta.2 O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles. Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção. Implementações do algoritmo. Procure a versão em inglês desse mesmo link.

Universidade Estadual de Maringá
Departamento de informática

Shellsort

Nome: Tiago Timóteo Zenon
R.A.: 53648

Maringá, 25 de agosto de 2014
Exemplo de utilização

Quando h=1, Shellsort é igual ao algoritmo de inserção.
Para S=1; h(s)= 1
Para s>1;
-h(s)=3h(s-1)+1
A sequência para h corresponde a 1,4, 13, 40, 121, 364, 1.093, 3.280, ...
Knuth mostrou experimentalmente que esta sequência é difícil de ser batida por mais de 20% em eficiência. Como escolher o valor de h? h = [log3 (2n +1)]

IMPLEMENTAÇÃO

Ánalise
A razão da eficiência do algoritmo ainda não é conhecida, ninguém ainda foi capaz de analisar o algoritmo pois a sua análise contém alguns problemas matemáticos muito difíceis, a começar pela própria sequência de incrementos. O que se sabe é que cada incremento não deve ser múltiplo do anterior.
Conjecturas referentes ao número de comparações para a sequência de Knuth:
•