Algoritmos de ordenação

Ordenar é colocar os elementos por ordem. Parece simples, mas cada algoritmo faz escolhas muito diferentes entre velocidade, memória, estabilidade e simplicidade — é por isso que todas as disciplinas de algoritmos começam aqui.

Comparação

Algoritmo	Melhor	Médio	Pior	Memória	Estável	No local
Flutuação	n	n²	n²	1	sim	sim
Seleção	n²	n²	n²	1	não	sim
Inserção	n	n²	n²	1	sim	sim
Shell	n log n	≈ n^1.25	n^1.5	1	não	sim
Fusão	n	n log n	n log n	n	sim	não
Quicksort	n log n	n log n	n²	log n	não	sim
Heapsort	n log n	n log n	n log n	1	não	sim
Contagem	n + k	n + k	n + k	n + k	sim	não
Radix	d(n + b)	d(n + b)	d(n + b)	n + b	sim	não

Todas as complexidades são O(…). k é o intervalo de valores, d o número de dígitos, b a base (10).

Ideias principais

Ordenações por comparação (da flutuação ao heapsort) só perguntam "a é menor do que b?". Qualquer algoritmo deste tipo precisa, no pior caso, de pelo menos ${\log }_{2}n!\approx n{\log }_{2}n$ comparações: há $n!$ ordens possíveis e cada comparação, na melhor das hipóteses, divide-as ao meio. Assim, O(n log n) é o melhor possível — o merge sort e o heapsort atingem-no sempre, o quicksort em média.

A ordenação por contagem e o radix sort não comparam elementos: usam os próprios valores como índices do array. É assim que ultrapassam n log n — mas só funcionam com inteiros (ou chaves que se possam converter em inteiros).

Estabilidade — os elementos iguais mantêm a ordem original. Importa quando se ordenam registos por uma chave e depois por outra: ordene as pessoas pelo nome e depois, de forma estável, pela idade — as pessoas com a mesma idade ficam por ordem alfabética.

No local — o algoritmo precisa apenas de O(1) (ou O(log n)) de memória adicional além do array.

Qual escolher

Situação	Escolha
Uso geral, o mais rápido em média	Quicksort
Tem de ser estável ou garantir n log n	Fusão
n log n garantido com memória O(1)	Heapsort
Arrays pequenos ou quase ordenados	Inserção
Inteiros num intervalo pequeno	Contagem
Muitos inteiros com poucos dígitos	Radix
Aprender os fundamentos	Flutuação, seleção

Em código JavaScript de produção, Array.prototype.sort (TimSort, um híbrido de fusão e inserção) é normalmente a escolha certa. Esta biblioteca mostra como funcionam os algoritmos clássicos e oferece implementações fiáveis para aulas, experiências e casos especiais.

Bibliografia

• Cormen — T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, 4.ª ed., MIT Press, 2022. Capítulos 2, 6, 7, 8.
• Sedgewick — R. Sedgewick, K. Wayne. Algorithms, 4.ª ed., Addison-Wesley, 2011. Capítulo 2.
• Knuth — D. Knuth. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2.ª ed., 1998.