Entendendo o Quicksort com Exemplos em JavaScript

Quicksort é um algoritmo de ordenação do tipo divisão e conquista: ele escolhe um elemento pivô, particiona o array de modo que os elementos menores fiquem à esquerda e os maiores à direita, e então ordena recursivamente cada lado no próprio array (in place).

A maioria de nós o encontra pela primeira vez em frente a um quadro branco, com alguém observando, e é justamente no laço de particionamento que a confiança costuma se esvair. Ele roda em tempo O(n log n) em média, ordena sem alocar um segundo array e é o algoritmo que a maioria dos entrevistadores escolhe quando pede para você “ordenar isso na mão”.

Este artigo cobre três coisas: uma versão legível para construir intuição, um rastreamento manual de uma passagem de particionamento para que você veja os elementos se movendo, e a implementação in-place que você realmente escreveria em uma entrevista, além de notas sobre complexidade, escolha do pivô e estabilidade.

Como funciona o algoritmo quicksort?

O quicksort ordena dividindo repetidamente o array em torno de um pivô escolhido. Uma passagem de particionamento reorganiza os elementos de modo que tudo o que é menor que o pivô fique antes dele e tudo o que é maior fique depois; o pivô então está em sua posição final ordenada. Aplique o mesmo passo às sub-faixas da esquerda e da direita, e o array inteiro se ordena.

Ele compartilha a estrutura de divisão e conquista do merge sort, mas os trade-offs são diferentes. Tanto o quicksort quanto o merge sort têm média O(n log n), mas o quicksort ordena in place com O(log n) de espaço auxiliar, enquanto o merge sort precisa de O(n) de espaço extra, e o merge sort é estável, enquanto o quicksort não é. O quicksort troca essa estabilidade garantida por menor consumo de memória e forte velocidade no mundo real.

Primeiro, a versão legível (filter e spread)

O quicksort mais fácil de ler particiona com filter e reconstrói o array com o operador spread. É a forma mais rápida de compreender a recursão e é uma boa ferramenta didática, mas aloca novos arrays em cada chamada, portanto não é verdadeiramente in-place e usa memória extra.

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const [pivot, ...rest] = arr;
  const left = rest.filter((x) => x < pivot);
  const right = rest.filter((x) => x >= pivot);

  return [...quickSort(left), pivot, ...quickSort(right)];
}

quickSort([3, 7, 2, 5, 1, 4, 6, 8]); // [1, 2, 3, 4, 5, 6, 7, 8]

O caso base (length <= 1) interrompe a recursão, já que um array com zero ou um elemento já está ordenado. Cada chamada constrói três novos arrays, então o uso de memória desta versão cresce com a entrada em vez de permanecer constante. Recorra a ela para explicar a ideia; recorra à versão in-place abaixo quando memória ou expectativas de entrevista importarem.

Como funciona o particionamento?

O particionamento é o motor do quicksort, então vale a pena observar uma passagem de perto. O esquema de Lomuto toma o último elemento como pivô, percorre a faixa com um índice de varredura j e mantém um índice de fronteira i marcando onde o próximo elemento “menor que o pivô” pertence. Cada vez que arr[j] é menor que o pivô, ele troca arr[i] e arr[j] e avança i. No final, ele troca o pivô para a posição i.

Rastreie [7, 2, 1, 8, 6, 3, 5, 4] com pivô 4 (o último elemento), começando com i = 0:

O pivô 4 acaba no índice 3, com [2,1,3] à sua esquerda e [6,7,5,8] à sua direita. Nenhum dos lados está ordenado ainda, mas o pivô está permanentemente posicionado, e os dois lados agora são subproblemas independentes.

function partition(arr, lo, hi) {
  const pivot = arr[hi];          // last element as pivot
  let i = lo;                     // boundary for elements < pivot
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]]; // move pivot into place
  return i;
}

O quicksort in-place que você escreveria em uma entrevista

O quicksort em formato de produção mantém o helper de particionamento acima e recorre sobre faixas de índices (lo, hi) em vez de construir novos arrays. Esta é a versão a que recorrer quando alguém pedir que você implemente o quicksort: ela muta um único array e usa apenas a pilha de recursão como espaço extra.

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo < hi) {
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
  }
  return arr;
}

quickSort([7, 2, 1, 8, 6, 3, 5, 4]); // [1, 2, 3, 4, 5, 6, 7, 8]

Cada chamada particiona sua faixa e então recorre sobre as duas sub-faixas ao redor do pivô. A guarda lo < hi é o caso base: uma faixa de zero ou um elemento já está ordenada. Se a recursão estiver fora de questão (uma pergunta de acompanhamento comum em entrevistas), a mesma lógica se converte em uma versão iterativa empilhando pares lo/hi em uma pilha explícita em vez da pilha de chamadas.

Complexidade, escolha do pivô e estabilidade

O custo do quicksort é decidido quase inteiramente pelo pivô. Com divisões equilibradas, cada nível de recursão toca cada elemento uma vez ao longo de aproximadamente log n níveis, resultando em O(n log n). Quando as divisões são consistentemente desbalanceadas, a profundidade da recursão cresce para n e o custo degrada para O(n²). In place, a pilha de recursão responde por O(log n) de espaço em entradas equilibradas.

A armadilha clássica: escolher o primeiro ou o último elemento como pivô faz o quicksort atingir seu pior caso O(n²) em entradas já ordenadas, porque cada particionamento descasca apenas um elemento. Você evita o pior caso de entrada ordenada escolhendo o elemento do meio, usando a mediana de três ou escolhendo um pivô aleatório. A mediana de três ordena o primeiro, o do meio e o último elemento e usa a mediana, o que resiste tanto a entradas adversárias ordenadas quanto ordenadas de forma inversa:

function medianOfThree(arr, lo, hi) {
  const mid = Math.floor((lo + hi) / 2);
  if (arr[mid] < arr[lo]) [arr[lo], arr[mid]] = [arr[mid], arr[lo]];
  if (arr[hi]  < arr[lo]) [arr[lo], arr[hi]]  = [arr[hi], arr[lo]];
  if (arr[hi]  < arr[mid]) [arr[mid], arr[hi]] = [arr[hi], arr[mid]];
  // median now sits at mid; move it to hi so Lomuto uses it as the pivot
  [arr[mid], arr[hi]] = [arr[hi], arr[mid]];
  return arr[hi];
}

Uma propriedade que nenhuma estratégia de pivô recupera: o quicksort não é uma ordenação estável, portanto elementos iguais podem ser reordenados em relação às suas posições originais. Isso importa quando você ordena registros por uma chave secundária e espera que a ordenação primária sobreviva.

O sort nativo do JavaScript é quicksort?

Não. Embora o algoritmo quicksort seja instável, o Array.prototype.sort nativo do JavaScript tem estabilidade garantida desde o ES2019, a décima edição do padrão da linguagem. O V8 ordena arrays com Timsort desde a v7.0 e o Chrome 70: um merge sort que aproveita sequências de dados já ordenados e mantém elementos iguais na ordem em que os encontrou. Todos os outros grandes engines estão sujeitos ao mesmo requisito de estabilidade imposto pela especificação. Portanto, “o quicksort é instável” descreve o algoritmo, não o sort nativo em qualquer navegador moderno.

O quicksort conquista sua reputação por um laço de particionamento enxuto, operação in-place e velocidade média O(n log n), desde que você mantenha o pivô longe das extremidades do array. Implemente a versão in-place acima com mediana de três ou um pivô aleatório, execute-a contra uma entrada ordenada para confirmar que ela não explode, e você será capaz tanto de escrever o quicksort quanto de explicar seus trade-offs sob demanda.

Perguntas Frequentes

Quando devo usar quicksort em vez de merge sort?

Use quicksort quando a memória for limitada e você quiser ordenar in place, já que ele precisa apenas de O(log n) de espaço auxiliar para a pilha de recursão, contra o array extra de O(n) do merge sort. Ambos têm média O(n log n), mas o quicksort é mais rápido na prática em dados típicos. Escolha o merge sort quando você precisar de estabilidade garantida ou de um pior caso O(n log n) garantido, pois o quicksort pode degradar para O(n ao quadrado).

Por que o quicksort atinge O(n ao quadrado) em um array já ordenado?

Um pivô fixo no primeiro ou no último elemento degrada para O(n ao quadrado) em entradas ordenadas porque cada particionamento coloca o pivô em uma das extremidades e produz uma sub-faixa vazia e uma faixa de n menos 1 elementos. Isso gera n níveis de recursão em vez de log n, cada um realizando trabalho linear. A correção é escolher o elemento do meio, usar a mediana de três ou escolher um pivô aleatório, todos restaurando divisões equilibradas em dados ordenados.

O Array.prototype.sort do JavaScript é implementado com quicksort?

Não. Os engines modernos não usam quicksort para o sort nativo. O V8 usa Timsort desde a v7.0 e o Chrome 70, um merge sort que explora sequências de dados já ordenados e preserva a ordem de elementos iguais. Desde o ES2019, a especificação ECMAScript exige que o Array.prototype.sort seja estável, e todos os principais engines entregam uma ordenação estável. Portanto, o algoritmo quicksort é instável, mas o sort nativo não é quicksort e tem estabilidade garantida.

Qual é a diferença entre os esquemas de particionamento de Lomuto e de Hoare?

Lomuto usa um único índice de varredura e normalmente toma o último elemento como pivô, trocando elementos menores em direção a um índice de fronteira; é mais simples de escrever e rastrear. Hoare usa dois ponteiros que se movem para dentro a partir das duas extremidades e geralmente realiza menos trocas, tornando-o mais rápido na prática. Ambos particionam in place e retornam um ponto de divisão, mas o índice retornado por Hoare não coloca o pivô em sua posição final como o de Lomuto faz.

Como converto o quicksort recursivo em uma versão iterativa?

Substitua a pilha de chamadas por uma pilha explícita de faixas de índices. Empilhe o par inicial lo e hi, depois itere enquanto a pilha não estiver vazia: retire uma faixa, particione-a para obter um índice de pivô p e empilhe de volta as duas sub-faixas de lo até p menos 1 e de p mais 1 até hi quando contiverem mais de um elemento. Isso produz o mesmo resultado evitando a recursão, uma pergunta de acompanhamento comum em entrevistas.