Comparação Empírica de Algoritmos de Ordenação

Comparação Empírica de Algoritmos de
Ordenação

UFABC, maio de 2012

1

Sumário

Sumário
Objetivos
Metodologia
Resultados
Análise
Conclusão
Estimativas para simulações não realizadas
Bibliografia

2

Objetivos
Realizar um estudo empírico do consumo de tempo dos agoritmos de ordenação Bubble
Sort, Insertion Sort, Selection Sort, Quick Sort, Heap Sort e Merge Sort.

Metodologia
Através da linguagem de programação C, foi criado um módulo com as funções de ordenação a serem exploradas(interface ordenacao.h e implementaçãp ordenacao.c que estão como anexo), utilizou­se também um módulo com funções de heap(heap.h e heap.c utilizados por alunos de Algorítmos e Estrutura de Dados I da UFABC durante o primeiro quadrimestre).
Foram implementadas 6 funções de ordenação em ordenacao.c, sendo estas os algoritmos Bubble Sort, Insertion Sort, Selection Sort, Quick Sort, Heap Sort e Merge Sort.
Todas as funções implementadas em ordenacao.c recebem como parâmetro um ponteiro para vetor v de inteiros(a sequência a ser ordenada) e o número inteiro n(quantidade de posições do vetor).
Cada algoritmo de ordenação foi testado para 9 tamanhos diferentes de sequências(10.000, 30.000, 90.000, 270.000, 810.000, 2.430.000, 7.290.000, 21.870.000 e
65.610.000). Ou seja, começando com uma sequência de 10.000 números, foi­se aumentando a quantidade de números a serem testados multiplicando­se por 3 até o ultimo tamanho de
65.610.000 números.
Para cada tamanho de sequência/vetor foram geradas 6 diferentes sequências pseudoaleatórias, sendo que as 6 sequecências utilizadas no teste de um algoritmo foram as mesmas seis sequências utilizadas para o teste do outro algoritmo, garantindo que a comparação fosse justa. Foram usadas as sementes 4, 81, 151, 1601, 2307, 4207 para gerar as sequências peseudoaleatórias.
Dessa forma tem­se (6 algoritmos) x (9 tamanhos) x (6 sequências aleatórias) = 324 ordenações a serem realizadas. No entando, os algorítmos menos