Documents

Projeto de Algoritmos – Cap.4 Ordenação

1

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
Última alteração: 26 de Março de 2004

Ordenação∗

– 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

∗ Transparências

elaboradas por Fabiano C. Botelho e Nivio Ziviani

– Quicksort Externo

Projeto de Algoritmos – Cap.4 Ordenação

2

Projeto de Algoritmos – Cap.4 Ordenação

3

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.

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

4

Projeto de Algoritmos – Cap.4 Ordenação

5

Introdução - Conceitos