Metodos de odenação

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

ALGORITMOS E ESTRUTURAS DE DADOS
Métodos de ordenação Interna.

Antonio Carlos de Nazaré Júnior
Professor - David Menotti Gomes

Ouro Preto
14 de novembro de 2008

Sumário
1 Introdução

1

2 Métodos de Ordenação
2.1 Métodos de Ordenação Interna . .
2.1.1 Implementação dos métodos
2.2 BubbleSort . . . . . . . . . . . . .
2.2.1 Implementação . . . . . . .
2.2.2 Estudo da Complexidade . .
2.2.3 Análise do algoritmo . . . .
2.3 InsertSort . . . . . . . . . . . . . .
2.3.1 Implementação . . . . . . .
2.3.2 Estudo da Complexidade . .
2.3.3 Análise do algoritmo . . . .
2.4 SelectSort . . . . . . . . . . . . . .
2.4.1 Implementação . . . . . . .
2.4.2 Estudo da Complexidade . .
2.4.3 Análise do algoritmo . . . .
2.5 ShellSort . . . . . . . . . . . . . . .
2.5.1 Implementação . . . . . . .
2.5.2 Estudo da Complexidade . .
2.5.3 Análise do algoritmo . . . .
2.6 QuickSort . . . . . . . . . . . . . .
2.6.1 Implementação . . . . . . .
2.6.2 Estudo da Complexidade . .
2.6.3 Análise do algoritmo . . . .
2.7 HeapSort . . . . . . . . . . . . . . .
2.7.1 Implementação . . . . . . .
2.7.2 Estudo da Complexidade . .
2.7.3 Análise do algoritmo . . . .
2.8 MergeSort . . . . . . . . . . . . . .
2.8.1 Implementação . . . . . . .
2.8.2 Estudo da Complexidade . .
2.8.3 Análise do algoritmo . . . .

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

2
3
3
6
7
8
9
10
11
12
13
14
15
16
16
18
19
20
20
21
21
23
24
25
27
28
28
29
30
31
31

3 Testes
3.1 Metodologia dos Testes . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Vetor ordenado em ordem crescente . . . . . . . . . . . . . . .

32
32
33
34

2

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