Aeds2 ORDENACAO 1pp

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 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

• Ordenação parcial:
– Seleção
– Inserção
– Heapsort
– Quicksort

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 elementos a serem ordenados.