Algoritmo Quick Sort: Particionamento In-Place e Performance Extrema

1. A Filosofia do Quick Sort de Tony Hoare

Em 1961, o cientista britânico Sir Tony Hoare desenvolveu o Quick Sort enquanto trabalhava em um projeto de tradução automática na Universidade de Moscou. Ele precisava ordenar grandes listas de palavras em um computador que possuía apenas fitas magnéticas e memória RAM limitadíssima.

O Merge Sort (Aula 34) resolvia a ordenação em tempo (O(N log N)), mas exigia duplicar a memória disponível. Hoare teve um estalo de genialidade: e se pudéssemos ordenar por divisão e conquista diretamente no vetor original (in-place), sem criar subvetores temporários?

Assim nasceu o conceito revolucionário de Particionamento. Em vez de dividir cegamente pela metade geométrica dos índices, o Quick Sort divide os dados com base nos valores numéricos dos próprios elementos em relação a um valor de referência chamado Pivô.

2. O Papel Central do Elemento Pivô

O pivô é a âncora do algoritmo. Ao escolher um elemento pivô (por exemplo, o último elemento do vetor), o objetivo da etapa de particionamento é reorganizar o vetor de modo que:

• Todos os elementos estritamente menores que o pivô fiquem alocados à sua esquerda.
• O próprio pivô seja assentado em sua posição final correta e definitiva no vetor.
• Todos os elementos maiores ou iguais ao pivô fiquem alocados à sua direita.

Uma vez concluído o particionamento, ocorre algo mágico: o elemento pivô nunca mais precisará ser movido até o fim do programa! O problema agora se reduziu a chamar recursivamente o Quick Sort para a sublista à esquerda do pivô e para a sublista à direita do pivô.

3. O Esquema de Particionamento de Lomuto

Existem dois esquemas clássicos de particionamento. O mais pedagógico e direto de compreender é o Esquema de Lomuto (popularizado no livro de Cormen, Leiserson e Rivest):

1. Escolhemos como pivô o último elemento: pivo = arr[fim].
2. Mantemos um ponteiro de barreira i = inicio - 1, que demarca a fronteira dos elementos menores conhecidos.
3. Percorremos um ponteiro j de inicio até fim - 1.
4. Sempre que encontramos arr[j] <= pivo, expandimos a fronteira (i = i + 1) e trocamos arr[i] com arr[j].
5. Ao final, trocamos o pivô com arr[i + 1]. O pivô está assentado no índice i + 1!

4. O Esquema de Particionamento de Hoare

O esquema original criado por Tony Hoare utiliza dois ponteiros que partem das extremidades opostas e caminham um em direção ao outro:

• O ponteiro da esquerda avança enquanto encontrar elementos menores que o pivô.
• O ponteiro da direita recua enquanto encontrar elementos maiores que o pivô.
• Quando ambos os ponteiros param em elementos que violam a barreira, eles trocam de valor entre si.

O particionamento de Hoare realiza em média três vezes menos trocas de memória do que o esquema de Lomuto, sendo a variante preferida em bibliotecas de sistemas de alta performance como a GNU C Library (glibc).

5. Implementação Completa no logicabr.dev

Vejamos a implementação completa do Quick Sort com Particionamento de Lomuto no padrão nativo do logicabr.dev:

// Funcao que particiona o vetor in-place ao redor do pivo (Lomuto)
funcao particionar(vetor arr, numero inicio, numero fim) {
  numero pivo = arr[fim];
  numero i = inicio - 1; // Barreira dos menores

  para (numero j = inicio; j < fim; j++) {
    // Se o elemento for menor ou igual ao pivo, traz para a esquerda
    se (arr[j] <= pivo) {
      i = i + 1;
      // Swap entre arr[i] e arr[j]
      numero temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }

  // Coloca o pivo em sua posicao definitiva (i + 1)
  numero tempPivo = arr[i + 1];
  arr[i + 1] = arr[fim];
  arr[fim] = tempPivo;

  retorno i + 1; // Retorna o indice onde o pivo assentou
}

funcao quickSort(vetor arr, numero inicio, numero fim) {
  // Caso Base: Quando inicio >= fim, o intervalo tem 0 ou 1 item (ja ordenado)
  se (inicio < fim) {
    // Particiona e descobre onde o pivo assentou
    numero indicePivo = particionar(arr, inicio, fim);

    // Ordena recursivamente o subvetor a esquerda do pivo
    quickSort(arr, inicio, indicePivo - 1);

    // Ordena recursivamente o subvetor a direita do pivo
    quickSort(arr, indicePivo + 1, fim);
  }
}

// Bloco de Teste
vetor colecao = [50, 23, 9, 18, 61, 32];

saida("================================================");
saida("        ALGORITMO QUICK SORT logicabr.dev       ");
saida("================================================");
saida("Vetor Original: [50, 23, 9, 18, 61, 32]");

quickSort(colecao, 0, tamanho(colecao) - 1);

saida("Vetor Ordenado:");
para (numero k = 0; k < tamanho(colecao); k++) {
  saida("[" + k + "] = " + colecao[k]);
}
saida("================================================");

6. Teste de Mesa Passo a Passo do Particionamento

Vamos acompanhar detalhadamente o particionamento do vetor [50, 23, 9, 18, 61, 32]:

• Pivô escolhido: 32 (no índice 5). Barreira inicial: i = -1.
• j = 0: arr[0] = 50. É menor que 32? Não. i não se move. Vetor: [50, 23, 9, 18, 61, 32].
• j = 1: arr[1] = 23. É menor que 32? Sim! i vira 0. Troca arr[0] (50) com arr[1] (23). Vetor: [23, 50, 9, 18, 61, 32].
• j = 2: arr[2] = 9. É menor que 32? Sim! i vira 1. Troca arr[1] (50) com arr[2] (9). Vetor: [23, 9, 50, 18, 61, 32].
• j = 3: arr[3] = 18. É menor que 32? Sim! i vira 2. Troca arr[2] (50) com arr[3] (18). Vetor: [23, 9, 18, 50, 61, 32].
• j = 4: arr[4] = 61. É menor que 32? Não. i permanece 2.
• Final: Troca o pivô (32) com arr[i + 1] (arr[3] = 50).
• Resultado do particionamento: [23, 9, 18, 32, 61, 50].

Observe o resultado: o número 32 ficou assentado no índice 3. Todos à esquerda [23, 9, 18] são menores que 32. Todos à direita [61, 50] são maiores que 32. A partição foi perfeita e ocorreu puramente in-place!

7. O Pior Caso O(N²) e Como Evitá-lo (Mediana de Três)

Apesar de ser chamado de "Quick" (Rápido), o algoritmo tem um calcanhar de Aquiles: se o pivô escolhido for repetidamente o extremo (menor ou maior elemento), a divisão não corta o vetor ao meio, mas sim em subproblemas desbalanceados de tamanho 0 e (N - 1).

Se você executar o Quick Sort tradicional escolhendo o último elemento como pivô em um vetor que já estava ordenado, a árvore de recursão degenerará em uma linha reta de (N) níveis, gerando (N(N-1)/2) comparações e caindo no pior caso O(N²)!

Para blindar o algoritmo contra essa armadilha, utiliza-se a técnica da Mediana de Três (Median-of-Three):

// Inspeciona o primeiro, o meio e o ultimo elemento e coloca a mediana no fim
numero meio = (inicio + fim - resto(inicio + fim, 2)) / 2;
// Ordena os 3 valores entre si: arr[inicio], arr[meio], arr[fim]
// O valor mediano resultante e entao utilizado com seguranca absoluta como pivo!

Fundamentos de Arquitetura e Impacto no Hardware da CPU

Para compreender verdadeiramente a performance de um algoritmo em ambientes modernos, não basta analisar apenas a contagem de instruções no papel. A arquitetura dos processadores atuais (x86-64 e ARM) baseia-se em hierarquias complexas de memória: registradores ultra-rápidos, caches L1 (instruções e dados), L2, L3 e finalmente a memória RAM principal.

Quando executamos Quick Sort, o comportamento do circuito de Branch Prediction (predição de saltos condicionais) da CPU desempenha um papel determinante. Cada desvio condicional (como um comando se ou condição de laço enquanto) que não pode ser previsto com precisão pela CPU provoca uma descarga da esteira de instruções (pipeline stall), descartando ciclos preciosos de processamento.

O laço interno de particionamento do Quick Sort executa uma sequência linear ininterrupta de instruções nos registradores sem invocar alocações no heap do sistema operacional, permitindo que as linhas de cache L1D sejam lidas e atualizadas em velocidade de pico.

Diferente do Merge Sort, o Quick Sort não divide memória, tornando a sua pegada de working set extraordinariamente compacta, eliminando custos de translation lookaside buffer (TLB misses) no hardware.

Do ponto de vista da física da computação, a localidade espacial e temporal de referência é outro fator crítico: percorrer a memória em posições contíguas sequenciais permite que o mecanismo de Hardware Prefetching da CPU antecipe os próximos blocos de dados antes mesmo de serem solicitados pelo código, carregando linhas inteiras de cache (tipicamente 64 bytes) sem penalidade de latência.

Demonstração Matemática Rigorosa da Eficiência Assintótica

A análise teórica desenvolvida pela ciência da computação formal permite prever o comportamento exato do algoritmo quando o volume de dados (N) cresce exponencialmente em direção ao infinito:

No caso médio, a recorrência assintótica é descrita por T(N) = 2/N * soma_{k=1}^{N-1} T(k) + Theta(N). Resolvendo essa relação integral por método probabilístico de permutações equiprováveis, obtém-se exatamente C(N) = 2N * ln(N) approx 1.386 N log_2 N comparações, o que comprova que o caso médio é estritamente O(N log N).

Essa dedução algébrica formal comprova por que a intuição superficial frequentemente engana programadores juniores. Saber classificar formalmente as curvas de crescimento assintótico separa o amador do engenheiro de software qualificado para arquitetar sistemas de alta escala que atendem milhões de usuários simultâneos sem lentidão.

10. Otimização de Tail Call na Pilha de Chamadas (Memória O(log N))

Para garantir que o Quick Sort nunca estoure a memória de pilha (stack overflow) mesmo quando o pivô não for perfeito, desenvolvedores experientes de sistemas operacionais aplicam a Eliminação de Recursão em Cauda (Tail Call Optimization):

Após a partição, em vez de chamar cegamente a recursão para ambos os lados, o algoritmo avalia qual dos dois subvetores é menor. A recursão é chamada apenas para o lado menor (cujo tamanho é no máximo (N/2)), enquanto o lado maior é reaproveitado transformando a chamada em um laço enquanto iterativo.

Essa garantia arquitetural limita rigorosamente a profundidade máxima da pilha de execução a (log_2 N) frames, tornando o Quick Sort inquebrável contra ataques intencionais de negação de serviço (DoS) por sobrecarga de pilha.

11. O Grande Duelo: Comparativo dos 5 Algoritmos de Ordenação

Completamos a nossa jornada pelos cinco grandes algoritmos fundamentais da ciência da computação. Veja a síntese definitiva de engenharia de software:

12. Os 5 Erros Clássicos de Implementação do Quick Sort

Fique muito atento a estas falhas na implementação do Quick Sort:

13. Projeto Prático: Ordenação Relâmpago de Catálogo E-Commerce

Vamos construir um classificador de catálogo para uma grande loja virtual que precisa ordenar milhares de produtos por preço em milissegundos para renderização da página de busca:

// Catálogo de produtos de informática
vetor catalogoLoja = [];
catalogoLoja[0] = { sku: "MON-4K", nome: "Monitor 4K 27pol", preco: 1899.90 };
catalogoLoja[1] = { sku: "TEC-MEC", nome: "Teclado Mecanico", preco: 249.90 };
catalogoLoja[2] = { sku: "PLA-VID", nome: "Placa de Video RTX", preco: 3890.00 };
catalogoLoja[3] = { sku: "MOU-GAM", nome: "Mouse Sem Fio 16000DPI", preco: 189.50 };
catalogoLoja[4] = { sku: "FON-USB", nome: "Headset Surround 7.1", preco: 320.00 };
catalogoLoja[5] = { sku: "SSD-NVME", nome: "SSD NVMe 1TB", preco: 450.00 };

funcao particionarProdutos(vetor lista, numero ini, numero fim) {
  moeda pivoPreco = lista[fim].preco;
  numero i = ini - 1;

  para (numero j = ini; j < fim; j++) {
    se (lista[j].preco <= pivoPreco) {
      i = i + 1;
      registro temp = lista[i];
      lista[i] = lista[j];
      lista[j] = temp;
    }
  }

  registro auxPivo = lista[i + 1];
  lista[i + 1] = lista[fim];
  lista[fim] = auxPivo;

  retorno i + 1;
}

funcao quickSortProdutos(vetor lista, numero ini, numero fim) {
  se (ini < fim) {
    numero p = particionarProdutos(lista, ini, fim);
    quickSortProdutos(lista, ini, p - 1);
    quickSortProdutos(lista, p + 1, fim);
  }
}

saida("==================================================");
saida("    CATALOGO CLASSIFICADO POR PRECO (CRESCENTE)   ");
saida("==================================================");

quickSortProdutos(catalogoLoja, 0, tamanho(catalogoLoja) - 1);

para (numero item = 0; item < tamanho(catalogoLoja); item++) {
  saida(catalogoLoja[item].sku + " | R$ " + catalogoLoja[item].preco + " | " + catalogoLoja[item].nome);
}
saida("==================================================");

Parabéns! Você concluiu a Trilha 7: Algoritmos de Busca e Ordenação Eficiente. Na próxima aula, iniciaremos a Trilha 8: Estruturas de Dados Lineares e Abstratas, desvendando como gerenciar dados na memória com as clássicas Pilhas (Stacks) e o princípio LIFO.