mauro

Páginas: 2 (430 palavras) Publicado: 1 de setembro de 2014
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 adjacentespara 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 fatode 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 passavá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 agostode 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, acomeç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:
•...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Mauro
  • Mauro
  • Mauro
  • MAURO GARRETT
  • Dj mauro
  • mauro munhoz
  • Mauro betti
  • AP Mauro

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!