Buscar

AEDSII_aula_016_shellsort

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 14 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 14 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 14 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Ordenação: Shellsort 
Algoritmos e Estruturas de Dados II 
Introdução 
}  Proposto por Donald Shell em 1959. 
}  Extensão do algoritmo de ordenação inserção. 
2 
Motivação 
3 
while (( j >= 0 ) && (aux.Chave < v[j].Chave)) { 
 v[j + 1] = v[j]; 
 j--; 
} 
11 comp. 
24 comp. 
Motivação 
4 
}  Problema do método de inserção 
}  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 posição mais à direita no vetor. 
}  O método de Shell contorna este problema 
permitindo trocas de registros distantes um do outro. 
Algoritmo 
5 
}  Os itens separados de h posições são rearranjados. 
}  Todo h-ésimo item leva a uma sequência ordenada. 
}  Tal sequência é dita estar h-ordenada. 
}  Quando h=1, o algoritmo é equivalente ao algoritmo 
de inserção 
Exemplo 
6 
}  Entrada: O R D E N A 
}  h = 4, 2, 1 
Escolha do h 
7 
}  Sequência para h: 
}  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. 
1s para 113
1 s para ,1)(
>+=
==
)h(s- h(s) 
sh
ShellSort 
void Shellsort (Item* A, int n) { 
int i, j; 
int h = 1; 
Item aux; 
 
 do /* calcula o h inicial */ 
 h = h * 3 + 1; 
 while (h < n); 
 
 do { 
 h = (h-1/3); /* atualiza o valor de h */ 
 for(i = h; i < n; i++) { 
 aux = A[i]; j = i; 
 
 /* efetua comparações entre elementos com distância h */ 
 while (A[j – h].Chave > aux.Chave) { 
 A[j] = A[j – h]; j -= h; 
 if (j < h) break; 
 } 
 A[j] = aux; 
 } 
 } while (h != 1); 
} 
ShellSort 
n  Análise 
q  A razão da eficiência do algoritmo ainda não é 
conhecida. 
q  Ninguém ainda foi capaz de analisar o algoritmo. 
q  A sua análise contém alguns problemas 
matemáticos muito difíceis. 
q  A começar pela própria seqüência de incrementos. 
q  O que se sabe é que cada incremento não deve ser 
múltiplo do anterior. 
ShellSort 
n  Análise 
q  Conjecturas referente ao número de 
comparações para a seqüência de Knuth: 
 Conjectura 1 : C(n) = O(n1,25) 
 Conjectura 2 : C(n) = O(n (ln n)2 ) 
ShellSort 
n  Vantagens: 
q  Shellsort é uma ótima opção para arquivos de tamanho 
moderado. 
q  Sua implementação é simples e requer uma quantidade de 
código pequena. 
 
n  Desvantagens: 
q  O tempo de execução do algoritmo é sensível à ordem 
inicial do arquivo. 
q  O método não é estável. 
Exercícios 
12 
1.  Mostre um exemplo de entrada que demonstra que o 
método de ordenação seleção não é estável. 
2.  Mostre um exemplo que demonstra que o Shellsort é 
instável para sequencia h=1,2 
3.  O método da bolha não é adaptável, altere o código para 
que ele se torne adaptável. 
4.  Qual dos métodos: bolha, inserção e seleção executa menos 
comparações para um vetor de entrada contendo valores 
idênticos. 
Exercícios 
13 
1.  Dê um exemplo de um vetor com N elementos que 
maximiza o número de vezes que o mínimo é atualizado no 
método de ordenação seleção. 
2.  Mostre um exemplo de entrada que demonstra que o 
método de ordenação seleção não é estável. 
3.  Mostre um exemplo que demonstra que o Shellsort é 
instável para sequencia h=1,2 
4.  O método da bolha não é adaptável, altere o código para 
que ele se torne adaptável. 
5.  Qual dos métodos: bolha, inserção e seleção executa menos 
comparações para um vetor de entrada contendo valores 
idênticos. 
14

Outros materiais