Algoritmo

∗ Ordenação

Última alteração: 10 de Outubro de 2006

elaboradas por Fabiano C. Botelho, Leonardo Rocha, Leonardo Mata e Nivio Ziviani

∗ Transparências

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

Projeto de Algoritmos – Cap.4 Ordenação

2

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. • A maioria dos métodos de ordenação é baseada em comparações das chaves. • Existem métodos de ordenação que utilizam o princípio da distribuição.

Projeto de Algoritmos – Cap.4 Ordenação

3

Introdução - Conceitos Básicos
• Exemplo de ordenação por distribuição: considere o problema de ordenar um baralho com 52 cartas na ordem: A < 2 < 3 < · · · < 10 < J < Q < K e ♣ < ♦ < ♥ < ♠. • Algoritmo: 1. Distribuir as cartas abertas em treze montes: ases, dois, três, . . ., reis. 2. Colete os montes na ordem especificada. 3. Distribua novamente as cartas abertas em quatro montes: paus, ouros, copas e espadas. 4. Colete os montes na ordem especificada.

Projeto de Algoritmos – Cap.4 Ordenação

4

Introdução - Conceitos Básicos
• Métodos como o ilustrado são também conhecidos como ordenação digital, radixsort ou bucketsort. • O método não utiliza comparação entre chaves. • Uma das dificuldades de implementar este método está relacionada com o problema de