CP Teoria MetodosOrdenacao

CLASSIFICAÇÃO E PESQUISA

MÉTODOS DE ORDENAÇÃO

Prof. Juliana Santiago Teixeira
[e-mail]

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
 Dificuldade de se utilizar um catálogo telefônico se os nomes das pessoa não estivessem listados em ordem alfabética INTRODUÇÃO – CONCEITOS BÁSICOS
 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: typedef int tchave; struct titem { tchave chave;
//outros componentes
} ;

INTRODUÇÃO – CONCEITOS BÁSICOS
 Qualquer tipo de chave sobre o qual exista uma regra de ordenação bem-definida pode ser utilizada  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

INTRODUÇÃO – CONCEITOS BÁSICOS
 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

INTRODUÇÃO – CONCEITOS BÁSICOS
 Classificação dos métodos de ordenação:
 Ordenação interna: arquivo a ser ordenado cabe todo na memória principal
 Ordenação externa: arquivo a ser ordenado não cabe na memória principal

INTRODUÇÃO – CONCEITOS BÁSICOS
 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 ORDENAÇÃO INTERNA
 Na escolha de um algoritmo de ordenação interna deve ser considerado o tempo gasto pela ordenação
 Sendo n o número registros no arquivo, as