Quicksort na prática: o pivô, a partição e o pior caso que você evita

Um milhão de números já ordenados. A versão de quicksort que você escreveu na faculdade, com o primeiro elemento como pivô, faz cerca de 500 bilhões de comparações nesse caso. A mesma função, com o pivô sorteado, faz algumas dezenas de milhões. O algoritmo é o mesmo; a escolha do pivô decide se ele termina em menos de um segundo ou trava a requisição.

A resposta curta: o quicksort escolhe um elemento, o pivô, coloca os menores de um lado e os maiores do outro, e repete o processo em cada lado. Em média, isso custa na ordem de n log n comparações. Se o pivô cai sempre num extremo, a divisão não divide e o custo vira n². Pivô aleatório ou mediana de três evita o caso ruim na prática. Em código de produção, use o sort da biblioteca da linguagem, que já trata esses problemas.

A ideia em uma frase: separar em dois montes

Ordenar parece exigir comparar todo mundo com todo mundo. O quicksort evita isso com uma observação simples: se você sabe que todos à esquerda de um elemento são menores e todos à direita são maiores, esse elemento já está na posição final. Falta ordenar cada lado, e cada lado é um problema menor do mesmo tipo.

A operação central se chama partição. Ela percorre o trecho uma vez, compara cada elemento com o pivô e troca posições até os menores ficarem juntos no começo. No fim, o pivô vai para a fronteira. Uma passada linear, um elemento no lugar certo e dois subproblemas.

Seguindo um vetor de sete números

Pegue [7, 2, 9, 4, 1, 8, 3]. Para o exemplo ficar previsível, o pivô é o último elemento, 3. A partição usada é a de Lomuto: um índice i marca onde termina o monte dos menores.

1. i = 0. O 7 não é menor que 3; segue.
2. O 2 é menor: troca com a posição 0. Vetor: [2, 7, 9, 4, 1, 8, 3], i = 1.
3. O 9 e o 4 não são menores; seguem.
4. O 1 é menor: troca com a posição 1. Vetor: [2, 1, 9, 4, 7, 8, 3], i = 2.
5. O 8 não é menor; segue.
6. Fim da passada: o pivô troca com a posição 2. Vetor: [2, 1, 3, 4, 7, 8, 9].

O 3 está no lugar definitivo. À esquerda ficou [2, 1] e à direita [4, 7, 8, 9]. Agora repare no lado direito: ele já está ordenado. Com pivô no último elemento, o 9 é o maior, a partição deixa três elementos de um lado e nenhum do outro. Depois o 8, depois o 7. Cada passada tira só um elemento do problema. Esse é o pior caso, em miniatura.

Por que o pior caso aparece justo em dado ordenado

Quando o pivô divide o trecho mais ou menos ao meio, o tamanho do problema cai pela metade a cada nível. Com um milhão de elementos, são cerca de 20 níveis, e cada nível percorre todos os elementos uma vez: algo como 20 milhões de comparações, um pouco mais na média real.

Quando o pivô é sempre o menor ou o maior, cada nível tira um elemento só. São um milhão de níveis, percorrendo 999.999, depois 999.998, e assim por diante. A soma dá perto de n²/2, ou 500 bilhões. Além do tempo, a recursão fica com um milhão de chamadas empilhadas, o que derruba muitas linguagens com estouro de pilha.

O detalhe cruel: dado já ordenado, ou quase ordenado, é extremamente comum. Lista de pedidos por data, IDs sequenciais, resultado de uma consulta com ORDER BY. Pegar o primeiro ou o último elemento como pivô é exatamente a escolha que falha no caso mais frequente.

Uma implementação que não degrada fácil

O código abaixo, em JavaScript, faz duas coisas além do básico. Sorteia o pivô, o que torna o pior caso improvável para qualquer entrada. E chama a recursão só no lado menor, tratando o maior num laço, o que limita a profundidade da pilha a algo na ordem de log n.

function quicksort(v, ini = 0, fim = v.length - 1) {
  while (ini < fim) {
    const p = particionar(v, ini, fim);
    if (p - ini < fim - p) {
      quicksort(v, ini, p - 1);
      ini = p + 1;
    } else {
      quicksort(v, p + 1, fim);
      fim = p - 1;
    }
  }
  return v;
}

function particionar(v, ini, fim) {
  const sorteado = ini + Math.floor(Math.random() * (fim - ini + 1));
  [v[sorteado], v[fim]] = [v[fim], v[sorteado]];
  const pivo = v[fim];
  let i = ini;
  for (let j = ini; j < fim; j++) {
    if (v[j] < pivo) {
      [v[i], v[j]] = [v[j], v[i]];
      i++;
    }
  }
  [v[i], v[fim]] = [v[fim], v[i]];
  return i;
}

console.log(quicksort([7, 2, 9, 4, 1, 8, 3])); // [1, 2, 3, 4, 7, 8, 9]

Uma alternativa ao sorteio é a mediana de três: olhar o primeiro, o do meio e o último, e usar o valor do meio. Em dado ordenado, ela pega exatamente o centro. Outra fraqueza que vale conhecer: a partição de Lomuto também degrada quando há muitos valores repetidos, porque todos os iguais ao pivô caem do mesmo lado. A correção é a partição em três vias, com um monte para menores, um para iguais e um para maiores.

Como medir antes de acreditar

1. Gere três entradas do mesmo tamanho: aleatória, já ordenada e com muitos repetidos (por exemplo, só valores de 0 a 9).
2. Rode sua função em cada uma e anote o tempo com performance.now() antes e depois.
3. Rode o sort da linguagem nas mesmas entradas, sempre sobre uma cópia.
4. Compare. Se a sua versão perde, e quase sempre perde, a resposta para produção já está dada.

O que a biblioteca da linguagem já faz por você

As bibliotecas padrão raramente usam quicksort puro. O motor V8, do Chrome e do Node, usa TimSort no Array.prototype.sort, e a especificação do JavaScript exige ordenação estável desde 2019. O Python usa um algoritmo derivado do TimSort. O Java usa um quicksort de dois pivôs para arrays de tipos primitivos e TimSort para objetos. O Array.Sort do .NET e a maioria das implementações de std::sort em C++ usam introsort, que começa como quicksort e troca de estratégia se a recursão ficar funda demais.

Esses algoritmos foram ajustados por anos para dados reais, aproveitam trechos já ordenados e têm o pior caso tratado. Reescrever o sort "para ser mais rápido" sem medir é trocar código testado por um bug de desempenho esperando a entrada errada. Quando a lentidão aparece, o gargalo quase nunca é a ordenação; comece medindo, como em site mais rápido: por onde começar.

Erros comuns

• Pivô fixo no primeiro ou último elemento: em dado ordenado, o tempo vira quadrático e a recursão pode estourar a pilha.
• Recursão nos dois lados sem cuidado: no pior caso, a profundidade chega a n chamadas e o processo cai com estouro de pilha.
• Ignorar valores repetidos: com partição de duas vias, um vetor cheio de iguais degrada como se estivesse ordenado.
• Usar o sort do JavaScript sem comparador para números: o padrão compara como texto, e [10, 9, 1].sort() devolve [1, 10, 9]. Use (a, b) => a - b.
• Esperar estabilidade de um quicksort caseiro: elementos iguais podem trocar de ordem, e uma ordenação por data seguida de outra por cliente embaralha o resultado.
• Medir só com entrada aleatória: o teste passa, e a produção, que recebe dado quase ordenado, encontra o pior caso.

Checklist

• Você consegue explicar a partição seguindo um vetor pequeno no papel.
• Sua implementação de estudo não usa pivô fixo num extremo.
• A recursão é limitada, chamando no lado menor ou com outra proteção.
• Você testou com entrada ordenada, inversa e cheia de repetidos.
• Em produção, o código usa o sort da biblioteca padrão.
• Todo sort numérico em JavaScript tem comparador explícito.
• Qualquer troca de algoritmo veio acompanhada de medição antes e depois.

Procure no seu código uma ordenação escrita à mão. Se você passar para ela um vetor já ordenado de cem mil itens, o pivô ainda corta no meio, ou você acabou de achar o pior caso esperando para aparecer?