Quicksort

O quicksort, ou ordenação rápida, é um dos algoritmos de ordenação mais usados. Escolhe um pivô, divide a lista entre os valores menores do que o pivô e os restantes, e ordena os dois lados da mesma forma. É rápido na prática e não precisa de uma lista extra, mas a rapidez depende do pivô.

Barras particionadas em torno de uma barra pivô: as menores de um lado, as maiores do outro e o pivô entre elas
Barras particionadas em torno de uma barra pivô: as menores de um lado, as maiores do outro e o pivô entre elas

A ideia

Escolha um valor como pivô. Reorganize a lista para que cada valor menor do que o pivô fique antes dele e todos os outros depois. Essa reorganização chama-se partição e deixa o pivô exatamente onde deve ficar na lista ordenada. Os dois lados são agora problemas independentes: ordene cada um com o quicksort. Um lado com um só valor, ou nenhum, já está ordenado.

A partição, passo a passo

A aplicação usa a partição de Lomuto. O pivô é movido para o fim da parte. Um marcador começa no início: tudo o que está antes dele é menor do que o pivô. Cada um dos outros valores é comparado com o pivô; se for menor, é trocado para a posição do marcador e o marcador avança uma posição. No fim, o pivô é trocado para a posição do marcador. Veja 5, 1, 4, 2, 8 com o último valor como pivô: os quatro valores são menores do que 8, por isso 8 fica no fim. A parte 5, 1, 4, 2 é particionada em torno de 2, o que dá 1, 2, 4, 5, e 4, 5 em torno de 5. São 8 comparações, 2 trocas e 3 partições.

Bons e maus pivôs

Se cada pivô ficasse no meio, cada partição reduziria o problema a metade, e a ordenação precisaria de cerca de n log₂ n comparações. Numa lista aleatória, os pivôs raramente são perfeitos, mas costumam ser suficientemente bons: para 40 valores aleatórios, a aplicação conta cerca de 190 comparações. O pior caso acontece quando o pivô é sempre o menor ou o maior valor. Com o último valor como pivô, uma lista já ordenada, ou invertida, faz exatamente isso: cada partição só retira o pivô, e a ordenação precisa de n(n − 1)/2 comparações, 780 para 40 valores.

Escolher o pivô

Um pivô aleatório torna o pior caso extremamente improvável para qualquer entrada, porque nenhuma ordem em particular o consegue enganar. A mediana de três, o valor do meio entre o primeiro elemento, o do meio e o último, é barata e lida bem com listas ordenadas e invertidas. Experimente ambos numa lista ordenada na aplicação: as comparações descem de 780 para cerca de 150. Muitos valores iguais são outro problema: ficam todos do mesmo lado do pivô. Uma partição em três partes, que guarda os valores iguais ao pivô numa parte do meio, resolve isso.

História e utilização

Tony Hoare inventou o quicksort em 1959 e publicou-o em 1961. A partição original dele percorre a lista a partir das duas pontas e faz menos trocas; a versão mais simples de Lomuto, mostrada aqui, tornou-se popular através dos manuais. O quicksort ordena in situ e o seu ciclo interno é muito curto, por isso costuma ser mais rápido do que o merge sort na prática, embora não seja estável. O introsort, a ordenação da biblioteca padrão de C++, executa o quicksort e passa para o heap sort se as partições ficarem demasiado desiguais, por isso o seu pior caso continua a ser n log n.

Tony Hoare, que inventou o quicksort em 1959 e o publicou em 1961.
Tony Hoare, que inventou o quicksort em 1959 e o publicou em 1961.

Experimente

Abra a aplicação e prima Avançar. A parte a particionar está sombreada, o pivô tem a sua própria cor e a linha tracejada marca o fim da parte esquerda, a dos valores menores do que o pivô. Cada pivô fica verde quando chega à posição final. Escolha uma lista ordenada e o último valor como pivô, mude depois para a mediana de três e compare os contadores.

Perguntas frequentes

Qual é a complexidade temporal do quicksort?

O(n log n) em média e com bons pivôs, O(n²) no pior caso. Ordena in situ; a recursão precisa de O(log n) de memória extra quando o lado menor é ordenado primeiro.

Qual é a diferença entre a partição de Lomuto e a de Hoare?

Lomuto usa um só marcador e percorre a lista da esquerda para a direita, o que é fácil de seguir e é o que esta aplicação mostra. Hoare percorre a lista a partir das duas pontas, uma em direção à outra, e troca os pares que estão do lado errado, o que faz em média cerca de três vezes menos trocas.

Porque é que o quicksort é lento quando muitos valores são iguais?

Os valores iguais ao pivô vão todos para o mesmo lado, por isso uma lista com poucos valores distintos divide-se de forma desigual, e uma lista de valores iguais é tão má como o pior caso. Uma partição em três partes, que junta no meio os valores iguais ao pivô, evita isso.

O quicksort é estável?

Não. As trocas durante uma partição movem valores a grandes distâncias, por isso valores iguais podem mudar de ordem.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Experimentar o quicksort