Métodos de ordenação e pesquisa binaria

THIAGO DE CAMARGO CEZAR

MÉTODOS DE ORDENAÇÃO E PESQUISA BINARIA

MEDIANEIRA
2009

Métodos de Ordenação

O problema da ordenação é fundamental na computação, como vimos nos métodos de pesquisa a eficiência da busca sempre é melhor quando trabalhamos com conjuntos ordenados. Genericamente a ordenação pode ser formulada como o processo em que uma seqüência qualquer de n valores é tomada como entrada e o resultado é o conjunto de também n valores onde v1`=vn` para a classificação em ordem decrescente.
Na prática os valores a serem ordenados, normalmente não estão isolados, cada valor é elemento de uma estrutura de dados do tipo registro que formam uma tabela, cada registro contém uma chave que é o valor a ser classificado e os demais valores do registro sempre acompanha a sua chave.
Usualmente quando os registros possuem muitos dados a ordenação é feita sobre uma lista de ponteiros para os registros com o objetivo de minimizar os movimentos dos dados. Esta técnica também é utilizada quando necessitamos de classificar registros por mais de uma chave. É bom lembrar que uma chave poder ser composta por um campo simples ou uma combinação de mais de um campo.
Quanto à movimentação dos dados os métodos de ordenação podem ser classificados com:
Contigüidade física - as entradas (registros) são fisicamente re-arranjadas, tomando posições diferentes na tabela.
Vetor indireto de ordenação – As entradas são mantidas nas posições originais. A classificação é dada por um vetor criado pelo processo de ordenação.
Encadeamento - As entradas são mantidas nas posições originais. É formada uma lista encadeada com a ordenação. Utiliza-se um campo extra que indica o próximo registro na seqüência da tabela. Para indicar o primeiro registro da tabela é usado um ponteiro.
Existem muitos algoritmos de ordenação, a escolha do mais eficiente vai depender de vários fatores: número de itens a ser classificado; se os valores já estão agrupados em subconjuntos ordenados; etc.