Ordenação


Introdução

De modo geral, podemos definir o problema de ordenação como:

Cada registro mencionado na definição acima possui uma chave, que governa o processo de ordenação. Dados adicionais, além da chave, podem estar presentes, mas não têm efeito na ordenação, exceto que eles devem ser carregados (movidos) como parte do registro. Entretanto, no nosso caso, para simplificar as explicações, os registros serão números inteiros, ou seja, cada registro é composto unicamente da chave. Além disso, sempre ordenaremos os registros em ordem crescente (novamente, para simplificar as explicações). Assim, podemos definir novamente o problema como abaixo:

Neste capítulo, aprenderemos diversos algoritmos para resolver o problema de se ordenar um vetor de números. Como você verá, os algoritmos de ordenação ilustram vários conceitos importantes em Ciência da Computação, e usam vários paradigmas (estratégias) de projeto de algoritmos que nos ajudarão a entender muitos outros algoritmos. Além disso, conhecer bem os diversos algoritmos de ordenação fará com que você seja capaz de decidir qual algoritmo é melhor para uma dada tarefa, o que nem sempre é algo trivial de se decidir. Portanto, é importante que você entenda bem o funcionamento dos algoritmos e as estratégias que cada um deles usa para resolver o problema de ordenação.

Como veremos adiante, a eficiência (sua complexidade assintótica) de um algoritmo de ordenação é determinada em termos de dois fatores:

Para cada um dos algoritmos de ordenação explicados, além de discutir seu funcionamento, responderemos também algumas perguntas importantes:

  1. Qual é a complexidade assintótica do algoritmo no pior caso? Em algumas situações discutiremos também o caso médio de alguns algoritmos.
  2. O algoritmo é in-place? Um algoritmo de ordenação in-place é um algoritmo que ordena o vetor de entrada sem usar um vetor auxiliar.
  3. O algoritmo é estável? Um algoritmo de ordenação é estável se dois objetos com chaves idênticas aparecem na mesma ordem no vetor ordenado em que eles apareciam no vetor de entrada. Em outras palavras, algoritmos de ordenação estáveis preservam a ordem relativa entre elementos com chaves iguais.

Um algoritmo ideal de ordenação deveria ter as seguintes propriedades:

Entretanto, nenhum algoritmo de ordenação possui todas essas propriedades. A melhor escolha de algoritmo de ordenação depende do contexto de uso do algoritmo. Portanto, é importante conhecer bem os algoritmos e saber em quais situações cada um deles é melhor.