Introdução
Comecei a escrever a primeira versão deste texto em inglês, em 2000, mas nunca cheguei a concluir. Para quem tiver curiosidade, aqui está a versão do texto que encostei em 2002.
Ordenar coisas é uma tarefa comum na programação. É também um daqueles tipos de tarefas onde o algorítmo utilizado faz uma grande diferença. Os exemplos que vão acompanhar esta série, além de conterem implementações dos algorítmos descritos, vai ajudar a ver como eles funcionam e comparar o desempenho deles.
Ordenação também é o tipo de tarefa que clama por uma boa análise matemática. Você não vai encontrar isto aqui! A "bíblia" da ordenação, na minha opinião, é o livro "The Art of Computer Programming, Vol 3 - Sorting and Searching" de Donald E. Knuth. Foi com este livro que aprendi o que apresento aqui. Alguns podem achar o estilo do Dr Knuth ultrapassado (implicando com os exemplos em linguagem assembler de um computador hipotético), mas dificilmente se acha um texto tão completo como o dele.
Por último, muitas linguagens possuem em sua biblioteca padrão funções genéricas de ordenação e muitos preferem simplesmente as usar sem conhecer como funcionam. Como veremos, existem vários pontos interessantes sobre a ordenação e nem sempre a escolha de um algorítmo é simples. Mesmo que você nunca precise escrever a sua própria função de ordenação, muito pode ser aprendido estudando estes algorítmos.
O Que é Ordenar?
Basicamente, estamos falando em colocar coisas em uma certa ordem. Nós temos itens (ou registros) a serem ordenados. Cada item está associado a uma uma chave. Nosso objetivo é re-arranjar os itens de forma que eles fiquem em ordem crescente (ou decrescente) de chave.
Nesta série vamos nos concentrar em ordenar um vetor de chaves numéricas (inteiras) que estão na memória. As idéias apresentadas podem ser facilmente expandidas:
- Podemos usar os mesmos algorítimos com qualquer tipo de chaves. Tudo que precisamos é uma forma de comparar as chaves e uma maneira de movê-las. Por exemplo, podemos ter chaves alfanuméricas e ordená-las sem considerando maiúsculas e minúsculas como equivalentes (de forma que 'aBc' seja igual a 'AbC' ou 'ABC')
- Podemos ter múltiplas chaves. Se as primeiras chaves são iguais, nós comparamos as segundas e assim por diante até acharmos uma diferença ou testarmos todas as chaves. Se as chaves forem alfanuméricas, podemos fazer isto simplesmente as concatenando. Se misturarmos chaves de tipo diferente, nossa comparação pode usar o operador && do C (ou construção equivalente de outra linguagem) para testar as chaves na ordem correta.
- Ao mesmo tempo em que ordenamos as chaves, ordenamos os registros. Se os registros forem pequenos, simplesmente os movemos junto com as chaves. Se os registros forem grandes, nós guardamos ponteiros para os registros junto com as chaves. Durante a ordenação, movemos junto as chaves e os ponteiros. Ao final seguimos os ponteiros para obter os registros na ordem certa (veja Figura 1).
- Se as chaves não cabem na memória, fazemos a ordenação por partes, gravando as partes em arquivos temporários. Ao final fazemos um merge das partes (ver Figura 2).
Figura 1 - Usando ponteiros para não mover os registros
Figura 2 - Dividindo o arquivo em partes, ordenando e fazendo o merge
Nenhum comentário:
Postar um comentário