Desenvolvimentos de algorítmos

Universidade Federal de Ouro Preto
Instituto de Ciências Exatas e Biológicas
Departamento de Computação

ALGORITMOS E ESTRUTURAS DE DADOS
Quinto Trabalho Prático
Análise de Desempenho de Algoritmos de Ordenação por
Comparação e suas Variações e Otimizações

Luiz Henrique Santos
Professor - David Menotti
Monitor - Kayran dos Santos
Monitor - Pedro Ismar Silva Souto

Ouro Preto
9 de dezembro de 2009

Sumário
1 Introdução
1.1 Considerações iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Computador usado para testes . . . . . . . . . . . . . . . . . . . . . .
1.3 Especificação do problema . . . . . . . . . . . . . . . . . . . . . . . .
2 Metodos de Ordenação
2.1 Ordenação Interna . . . . . . . . . . .
2.2 BubbleSort . . . . . . . . . . . . . . .
2.2.1 Implementação . . . . . . . . .
2.2.2 Comparação BubbleSort . . . .
2.3 SelectSort . . . . . . . . . . . . . . . .
2.3.1 Implementação . . . . . . . . .
2.3.2 Comparação SelectSort . . . . .
2.4 InsertSort . . . . . . . . . . . . . . . .
2.4.1 Implementação . . . . . . . . .
2.4.2 Comparação InsertSort . . . . .
2.5 Comparação dos Métodos Simples . . .
2.6 QuickSort . . . . . . . . . . . . . . . .
2.6.1 Implementação . . . . . . . . .
2.7 HeapSort . . . . . . . . . . . . . . . . .
2.7.1 Implementação . . . . . . . . .
2.8 MergeSort . . . . . . . . . . . . . . . .
2.8.1 Implementação . . . . . . . . .
2.9 Comparação dos métodos eficientes . .
2.10 Métodos Simples x Métodos Eficientes
3 Testes
3.1 Vetor
3.2 Vetor
3.3 Vetor
3.4 Vetor

Ordenado . . . . . . . .
Quase Ordenado . . . .
Aleatório . . . . . . . .
Inversamente ordenado

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.