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