Estruturas de Dados - Ordenação Métodos Eficientes

Prévia do material em texto

Ordenação Métodos Eficientes
Estruturas de Dados
Profa. Carla Koike
   
Métodos de Ordenação
● Métodos Básicos:
– Bubblesort, ou bolha
– Seleção
– Inserção
● Método Eficiente
– Quicksort
– Shellsort
– Mergesort
– Heapsort
   
Método Shellsort
● Proposto por Shell em 1959.
● É uma extensão do algoritmo de ordenação por 
inserção.
● 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 no 
vetor.
● O método de Shell contorna este problema permitindo 
trocas de registros distantes um do outro
   
Shellsort
● Os itens separados de h posições são 
rearranjados.
● Todo h­ésimo item leva a uma seqüência 
ordenada.
● Tal seqüência é dita estar h­ordenada.
● Quando h = 1 Shellsort corresponde ao 
algoritmo de inserção.
   
Shellsort ­ Ilustração
3 7 9 0 5 1 6
8 4 2 0 6 1 5
7 3 4 9 8 2
3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2 
3 3 2 0 5 1 5
7 4 4 0 6 1 6
8 7 9 9 8 2
3 3 2
0 5 1
5 7 4
4 0 6
1 6 8
7 9 9
8 2
0 0 1
1 2 2
3 3 4
4 5 6
5 6 8
7 7 9
8 9
   
Shellsort ­ Ilustração
   
Como escolher h's
● Não há prova da melhor seqüência
● Knuth (1973) propôs a seqüência:
– 1, 4, 13, 40, 121, 364, 1093, 3280, ...
– Experimentalmente, ele demonstrou que esta 
seqüência é difícil de ser batida por mais de 20% 
em eficiência.
● Na prática, usa­se:
– h
1
 = 1
– h
i+1
 = 3*h+1
   
void shellSort( int * vet, int size ){  
    int i , j , value;
    int gap = 1;    
    do {gap = 3*gap+1;} while ( gap < size );
    do {
         gap /= 3;
         for ( i = gap; i < size; i++ ){
               value =vet[i];
               j = i ­ gap;
               while ( j >= 0 && value < vet[j] ){
                     vet [j + gap] =vet[j];
                     j ­= gap;
               }
               vet [j + gap] = value;
         }
     } while ( gap > 1);
}
Shellsort
   
Shellsort
● Ninguém ainda foi capaz de analisar o algoritmo!!!
● Vantagens:
– Shellsort é uma ótima opção para arquivos de tamanho 
moderado.
– Sua implementação é simples e requer uma 
quantidade de código pequena.
● Desvantagens:
– O tempo de execução do algoritmo é sensível à ordem 
inicial do arquivo.
– O método não é estável
   
Mergesort – Ordenação por Fusão
● É mais rápido ordenar vetores menores que 
vetores maiores
● É mais rápido fundir dois vetores ordenados 
que dois vetores não ordenados
● Idéia básica: dividir o vetor em vetores 
menores, ordenar os vetores menores, fundir 
os vetores menores ordenados
   
Método Mergesort
● Dividir a lista não ordenada em duas listas de 
tamanho aproximado
● Dividir cada uma dessas listas menores em 
duas recursivamente, até que que as listas 
tenham tamanho um
● Fundir as duas listas de volta em um única lista, 
desta vez ordenada.
● MergeSort.c
   
Mergesort Ilustração 
   
Análise do Algoritmo
● Complexidade de tempo dos casos médio e 
pior caso O(n logn)
● Complexidade de espaço O(n), no pior caso
● Método Estável
● Fácil paralelização
● Eficiente para ordenar uma lista encadeada
– Complexidade espacial se torna O(1). Porque????
   
Método Heapsort – Ordenação de 
Raiz
● Possui o mesmo princípio de funcionamento da 
ordenação por seleção.
● Utiliza uma estrutura de dados chamada heap 
(Raiz) para ordenar os elementos a medida que 
os insere na estrutura. 
● Comparável a ordenação usando pilhas de 
elementos:
– Ao ordenar livros, criam­se pilhas por ordem letra, e 
cada pilha é ordenada separadamente, usando o 
mesmo método
   
Método Heapsort
● Ao final das inserções, os elementos podem 
ser sucessivamente removidos da raiz da heap, 
na ordem desejada.
● A heap pode ser representada como uma 
árvore ou como um vetor.
   
TAD Heap
● É uma seqüência de itens com chaves c[1], c[2], . . . , c[n], 
tal que:
– c[i] ≥ c[2i],
– c[i] ≥ c[2i + 1], para todo i = 1, 2, . . . , n/2.
Max heap Min heap
   
TAD Heap
● As chaves na árvore satisfazem a condição do heap.
● A chave em cada nó é maior/menor do que as chaves 
em seus filhos.
● A chave no nó raiz é a maior/menor chave do 
conjunto.
Max heap Min heap
   
TAD Heap
●   Uma árvore binária completa pode ser representada 
por um array:
1  2   3   4  5   6   7
S  R  O  E  N  A   D
● A representação é extremamente compacta.
● Permite caminhar pelos nós da árvore facilmente.
● Os filhos de um nó i estão nas posições 2i e 2i + 1.
● O pai de um nó i está na posição i div 2.
   
Operações no TAD Heap ­ Inserção
   
Operações no TAD Heap ­ 
Remoção
   
Heapsort
● Dados armazenados na forma de heap
● A ordenação se dá pela retirada a partir da raiz
● A cada retirada, a heap é refeita
   
Análise
● Comparações: O(n lgn)
● Trocas: O(n lgn)
● Melhor que Quicksort, que é O(n2) no pior caso
● Método Não estável
● Recomendado para aplicações que não podem 
tolerar eventualmente um caso desfavorável.
● Não é recomendado para arquivos com poucos 
registros, por causa do tempo necessário para 
construir o heap.
   
Comparação entre Métodos ­ 
Complexidade
Não se conhece
Analiticamente
   
Tempo de Execução
● O método que levou menos tempo real para executar recebeu o valor 
1 e os outros receberam valores relativos a ele.
● Registros em ordem aleatória           Registro em ordem Inversa
Registros em Ordem
   
Comparando os Métodos Eficientes
● O Shellsort é bastante sensível à ordenação ascendente ou 
descendente da entrada.
● Em arquivos do mesmo tamanho, o Shellsort executa mais 
rápido para arquivos ordenados.
● O Quicksort é sensível à ordenação ascendente ou 
descendente da entrada.
● Em arquivos do mesmo tamanho, o Quicksort executa mais 
rápido para arquivos ordenados.
● O Quicksort é o mais rápido para qualquer  tamanho para 
arquivos na ordem ascendente.
● O Heapsort praticamente não é sensível à ordenação da 
entrada.
   
Árvore de Decisão
● Árvores binárias onde cada nó representa um 
comparação: o filho a esquerda é o caminho se 
a resposta for sim, e o filho a direita é o 
caminho se a resposta for não.
● Árvores de decisão auxiliam na análise de 
performance de um algoritmo de ordenação 
para um certo tipo de problema
   
Mínimo entre três números
   
Árvore de Decisão
● Cada folha representa um resultado possível.
● O número de folhas deve ser pelo menos igual 
ao número de resultados possíveis
● O trabalho do algoritmo pode ser traçado 
através de um caminho da raiz até uma folha
● O número de comparações é igual ao número 
de arestas neste caminho.
   
Número de Comparações de 
Algoritmo
● A maioria dos algoritmos de ordenação são baseados 
em comparação, i.e. eles funcionam comparando 
elementos da lista.
● O número de comparações no pior caso é igual a 
altura da árvore de decisão. 
● Para uma árvore binária com x folhas e altura h:
                        h ≥ log
2
 x
●  O maior número de folhas em uma árvore será 2h
●  A desigualdade h ≥ log2 x impõe um limite inferior na 
altura da árvore de decisão
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29