Ordenação sem Comparações

O limite inferior Ω(n log n) aplica-se aos algoritmos que descobrem a ordem apenas por comparações. Conhecimento adicional sobre a estrutura das chaves permite outras abordagens.

Counting sort

Para chaves inteiras em um intervalo conhecido de tamanho k, conte as ocorrências e reconstrua a ordem. O tempo é Θ(n + k), e o espaço auxiliar é Θ(k) ou Θ(n + k) para uma versão estável que produz outra saída. Essa opção é pouco atraente quando o intervalo é enorme em relação à entrada.

Radix sort

O Radix sort processa as chaves dígito a dígito usando uma subordenação estável. Com d dígitos e base k, um limite convencional é Θ(d(n + k)). A correção do Radix sort de dígito menos significativo depende da estabilidade de cada passagem por dígito.

Bucket sort

O Bucket sort distribui valores em intervalos, ordena dentro dos buckets e os concatena. O desempenho esperado depende da distribuição de entrada declarada; uma distribuição ruim pode concentrar a maioria dos elementos em um único bucket.

Use esses métodos apenas quando as premissas sobre o domínio e os custos de memória estiverem explícitos.

Exercícios

1. Escreva um Counting sort estável que preserve os registros associados.
2. Explique por que uma ordenação instável por dígito pode invalidar o Radix sort LSD.
3. Compare Counting sort e QuickSort quando k for muito maior que n.