Avaliação empírica de desempenho dos algoritmos de ordenação: quicksort, mergesort e heapsort

Avaliação empírica de desempenho dos algoritmos de ordenação: Quicksort, Mergesort e Heapsort
Andrew Cavalcante Pacífico Instituto de Computação Universidade Federal do Amazonas, Manaus – AM – Brasil.
{[e-mail]}

1.

Introdução

O trabalho consistia em fazer uma análise de desempenho dos algoritmos de ordenação Quicksort, Mergesort e Heapsort. Foram realizados experimentos com os 3 algoritmos, onde os mesmos foram utilizados para ordenar vetores de tamanho 10.000, 100.000, 1.000.000, 10.000.000 e 100.000.000, e foram analisados os tempos de execução dos algoritmos em função do tamanho da entrada. Para cada um dos algoritmos foram realizados testes com 50 vetores com inteiros naturais entre 0 e 65535 para cada tamanho de entrada, e ainda foram realizados testes com vetores compostos apenas pelos números 1 e 0 dispostos aleatoriamente nos vetores.

2.

Descrição dos experimentos e arquivos fornecidos

Os experimentos foram realizados utilizando as implementações dos slides passados em sala de aula. Além dos programas que executam os algoritmos de ordenação foi criado um programa geraEntrada, que é responsável por criar todas as entradas utilizadas nos experimentos. Os arquivos fornecidos são os códigos-fonte de todos os programas utilizados no trabalho, um Makefile responsável por compilar todos os fontes, e pra cada algoritmo de ordenação, são fornecidos 2 scripts que executam o algoritmo para todas as entradas. Um executa para as entradas compostas de inteiros entre 0 e 65535, e o outro para as entradas compostas por 1 e 0. Os tempos de execução de cada um dos algoritmos foram medidos utilizando o comando time do Linux.

3. 3.1.

Testes realizados com inteiros naturais Entradas de tamanho 10.000

Para entradas de tamanho 10.000 o desempenho dos três algoritmos acabou sendo muito semelhante, o que mostra que para entradas pequenas os três algoritmos podem ser utilizados sem nenhuma visível diferença de desempenho. A seguir são