Métodos de ordenação

Prévia do material em texto

Comparação entre os métodos 
de ordenação 
Laboratório de Algoritmos e Estruturas de Dados
Número de comparações 
Método Complexidade
Bubble O(n²) 
Insertion O(n²)
Selection O(n²)
Quick O(n log(n)) 
Shell O(n log(n)²) 
Merge O(n log n)
Tempo de execução – Ordem Aleatória 
 O método que levou menos tempo real para executar recebeu o 
valor 1 e os outros receberam valores relativos: Quicksort
50 mil 100 mil 150 mil 200 mil 250 mil 300 mil
Bubble 1914 3487 6078 7876 9917 11308
Insertion 322 633 1102 1425 1805 2024
Selection 530 1014 1772 2296 2895 3229
Quick 1 1 1 1 1 1
Shell 1,7 1,8 2,1 2,2 2,4 2,1
Merge 2,1 1,7 2,0 2,0 2,1 2,0
Gráfico comparativo - Ordem Aleatória 
0
2000
4000
6000
8000
10000
12000
50 mil 100 mil 150 mil 200 mil 250 mil 300 mil
Aleatório
Bubble Insertion Selection Quick Shell Merge
Tempo de execução – Ordem Crescente
 O método que levou menos tempo real para executar recebeu o 
valor 1 e os outros receberam valores relativos: Insertion
50 mil 100 mil 150 mil 200 mil 250 mil 300 mil
Bubble 33291 66106 84773 125337 164422 1104556
Insertion 1 1 1 1 1 1
Selection 15496 31081 40489 59082 78366 107406
Quick 10 11 10 11 11 12
Shell 13 15 13 15 16 17
Merge 38 39 35 38 46 42
Gráfico comparativo – Ordem Crescente
0
200000
400000
600000
800000
1000000
1200000
50 100 150 200 250 300
Crescente
Bubble Insertion Selection Quick Shell Merge
Tempo de execução – Ordem Decrescente
 O método que levou menos tempo real para executar recebeu o 
valor 1 e os outros receberam valores relativos: Insertion
50 mil 100 mil 150 mil 200 mil 250 mil 300 mil
Bubble 33221 45118 96403 132267 97322 233338
Insertion 1 1 1 1 1 1
Selection 16163 20993 47808 62699 46719 108342
Quick 10 8 11 11 7 14
Shell 13 10 15 16 9 21
Merge 39 26 41 48 24 56
Gráfico comparativo – Ordem Decrescente
0
50000
100000
150000
200000
250000
50 100 150 200 250 300
Decrescente
Bubble Insertion Selection Quick Shell Merge
Observações
• Quicksort é o mais rápido para todos os tamanhos aleatórios 
experimentados
• Insertion é o método mais rápido para qualquer tamanho se os 
elementos estão em ordem crescente e decrescente
• Merge e Shellsort possuem velocidades parecidas para todos os 
tamanhos aleatórios
• A relação Shell/Quicksort aumenta com o tamanho da entrada 
• Bubblesort não é muito indicado para ordenação de muitos elemento