Analise Metodos de Ordenação

UNIVERSIDADE FEDERAL DO ABC

Felipe Perez Vaz Morais

RA: 21039310

ANÁLISE EMPÍRICA: MÉTODOS DE ORDENAÇÃO

Santo André
Maio de 2014

1 INTRODUÇÃO E OBJETIVOS
Neste trabalho, será avaliado empiricamente o desempenho dos algoritmos de ordenação visto na disciplina. Serão considerados apenas os algoritmos ditos eficientes.
Os algoritmos de ordenação serão avaliados de acordo com o tempo médio de execução de cada algoritmo para determinados tamanhos de vetores compostos de números aleatórios.
2 MÉTODOS

Foram utilizados oito algoritmos de ordenação, seis conjuntos aleatórios baseados no conceito de sementes. Os vetores possuíam tamanhos de 10.000, 30.000, 90.000, 270.000,
810.000, 2.430.000, 7.290.000, 21.870.000, e 65.610.000 elementos (nove vetores). As sementes utilizadas para gerar números aleatórios foram: 4, 81, 151, 1601, 2307, 4207.
Os algoritmos testados foram: HeapSort, MergeSort, ShellSort (as variações Shell, Knuth e Pardons), QuickSort com pivô central, Sort C++ e QSort. O QuickSort com pivô central foi utilizado no lugar do QuickSort orignal como forma de evitar o pior caso do algoritmo.
3 RESULTADOS
O gráfico apresentado abaixo representa a relação de tamanho do vetor vs. tempo de execução dos algoritmos. 70000,00

60000,00
HeapSort (ms)
MergeSort (ms)
50000,00

Shellshort_shell (ms)
Shellshort_knuth
(ms)
Shellshort_pardons
(ms)
QuickSort-Mediano
(ms)
C++ Sort (ms)

40000,00

30000,00

Qsort (ms)
20000,00

10000,00

0,00
10000

10010000

20010000

30010000

40010000

50010000

60010000

70010000

Quicksort se apresentou como o algoritmo mais rápido dos estudados. C++ Sort e QSort que são variações do quicksort foram os mais próximo, sem grande diferença de um para o outro
(QSort apresentou um desempenho levemente maior. Quicksort e suas variações serem os algoritmos mais rápidos dos testes era algo esperado, dado que segundo vários estudos o quicksort no caso médio é O (n *