Métodos de Ordenação

∗
Ordenação

Última alteração: 26 de Março de 2004

∗ Transparências

elaboradas por Fabiano C. Botelho e Nivio Ziviani

Projeto de Algoritmos – Cap.4 Ordenação

Ordenação
• Introdução - Conceitos Básicos
• Ordenação Interna
– Ordenação por Seleção
– Ordenação por Inserção
– Shellsort
– Quicksort
– Heapsort
– Ordenação Parcial
∗ Seleção Parcial
∗ Inserção Parcial
∗ Heapsort Parcial
∗ Quicksort Parcial
• 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

1

Projeto de Algoritmos – Cap.4 Ordenação

Introdução - Conceitos Básicos
• Ordenar: processo de rearranjar um conjunto de objetos em uma ordem ascendente ou descendente. • A ordenação visa facilitar a recuperação posterior de itens do conjunto ordenado.
– Dificuldade de se utilizar um catálogo telefônico se os nomes das pessoas não estivessem listados em ordem alfabética.
• Notação utilizada nos algoritmos:
– Os algoritmos trabalham sobre os registros de um arquivo.
– Cada registro possui uma chave utilizada para controlar a ordenação.
– Podem existir outros componentes em um registro. 2

Projeto de Algoritmos – Cap.4 Ordenação

3

Introdução - Conceitos Básicos
• Estrutura de um registro: type Item = record
Chave: ChaveTipo;
{ outros componentes } end; • Qualquer tipo de chave sobre o qual exista uma regra de ordenação bem-definida pode ser utilizado.
• Um método de ordenação é estável se a ordem relativa dos itens com chaves iguais não se altera durante a ordenação.
• Alguns dos métodos de ordenação mais eficientes não são estáveis.
• A estabilidade pode ser forçada quando o método é não-estável.
• Sedgewick (1988) sugere agregar um pequeno índice a cada chave antes de ordenar, ou então aumentar a chave de alguma outra forma.

Projeto de Algoritmos – Cap.4 Ordenação

Introdução - Conceitos