Analise Empírica de Algoritmos de Ordenação

CENTRO UNIVERSITÁRIO DO TRIÂNGULO - UNITRI

Victor Bernardes Araújo

Analise Empírica de Algoritmos de Ordenação

Uberlândia, 2013

Victor Bernardes Araújo

Analise Empírica de Algoritmos de Ordenação

Trabalho apresentado no Curso de Ciência da
Computação do Centro Universitário do Triângulo UNITRI a ser avaliado na disciplina de Analise de
Algoritmos.

Professor Humberto

Uberlândia, 2013

RESUMO

Este trabalho apresenta a analise empírica de quatro diferentes tipos de algoritmos de ordenação. O objetivo dele é mostrar as diferentes formas que os algoritmos utilizam para ordenar, a eficácia de cada um e o melhor uso de cada para as diferentes situações que possam surgir. I.

INTRODUÇÃO

Neste trabalho nos analisaremos quatro diferentes tipos de algoritmos de ordenação, sendo eles:


Bubble Sort;



Insertion Sort;



Heap Sort;



Quick Sort;

Na hora dos testes dos códigos de ordenamento iremos analisar qual o melhor caso e o pior caso para cada um dos métodos de ordenamento, iremos trabalhar com vetores de dados do tipo int (inteiro) nos tamanhos de: 100.000, 1.000.000, 5.000.000 e 10.000.000 de posições e analisar o tempo gasto para se compilar o código para cada um dos tamanhos citados.

II.

FUNDAMENTOS BASICOS

1. Quick Sort

É um algoritmo de ordenação do tipo de particionamento que foi inventado por Hoare
[HOA62]. O primeiro elemento da lista a ser classificada é escolhido como o pivô. Depois da primeira fase da classificação, o pivô ocupa a posição que ocupará quando a lista estiver completamente classificada. Os registros com valores de chaves menores do que o valor de chave do registro pivô o precedem na lista e os registros com valores de chaves maiores do que o valor

de

chave

do

registro

pivô

o

sucedem

na

lista.

Cada registro é comparado com o registro pivô e suas posições são permutadas se o valor de chave do registro for maior e o registro