Análise Téorica e Prática de Métodos de Ordenação

UNIVERSIDADE FEDERAL DE MINAS GERAIS
ALGORITMOS E ESTRUTURAS DE DADOS II

ANÁLISE DE ALGORITMOS DE ORDENAÇÃO:
ANÁLISE TEÓRICA E EMPÍRICA DOS ALGORITMOS DE ORDENAÇÃO
INSERTION SORT, QUICK SORT E HEAP SORT

DIOGO LOURENÇO PINTO

BELO HORIZONTE
ABRIL DE 2014

ALGORITMOS E ESTRUTURAS DE DADOS II
DIOGO LOURENÇO PINTO

ANÁLISE DE ALGORITMOS DE ORDENAÇÃO:
ANÁLISE TEÓRICA E EMPÍRICA DOS ALGORITMOS DE ORDENAÇÃO
INSERTION SORT, QUICK SORT E HEAP SORT

Trabalho acadêmico com vistas à aprovação na disciplina Algoritmos e
Estruturas de Dados II, apresentado ao
Prof. Dr. Sebastián Urrutia e Prof. Dr.
Thiago Ferreira de Noronha, do curso de graduação em Engenharia Elétrica da
Universidade Federal de Minas Gerais.

BELO HORIZONTE
ABRIL DE 2014

Introdução
Um algoritmo é uma sequência finita de instruções bem definidas e não ambíguas, cada uma das quais pode ser executada mecanicamente num período de tempo finito e com uma quantidade de esforço finita. A maioria dos algoritmos é desenvolvida para ser implementada em um programa de computador através de uma linguagem de programação A análise de algoritmos estuda o desempenho, viabilidade e aplicabilidade do mesmo. Além disto, estuda certos paradigmas (como divisão-e-conquista, programação dinâmica, etc.) que se mostraram úteis na criação de algoritmos para vários problemas computacionais. Este trabalho aplicará técnicas de análise sobre uma classe muito importante e recorrente de algoritmos: os algoritmos de ordenação.
Algoritmo de ordenação é um algoritmo que coloca os elementos de uma dada sequência em uma certa ordem, efetuando sua ordenação completa ou parcial. As ordens mais usadas são a numérica e a lexicográfica. Uma razão para se ordenar uma sequência é a possibilidade se acessar seus dados de modo mais eficiente, por exemplo. Será analisado e discutido os algoritmos de ordenação Insertion Short, Quick Sort, e, por último, o Heap Sort.
Num primeiro instante será apresentado as