Quicksort
Divide para conquistar — escolhe um pivô e particiona o array em menores e maiores, ordenando recursivamente cada parte.
O(n log n)O(log n)Como Funciona
Passo a passo do algoritmo
Escolha um pivô
Selecione um elemento como pivô. A estratégia mais comum é usar o último elemento do subarray. A escolha do pivô impacta diretamente o desempenho.
pivô = array[alto]Particione o array
Reorganize os elementos de forma que todos menores ou iguais ao pivô fiquem à esquerda, e todos maiores fiquem à direita. O pivô ainda não está na posição final.
para j de baixo até alto-1: se array[j] ≤ pivô: troca(array, ++i, j)Posicione o pivô definitivamente
Após a partição, coloque o pivô em sua posição final — exatamente onde ele ficará no array completamente ordenado.
troca(array, i+1, alto)Recursão nas partições
Aplique o mesmo processo recursivamente na partição esquerda (elementos menores) e na partição direita (elementos maiores).
quicksort(array, baixo, pivôFinal-1)
quicksort(array, pivôFinal+1, alto)Caso base da recursão
A recursão para quando um subarray tem zero ou um elemento — ele já está ordenado por definição e não precisa de processamento.
se baixo >= alto: retorneImplementação
Código comentado em JavaScript e Python
function quicksort(array, baixo = 0, alto = array.length - 1) {
// Caso base: subarray vazio ou de um elemento
if (baixo >= alto) return array;
// Particiona e obtém a posição final do pivô
const posicaoPivo = particionar(array, baixo, alto);
// Ordena recursivamente a partição esquerda
quicksort(array, baixo, posicaoPivo - 1);
// Ordena recursivamente a partição direita
quicksort(array, posicaoPivo + 1, alto);
return array;
}
function particionar(array, baixo, alto) {
const valorPivo = array[alto]; // Pivô = último elemento
let i = baixo - 1; // Índice do menor elemento
for (let j = baixo; j < alto; j++) {
// Se elemento atual é menor ou igual ao pivô
if (array[j] <= valorPivo) {
i++;
// Troca: move elemento menor para a esquerda
[array[i], array[j]] = [array[j], array[i]];
}
}
// Posiciona o pivô na posição correta
[array[i + 1], array[alto]] = [array[alto], array[i + 1]];
return i + 1; // Retorna posição final do pivô
}
// Exemplo de uso
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(quicksort(arr)); // [11, 12, 22, 25, 34, 64, 90]Playground
Visualize a partição e recursão do Quicksort em ação
Quando Usar
Cenários ideais para este algoritmo
Ordenação de uso geral
Implementação padrão em muitas linguagens — V8 (JavaScript) e Python usam variações do Quicksort para arrays.
Grandes volumes de dados
Excelente para arrays em memória principal graças ao ótimo uso de cache e baixo overhead de alocação.
Quando espaço é crítico
Versão in-place usa apenas O(log n) de espaço extra na pilha de recursão — muito menos que Merge Sort (O(n)).
Dados sem muitas duplicatas
Performa muito bem quando os dados têm poucos valores repetidos, evitando degeneração para O(n²).
Complexidade
Análise de desempenho por cenário
| Cenário | Tempo |
|---|---|
| Melhor caso | O(n log n) |
| Caso médio | O(n log n) |
| Pior caso | O(n²) |