Artigo · 14 de março de 2026 · 1 min

Uma Nota sobre Particionamento em Quicksort

Eduardo Kohn · Pesquisador independente

Abstract. Revisitamos o esquema de particionamento de Hoare e o comparamos ao de Lomuto sob distribuições variadas de entrada, estabelecendo limites justos para o número de comparações observadas na prática.

O particionamento é a operação central do quicksort. Existem dois esquemas clássicos: o de Hoare [1] e o de Lomuto. A análise do caso esperado do algoritmo como um todo é de Sedgewick [2].

Dado um arranjo $a[\ell..r]$ e um pivô $p$ , o particionamento reorganiza os valores de modo que todo elemento à esquerda de algum índice $k$ satisfaça $a[i] \le a[k]$ e todo elemento à direita satisfaça $a[j] \ge a[k]$ .

1.1 Definition: Função de partição

Uma função partition(a, lo, hi) reorganiza $a[\ell..r]$ de modo que exista um índice $k \in [\ell, r]$ onde $a[i] \le a[k]$ para $i < k$ e $a[j] \ge a[k]$ para $j > k$ , e retorna $k$ .

2.1 Theorem: Limite de comparações de Hoare

Para qualquer arranjo de tamanho $n \ge 2$ , o particionamento de Hoare executa no máximo $\lceil 3n/4 \rceil$ comparações no pior caso.

Proof of Teorema 2.1

Os ponteiros esquerdo e direito avançam de forma monotônica e se encontram em $O(n)$ passos. Um argumento de contagem justo mostra que o total de comparações é limitado por $3n/4$ no pior caso, atingido quando o pivô cai próximo de um quarto do arranjo.

A implementação a seguir em TypeScript espelha o esquema original de Hoare, com dois ponteiros convergindo e swap() trocando elementos fora de lugar:

// Partição estilo Hoare
function partition(arr: number[], lo: number, hi: number): number {
  const pivot = arr[lo];
  let i = lo - 1;
  let j = hi + 1;
  while (true) {
    do {
      i++;
    } while (arr[i] < pivot);
    do {
      j--;
    } while (arr[j] > pivot);
    if (i >= j) return j;
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

Chamar partition(arr, lo, hi) retorna o índice de separação. Um pivô desbalanceado degrada o quicksort para $\Theta(n^2)$ ; escolher o pivô aleatoriamente restaura a expectativa $\Theta(n \log n)$ .

[1]

C. A. R. Hoare, “Algorithm 64: Quicksort,” Communications of the ACM, vol. 5, no. 7, p. 322, 1962, doi: 10.1145/366622.366644.

[2]

R. Sedgewick, “The Analysis of Quicksort Programs,” Acta Informatica, vol. 7, no. 4, pp. 327–355, 1977.