Métodos de Ordenação - PT01

Prévia do material em texto

Prof. Jesus José de Oliveira Neto
� O que é ordenação?
- Ordenação é o processo de rearranjar um conjunto de 
objetos em uma ordem ascendente ou descendente.
� Por exemplo:
◦ Fora de ordem: 5, 2, 1, 3, 4
◦ Ordenado: 1, 2, 3, 4, 5 ou 5, 4, 3, 2, 1
� Por que utilizar ordenação?
- A ordenação permite que o acesso aos dados seja feito de 
forma mais eficiente. 
� É parte de muitos métodos computacionais
◦ Algoritmos de busca, intercalação/fusão, utilizam ordenação como 
parte do processo
◦ Aplicações em geometria computacional, bancos de dados, entre 
outras necessitam de listas ordenadas para funcionar
 A ordenação é baseada em uma chave
 A chave de ordenação é o campo do item de dados utilizado 
para comparação. Por exemplo:
Valor armazenado em um vetor de inteiros
Campo nome de uma struct, dentre outros
 É por meio da chave que sabemos se um determinado item 
está a frente ou não de outros no conjunto
 Além disso, a ordenação pode ser estável ou não
 Um algoritmo de ordenação é considerado estável se a 
ordem dos elementos com chaves iguais não muda durante 
a ordenação
 O algoritmo preserva a ordem relativa original dos valores
 Exemplo: considere estes dados não ordenados:
 5a, 2, 5b, 3, 4, 1
 Onde 5a e 5b são o mesmo número (a e b servem apenas 
para definir sua posição um relação ao outro)
 Dados ordenados
1, 2, 3, 4, 5a, 5b: ordenação estável
1, 2, 3, 4, 5b, 5a: ordenação não-estável
Tipos de Ordenação
 Ordenação Interna: conjunto de dados que deve ser
ordenado. Cabe na memória principal.
 Todos os elementos podem ser acessados
imediatamente.
 Quanto menor for o uso da memória principal, melhor será
o desempenho
� Para calcular a complexidade de um algoritmo de 
ordenação interna são necessários dois itens:
◦ O número de comparações entre as chaves.
◦ O número de movimentações de itens no arquivo.
� A complexidade do algoritmo sofre influência dos números
de chaves contida nos registros dos arquivos.
� Métodos de Ordenação Elementares
◦ Utilizados em pequenos arquivos.
◦ Ordem de complexidade O(n2).
◦ Implementação Simples. Ex.: InsertionSort, BubbleSort, etc.
� Métodos de Ordenação Avançados
◦ Utilizados em grandes arquivos.
◦ Usam menos comparações.
◦ Ordem de complexidade O(n log n).
◦ Implementação mais complexa. Ex.: QuickSort, MergeSort, 
etc.
� Ordenação Externa: conjunto de dados que deve ser
ordenado. Não cabe na memória principal.
◦ Troca de informações entre a memória secundária e a 
principal interfere no desempenho do algoritmo.
◦ Os registros devem ser acessados seqüencialmente ou
em grandes blocos.
� Também conhecido como ordenação por seleção
� Algoritmo de ordenação bastante simples
� A cada passo ele seleciona o melhor elemento para ocupar 
aquela posição do vetor
◦ Maior ou menor, dependendo do tipo de ordenação
◦ Na prática, possui um desempenho quase sempre superior quando 
comparado com o bubble sort
� Funcionamento: a cada passo, procura o menor valor do 
vetor e o coloca na primeira posição do vetor
� Avança da primeira posição do vetor e repete o processo 
para a segunda posição e assim por diante
� Isso é feito para todas as posições do vetor
� Para cada posição i, procura no restante do vetor o menor 
valor para ocupá-la
� Para cada posição i, procura no restante do vetor o menor 
valor para ocupá-la
� Vantagem
◦ Estável: não altera a ordem dos dados iguais
� Desvantagens
◦ Sua eficiência diminui drasticamente a medida que o número de 
elementos no vetor aumenta
◦ Não é recomendado para aplicações que que envolvam grandes 
quantidade de dados ou que precisem de velocidade
� Considerando um vetor com N elementos, o tempo de execução é 
sempre de ordem O(N2)
� A eficiência do SelectionSort não depende da ordem inicial dos 
elementos
� Melhor do que o BubbleSort
� Apesar de possuírem a mesma complexidade no caso médio, na 
prática o SelectionSort quase sempre supera o desempenho do 
BubbleSort pois envolve um número menor de comparações
� Também conhecido como ordenação por inserção
� Similar a ordenação de cartas de baralho com as mãos
◦ Pegue uma carta de cada vez e a insira em seu devido lugar, sempre 
deixando as cartas da mão em ordem
� O algoritmo percorre o vetor e para cada posição i verifica 
se o seu valor está na posição correta
� Isso é feito percorrendo o vetor da posição i - 1 até zero 
(início do vetor) deslocando uma posição para frente os 
valores que são maiores do que o valor da posição i
� Desse modo, teremos uma posição livre para inserir o valor 
da posição j para o seu devido lugar
� Para cada posição i, movimenta os valores maiores uma 
posição para frente no vetor
� Para cada posição i, movimenta os valores maiores uma 
posição para frente no vetor
� Considerando um vetor com N elementos, o 
tempo de execução é:
◦ O(N), melhor caso: os elementos já estão 
ordenados. 
◦ O(N2), pior caso: os elementos estão ordenados na 
ordem inversa.
◦ O(N2), caso médio.
� Fácil de implementar.
� Estável: não altera a ordem dos dados iguais
� É um bom método quando se deseja adicionar uns poucos 
itens a um arquivo ordenado, pois o custo é linear.
� É mais eficiente quando o conjunto de dados está “quase 
ordenado”.
� Na prática, é mais eficiente que a maioria dos algoritmos de 
ordem quadrática como o SelectionSort e o BubbleSort.
� Alto custo de movimentação de elementos no vetor
� Pouco eficiente para conjunto de dados desordenados
� Proposto por Donald Shell em 1959. É uma extensão do 
InsertionSort.
� Problema com o algoritmo de ordenação por 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 do vetor.
� O método de Shell contorna este problema permitindo trocas 
de registros distantes um do outro.
� Os itens separados de h posições são rearranjados, gerando 
sequências ordenadas.
� É dito que cada sequência está h-ordenada.
� Depois, o valor de h é reduzido progressivamente, até atingir 
o valor 1, que resultará no vetor completamente ordenado.
� À medida que h decresce, o vetor vai ficando cada vez mais 
próximo da ordenação.
� Com h = 1, o algoritmo se comporta exatamente igual ao 
InsertionSort.
� Mas, como podemos escolher uma boa sequência de valores 
para h?
� Como escolher o valor de h?
◦ 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 (1973, p. 95) mostrou experimentalmente que esta 
sequência é difícil de ser batida por mais de 20% em 
eficiência.
� A complexidade do algoritmo ainda não é conhecida.
� Ninguém foi capaz de analisar o algoritmo até hoje.
◦ Depende de 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.
� Shellsort é uma ótima opção para arquivos de tamanho 
moderado (±10000 itens).
� Sua implementação é simples e requer uma quantidade de 
código pequena.
� O tempo de execução do algoritmo é sensível à ordem 
inicial do arquivo.
� O método não é estável.