Algoritmos de ordenação comparados
Não existe um único algoritmo de ordenação mais rápido. Alguns são simples mas lentos, outros são rápidos com dados aleatórios mas tropeçam em dados ordenados, e alguns nem sequer ordenam por comparação. Pôr os oito a competir na mesma lista mostra as diferenças num relance.
Três famílias
O bubble sort, a ordenação por seleção e a ordenação por inserção são os algoritmos simples. Comparam e trocam valores próximos e precisam de tempo proporcional a n² numa lista aleatória. O merge sort, o quicksort e a ordenação por heap dividem o trabalho de forma inteligente e precisam de tempo proporcional a n log n, o melhor que um algoritmo consegue quando só pode perguntar qual de dois valores é maior. A ordenação radix e a ordenação por contagem dispensam essa pergunta por completo: usam os próprios dígitos ou valores, o que só funciona com chaves como números inteiros pequenos.
Medir o trabalho
A Corrida de ordenações conta uma operação por cada comparação, cada dígito ou valor lido e cada troca ou movimento. Com 40 valores aleatórios, isso dá cerca de 120 para a ordenação por contagem, 240 para a ordenação radix, 260 para o quicksort, 380 para o merge sort, 490 para a ordenação por heap, cerca de 820 cada para a ordenação por seleção e por inserção, e mais de 1100 para o bubble sort. Os computadores reais também dependem da memória: na prática, o quicksort costuma ser mais rápido do que a contagem sugere, e a ordenação por heap mais lenta, pela forma como percorrem a lista.
Os dados de entrada contam
Numa lista quase ordenada, a ordenação por inserção precisa só de cerca de 50 operações para 40 valores e o bubble sort de cerca de 90, porque cada valor está perto do seu lugar. Numa lista invertida, os mesmos dois precisam de 1560, o seu pior caso. Para a ordenação por seleção, a ordenação por heap, o merge sort, a ordenação radix e a ordenação por contagem, a ordem quase não importa. O quicksort com a mediana de três lida bem com listas ordenadas e invertidas, mas com um pivô ingénuo uma lista ordenada é o seu pior caso. Poucos valores distintos tornam o quicksort mais lento, porque os valores iguais vão todos para o mesmo lado.
Memória e estabilidade
O bubble sort, a ordenação por seleção, a ordenação por inserção, o quicksort e a ordenação por heap funcionam in-place, com pouca ou nenhuma memória extra. O merge sort, a ordenação radix e a ordenação por contagem precisam de um buffer do tamanho da lista. Uma ordenação estável mantém os valores iguais na ordem original: o bubble sort, a ordenação por inserção, o merge sort, a ordenação radix e a ordenação por contagem são estáveis, enquanto a ordenação por seleção, o quicksort e a ordenação por heap não são. A estabilidade importa quando ordena registos por um campo e depois por outro.
Qual usar
Na prática, usa a ordenação incluída na sua linguagem de programação: normalmente Timsort, um merge sort que usa a ordenação por inserção nos troços curtos e é rápido com dados parcialmente ordenados, ou introsort, um quicksort que recorre à ordenação por heap e usa a ordenação por inserção nas partes pequenas. Com muitas chaves inteiras pequenas, a ordenação por contagem ou a ordenação radix podem bater ambos. O bubble sort e a ordenação por seleção servem sobretudo para aprender.
Experimente
Abra a Corrida de ordenações e prima Reproduzir. Cada pista é um algoritmo na mesma lista; o número à direita conta as suas operações, e uma pista fica verde quando termina. Experimente uma lista quase ordenada, uma invertida e poucos valores distintos, e veja a ordem de chegada mudar. Cada algoritmo tem também a sua própria app, onde o pode seguir passo a passo.
Perguntas frequentes
Qual é o algoritmo de ordenação mais rápido?
Para dados gerais, o quicksort e o merge sort (e os híbridos baseados neles, como introsort e Timsort) são os mais rápidos em média, com n log n. Para chaves inteiras pequenas, a ordenação por contagem e a ordenação radix são ainda mais rápidas. Para listas curtas ou quase ordenadas, ganha a ordenação por inserção.
Porque é que nenhuma ordenação por comparação consegue bater n log n?
Uma lista de n valores pode estar em n! ordens, e cada comparação tem dois resultados, por isso são precisas pelo menos log₂(n!) comparações para as distinguir todas no pior caso. Isso dá cerca de n log₂ n. A ordenação radix e a ordenação por contagem evitam este limite porque não comparam.
Que algoritmos de ordenação são estáveis?
O bubble sort, a ordenação por inserção, o merge sort, a ordenação radix e a ordenação por contagem são estáveis nas suas formas habituais. A ordenação por seleção, o quicksort e a ordenação por heap não são, porque movem valores a grandes distâncias.
Que algoritmos precisam de memória extra?
O merge sort, a ordenação radix e a ordenação por contagem precisam de um buffer quase do tamanho da lista. O bubble sort, a ordenação por seleção, a ordenação por inserção e a ordenação por heap quase não precisam, e o quicksort só um pouco para a recursão.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Começar a Corrida de ordenações