Ordenação

Algoritmos e Estruturas de Dados II Ordenação
Antonio Alfredo Ferreira Loureiro [e-mail] http://www.dcc.ufmg.br/~loureiro

UFMG/ICEx/DCC

Algoritmos e Estruturas de Dados II

1

Sumário
• Introdução: conceitos básicos • Ordenação Interna: – Seleção – Inserção – Bolha – Shellsort – Quicksort – Heapsort • Ordenação parcial: – Seleção – Inserção – Heapsort – Quicksort • Ordenação externa: – Intercalação balanceada de vários caminhos – Implementação por meio de seleção por substituição – Considerações práticas – Intercalação polifásica – Quicksort externo

UFMG/ICEx/DCC

Algoritmos e Estruturas de Dados II

2

Considerações iniciais
• Objetivos: – Apresentar os métodos de ordenação mais importantes sob o ponto de vista prático – Mostrar um conjunto amplo de algoritmos para realizar uma mesma tarefa, cada um deles com uma vantagem particular sobre os outros, dependendo da aplicação • Cada método: – ilustra o uso de estruturas de dados – mostra como a escolha da estrutura influi nos algoritmos

UFMG/ICEx/DCC

Algoritmos e Estruturas de Dados II

3

Definição e objetivos da ordenação
• Ordenar corresponde ao processo de rearranjar um conjunto de objetos em uma ordem específica. • Objetivo da ordenação: – facilitar a recuperação posterior de elementos do conjunto ordenado. • Exemplos: – Listas telefônicas – Dicionários – Índices de livros – Tabelas e arquivos

UFMG/ICEx/DCC

Algoritmos e Estruturas de Dados II

4

Observações
• Os algoritmos trabalham sobre os registros de um arquivo. • Apenas uma parte do registro, chamada chave, é utilizada para controlar a ordenação. • Além da chave podem existir outros componentes em um registro, que não têm influência no processo de ordenar, a não ser pelo fato de que permanecem com a mesma chave. • O tamanho dos outros componentes pode influenciar na escolha do método ou na forma de implementação de um dado método. • A estrutura de dados registro é a indicada para representar os