Corrida de Algoritmos de Ordenação

O bubble sort faz exatamente n(n−1)/2 comparações no pior caso — cerca de 2.000 para n=64. Cada passagem precisa varrer toda a região restante não ordenada, sem saída antecipada. A partição do quicksort coloca o pivô em sua posição final e divide o problema em dois subproblemas; cada nível de recursão realiza trabalho O(n) ao longo de O(log n) níveis, totalizando O(n log n). A pegadinha: se o pivô sempre cai em uma extremidade — por exemplo, entrada ordenada com o último elemento como pivô — a partição degenera em n subproblemas de tamanho n−1, n−2, ... somando O(n²). O pivô do elemento central usado aqui evita isso, motivo pelo qual a entrada invertida permanece rápida. Valores com poucos elementos únicos são o caso interessante: quando muitos elementos são iguais ao pivô, trocar valores idênticos desperdiça trabalho e pode empurrar em direção ao comportamento quadrático. O Big-O indica a classe de crescimento; as constantes, a sensibilidade à entrada e o comportamento do cache determinam qual algoritmo você realmente deve usar.

Esta corrida pontua cada algoritmo contando comparações e trocas, não com um cronômetro. O tempo real depende da sua CPU, do navegador e do que mais estiver rodando, então o mesmo código pode parecer rápido ou lento em máquinas diferentes. Contar operações dá uma medida limpa e reproduzível do trabalho de fato realizado: a mesma entrada sempre produz as mesmas contagens, permitindo comparar os algoritmos em si, e não o hardware.

Tony Hoare inventou o Quicksort em 1959, como estudante visitante em Moscou, enquanto trabalhava num projeto de tradução automática. Para procurar uma frase russa no dicionário, precisava antes ordenar suas palavras em ordem alfabética — e o método usual era desesperadamente lento. Sua solução, particionar em torno de um pivô, tornou-se um dos algoritmos mais usados de todos os tempos. As barras que disputam aqui vêm de um problema de linguagem, não de computação.