Metodos de Ordenacao

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.
Antônio Carlos de Nazaré Junior
Professor - David Menotti Gomes
Ouro Preto
14 de novembro de 2008
Sumario
1 Introdução 1
2 Métodos de Ordenação 2
2.1 Métodos de Ordenação Interna . . . . . . . . . . . . . . . . . . . . . 3
2.1.1 Implementação dos métodos . . . . . . . . . . . . . . . . . .. 3
2.2 BubbleSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 Implementação . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.2 Estudo da Complexidade . . . . . . . . . . . . . . . . . . . . . 8
2.2.3 Análise do algoritmo . . . . . . . . . . . . . . . . . . . . .. 9
2.3 InsertSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.1 Implementação . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.2 Estudo da Complexidade . . . . . . . . . . . . . . . . . . . . . 12
2.3.3 Análise do algoritmo . . . . . . . . . . . . . . . . . . . . .. 13
2.4 SelectSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4.1 Implementação . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4.2 Estudo da Complexidade . . . . . . . . . . . . . . . . . . . . . 16
2.4.3 Análise do algoritmo . . . . . . . . . . . . . . . . . . . . . . . 16
2.5 ShellSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5.1 Implementação . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5.2 Estudo da Complexidade . . . . . . . . . . . . . . . . . . . . . 20
2.5.3 Análise do algoritmo . . . . . . . . . . . . . . . . . . . . . . . 20
2.6 QuickSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.6.1 Implementação . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.6.2 Estudo da Complexidade . . . . . . . . . . . . . . . . . . . . . 23
2.6.3 Analise do algoritmo .