Shellsort
756 palavras
4 páginas
Ordenação: ShellsortAlgoritmos e Estruturas de Dados II
Introdução
Proposto por Donald Shell em 1959
Extensão do algoritmo de ordenação por inserção
2
Motivação
Ordenação por inserção só troca itens adjacentes para determinar o ponto de inserção
São efetuadas n-1 comparações e movimentações quando o menor item está na última posição
O método de Shell contorna este problema permitindo trocas de registros distantes
3
Exemplo
4
Algoritmo
Os conjuntos de itens separados de h posições são ordenados
O elemento na posição x é comparado (e trocado) com o elemento na posição x-h
O vetor resultante é composto de h arquivos ordenados e entrelaçados
O vetor (sequência) é dito estar h-ordenado
Quando h = 1, o algoritmo é equivalente ao algoritmo de inserção
5
Exemplo: Shellsort
E
X
E
M
P
L
O
E
X
E
M
P
L
O
E
L
E
M
P
X
O
E
L
E
M
P
X
O
E
L
E
M
P
X
O
E
L
E
M
P
X
O
E
L
E
M
P
X
O
E
L
E
M
P
X
O
E
L
E
M
O
X
P
E
L
E
M
P
X
O
E
L
E
M
O
X
P
E
L
E
M
O
X
P
E
L
E
M
O
X
P
E
E
L
M
O
X
P
E
E
L
M
O
X
P
E
L
E
M
O
X
P
E
L
E
M
O
X
P
E
L
E
M
O
P
X
h=4
h=2 h = 1 (inserção)
6
Escolha da distância de salto h
Qualquer sequência terminando com h = 1 garante ordenação correta (h = 1 é ordenação por inserção)
Forte impacto no desempenho do algoritmo
Sequência para h:
h(s) = 1, para s = 1
h(s) = 3h(s-1) + 1, para s > 1
A sequência corresponde a 1, 4, 13, 40, 121, 364,
1093, 3280, ...
Knuth (1973, p. 95) mostrou experimentalmente que esta sequência é difícil de ser batida por mais de
20% em eficiência
Outras escolhas são possíveis
7
Escolha da distância de salto h
Qualquer sequência terminando com h = 1 garante ordenação correta h = 1 é ordenação por inserção
Forte impacto no desempenho do algoritmo
Exemplo de sequência ruim: 1, 2, 4, 8, 16, ...
Não compara elementos em posições pares com elementos em posições ímpares até a última iteração
8
Escolha da