Relatório comparativo de métodos de ordenação

Universidade Federal de Lavras
GCC 111 - Projeto e Análise de Algoritmos

TRABALHO PRÁTICO 1

Professor: Eric Fernandes de Mello Araújo
Aluno: Juliano Alves de Lima Pereira

Sumário
Conteúdo

Página

1. Introdução
1.1 Descrições do trabalho
1.2 Métodos de Ordenação
1.3 Vetores
1.4 Considerações na comparação
1.5 Códigos

3
3
3
3
3
4

2. Implementação
2.1 Método de ordenação de um modo geral
2.2 Vetores
2.3 Insert Sort
2.4 Bubble Sort
2.5 Selection Sort
2.6 Merge Sort
2.7 Heap Sort
2.8 Quick Sort

5
5
5
7
9
12
14
18
21

3. Análise dos testes

25

4. Conclusões

29

2

1. Introdução
1.1 Descrições do trabalho
Trabalho prático envolvendo algoritmos de ordenação. Este trabalho consiste na implementação e comparação de algoritmos de ordenação. Este trabalho contém os códigos de dois grupos de métodos de ordenação.
1.2 Métodos de Ordenação
Primeiro grupo: InsertSort, SelectionSort e BubbleSort, este grupo de métodos de ordenação tem a característica de serem de complexidade da ordem de O( ), são métodos considerado de fácil implementação. Foi usado um método sentinela nos métodos SelectionSort e no BubbleSort, método que agiliza o processo de ordenação, será explicado mais adiante.
Segundo grupo: Heap Sort, Quick Sort e Merge Sort, este grupo de métodos de ordenação tem a característica de serem de complexidade da ordem de O(n log n), são métodos mais complicados de serem implementados, todos são recursivos e tem algumas técnicas de implementação bastante complicadas. 1.3 Vetores
Foram considerados no trabalho vetores de inteiros de quantidades variadas: 10, 100, 1000, 10000, 100000, 1000000. Dados que não poderiam ter valores repetidos e foram distribuídos das seguintes maneiras: ordenados, inversamente ordenados, quase ordenados e aleatórios. Tudo para que haja maior compreensão dos métodos de ordenação e como eles funcionam.
1.4 Considerações na comparação
Na análise dos métodos foram