Cap4
12754 palavras
52 páginas
OrdenaçãoLivro “Projeto de Algoritmos” – Nívio Ziviani
Capítulo 4 http://www2.dcc.ufmg.br/livros/algoritmos/ Ordenação
Introdução – Conceitos Básicos
Ordenação Interna
Ordenação ç por p Seleção ç
Ordenação por Inserção
ShellSort
QuickSort
HeapSort
MergeSort
Ordenação Digital
Ordenação Parcial
Algoritmos e Estrutura de Dados II
Ordenação
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
Q i k t Externo
Quicksort
E t
Algoritmos e Estrutura de Dados II
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.
Algoritmos e Estrutura de Dados II
Introdução – Conceitos Básicos
Notação utilizada nos algoritmos:
Os algoritmos
O
l it ttrabalham b lh sobre b os registros i t d de um arquivo. Cada registro possui uma chave utilizada para controlar a ordenação.
Podem existir outros componentes em um registro. Algoritmos e Estrutura de Dados II
Introdução – Conceitos Básicos
Estrutura de um registro: typedef int ChaveTipo; typedef struct Item {
Ch
ChaveTipo
Ti
Ch
Chave;
/* outros componentes */
} Item;
Qualquer tipo de chave sobre o qual exista uma regra de ordenação bem-definida pode ser utilizado.
Algoritmos e Estrutura de Dados II
Introdução – Conceitos Básicos
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