estudante

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

Introdução - Conceitos Básicos
• Estrutura de um registro: typedef long TipoChave; typedef struct TipoItem {
TipoChave Chave;
/∗ outros componentes ∗/
} TipoItem ;

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

3

Projeto de Algoritmos – Cap.4 Ordenação

Introdução - Conceitos Básicos
• Classificação dos métodos de ordenação:
– Interna: arquivo a ser ordenado cabe todo na memória principal.
– Externa: arquivo a ser ordenado não cabe na memória principal.
• Diferenças entre os métodos:
– Em um método de ordenação interna, qualquer registro pode ser imediatamente acessado.
– Em um método de ordenação externa, os registros são acessados seqüencialmente ou em grandes blocos.
• 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. 4

Projeto de Algoritmos – Cap.4