Ordenação De Dados

Ordenar indica o processo de rearranjar um conjunto de objetos ou informações em uma ordem ascendente ou descendente. A atividade de colocar as coisas em ordem está presente na maioria das aplicações em que os objetos e informações armazenados precisam ser pesquisados e recuperados.

O objetivo principal da ordenação é facilitar a recuperação posterior de itens do conjunto ordenado. Imagine como seria difícil utilizar um catálogo telefônico se os nomes das pessoas não estivessem listados em ordem alfabética. O mesmo pode ser dito com relação a dicionários, índices de livros, folhas de pagamento, contas bancárias, tabelas, arquivos e outros materiais organizados alfabeticamente, portanto, evidencia-se que a conveniência de usar dados ordenados é inquestionável.

Os tipos de ordenação mais usados conhecidos são: Ordenação por troca, Ordenação por inserção, Ordenação por seleção, entre outros.

Em ordenação por troca existem os algoritmos: BubbleSort (método da bolha) e QuickSort (método da troca e partição); Na ordenação por inserção, existem os algoritmos: InsertionSort (método da inserção direta) e BinaryInsertionSort (método da inserção direta binária); Na ordenação por seleção, os algoritmos são: SelectionSort (método da seleção direta) e HeapSort (método da seleção em árvore). Existem ouros métodos como o : MergeSort (método da intercalação) e o BucketSort (método da distribuição de chave).

Cada um desses algoritmos faz a ordenação de maneiras diferentes, possuindo suas vantagens e desvantagens as quais devem ser consideradas conforme a aplicação que se destinam. Para decidir que método é o melhor, certos critérios de eficiência têm que ser estabelecidos, e um método para comparar diferentes algoritmos precisa ser selecionado.

Para tornar a comparação independente da máquina, certas propriedades críticas dos algoritmos de ordenação precisam ser definidas quando comparados, como o número de comparações e o número de movimentos de dados. Para ordenar um conjunto de dados, eles têm que ser comparados e movidos conforme necessário; a eficiência dessas duas operações depende do tamanho do conjunto de dados.

Os métodos de ordenação são classificados através de sua complexidade (O) e são em geral, classificados em dois grandes grupos: métodos de ordenação interna (vetores) e métodos de ordenação externa (arquivos). Se o arquivo a ser ordenado é pequeno, ou seja, cabe todo na memória principal então o método ordenador é chamado de ordenação interna. Em um método de ordenação interna, qualquer registro pode ser imediatamente acessado. Se o arquivo a ser ordenado não cabe na memória principal e por isso tem de ser armazenado em fita ou disco, então o método de ordenação é chamado de ordenação externa. Em um método de ordenação externa, os registros são acessados seqüencialmente ou em grandes blocos.

Existem os métodos simples, que são ideais para conjuntos pequenos, requerem O(n2) comparações, produzem programas pequenos e fáceis de entender; e existem métodos eficientes que são adequados para conjuntos maiores, requerem O(n log n) comparações, usam menos comparações e essas comparações são mais complexas nos detalhes.

A proposta deste trabalho consiste justamente em estudar com maior profundidade