[Veja a versão desta página em formato perguntas-e-respostas]
Este página é inspirada no capítulo 8 de CLR. Ela trata do seguinte problema de ordenação de vetor:
Problema da ordenação: rearranjar um vetor A[p..r] de modo que ele fique em ordem crescente.
O algoritmo Quicksort, inventado por C.A.R. Hoare, usa o paradigma da divisão e conquista para resolver o problema Ele é muito rápido em média, mas lento no pior caso.
Veja o verbete Quicksort na Wikipedia.
O coração do algoritmo Quicksort está no seguinte subproblema, que formularemos de maneira propositalmente vaga:
rearranjar A[p..r] de modo que todos os elementos pequenos fiquem na parte esquerda do vetor e todos os elementos grandes fiquem na parte direita.
Este é o subproblema da separação. O ponto de partida para a solução do subproblema é a escolha de um "pivô", digamos x: os elementos do vetor que forem maiores que x serão considerados grandes e os demais serão considerados pequenos. É preciso escolher x de tal modo que cada uma das duas partes do vetor rearranjado seja estritamente menor que o vetor todo.
O seguinte algoritmo resolve o subproblema da separação da seguinte maneira: supondo p < r, o algoritmo rearranja os elementos de A[p..r] e devolve um índice q tal que p ≤ q < r e, para algum x,
| p | q | q+1 | r | ||||||||
| ≤ x | ≤ x | ≤ x | ≤ x | ≤ x | ≤ x | ≥ x | ≥ x | ≥ x | ≥ x | ≥ x | ≥ x |
A seguinte versão do algoritmo adota como pivô x o valor inicial de A[p].
| Separe (A, p, r) |
| 11 o x ← A[p] |
| 12 o i ← p−1 |
| 13 o j ← r+1 |
| 14 o enquanto 0 = 0 faça |
| 15 oooo repita j ← j−1 |
| 16 ooooooo até que A[j] ≤ x |
| 17 oooo repita i ← i+1 |
| 18 ooooooo até que A[i] ≥ x |
| 19 oooo se i < j |
| 10 ooooooo então troque A[i] ↔ A[j] |
| 11 ooooooo senão devolva j |
Para entender como e por que o algoritmo funciona como deveria, observe que no início de cada iteração do loop que começa na linha 4 temos as seguintes propriedades invariantes:
A[p..i] ≤ x , i < j , A[j..r] ≥ x .
(Se eu estivesse programando pra valer, escreveria estas relações, como comentário, logo depois da linha 4.)
| p | i | j | r | ||||||||
| ≤ x | ≤ x | ≤ x | ≥ x | ≥ x |
Na última passagem pela linha 4, o vetor A[i+1 .. j−1] consiste em
No primeiro caso, o algoritmo chega à linha 11 com j = i−1.
| p | j | i | r | ||||||||
| ≤ x | ≤ x | ≤ x | ≤ x | ≤ x | ≤ x | ≥ x | ≥ x | ≥ x | ≥ x | ≥ x | ≥ x |
No segundo caso, o algoritmo chega à linha 11 com j = i.
| p | j=i | r | |||||||||
| ≤ x | ≤ x | ≤ x | ≤ x | ≤ x | = x | ≥ x | ≥ x | ≥ x | ≥ x | ≥ x | ≥ x |
Não é difícil perceber agora que o algoritmo faz o que prometeu; em particular, que p ≤ j < r na linha 11.
Quanto tempo o algoritmo Separe consome? Comecemos contando o número total de execuções das linhas 6 e 8. (Note que as execuções do bloco de linhas 5-6 não são, necessariamente, consecutivas. O mesmo vale para o bloco de linhas 7-8.) Se a o número total de execuções da linha 6 e b o número total de execuções da linha 8, então a+b ≤ n+2 , sendo n = r−p+1. Analogamente, a soma do número total de execuções da linha 5 e da linha 7 não passa de n+2.
Agora considere as demais linhas. O número total de execuções da linha 9 não passa de n+1. O número de execuções da linha 10 não passa de n, o número de execuções da linha 4 não passa de n+1, a as linhas 1 a 3 são executadas 1 vez cada.
Se a execução de cada linha consome 1 unidade de tempo, o consumo total de tempo não passa de
5n + 6 .
Se cada execução de cada linha consumisse uma quantidade de tempo diferente de 1 (mas independente de n), o consumo total não passaria de um múltiplo de n, ou seja, o consumo estaria em
Ο(n) .
Portanto, o algoritmo é linear.
O algoritmo Quicksort recebe um vetor A[p..r] e rearranja o vetor em ordem crescente.
| Quicksort (A, p, r) |
| 1 o se p < r então |
| 2 oooo q ← Separe (A, p, r) |
| 3 oooo Quicksort (A, p, q) |
| 4 oooo Quicksort (A, q+1, r) |
Note que q ≥ p e q < r; portanto os vetores A[p..q] e A[q+1 .. r] são estritamente menores que o vetor original A[p..r]. Isso garante que a execução do algoritmo termina, mais cedo ou mais tarde.
(Se você estivesse programando pra valer, que comentários escreveria no seu programa? Eu escreveria só dois comentários. Antes da linha 1 eu diria "estamos supondo p<r". Depois da linha 2 eu diria "p≤q<r e A[i]≤A[j] para cada i em p..q e cada j em q+1..r".)
Durante a execução do Quicksort2, o computador usa um pilha para administrar a recursão. Mostre que a pilha pode chegar a ter Ω(n) elementos quando Quicksort2 processa um vetor com n elementos.
Modifique Quicksort2 de modo que a pilha tenha Ο(log n) elementos, mesmo no pior caso.
Quanto tempo o algoritmo consome no pior caso? Como vimos acima, podemos supor que Separe não consome mais que 5n+6 unidades de tempo, sendo n = r−p+1. Então o consumo de tempo do Quicksort no pior caso, digamos T(n), satisfaz a seguinte recorrência
| T(n) = 5n + 7 + max 0<k<n (T(k) + T(n−k)) | (*) |
onde o máximo é tomado sobre todos os possíveis valores de k no intervalo 1 .. n−1. Podemos supor T(1) = 1. Assim, por exemplo, T(2) ≤ 10+7+T(1)+T(1) = 19. Outro exemplo: T(3) ≤ 15+7+T(1)+T(2) = 42. Mais um exemplo: T(4) ≤ 20+7+T(1)+T(3) = 70, uma vez que T(1)+T(3) = 43 > 38 = T(2)+T(2). Em geral, vamos mostrar que
T(n) ≤ 5n²
para n = 1, 2, 3, … A desigualdade é certamente verdadeira quando n = 1, 2, 3. Agora suponha que n > 3 e suponha que a desigualdade vale para T(i) sempre que i < n. Teremos então
| T(n) | = | 5n + 7 + maxk (T(k) + T(n−k)) |
| ≤ | 5n + 7 + maxk (5k² + 5(n−k)²) | |
| = | 5n + 7 + 5 (1 + (n−1)²) | |
| = | 5n² − 5n + 17 | |
| ≤ | 5n² . |
O terceiro passo da prova segue da seguinte observação: para n fixo e k variando entre 1 e n−1, a expressão k² + (n−k)² tem valor máximo nos pontos k = 1 e k = n−1 (e atinge o mínimo quando k está próximo de n/2). O último passo da prova está correto pois quando n > 3 tem-se −5n+17 ≤ 0.
A cota superior de 5n² não é exagerada. De fato, é fácil mostrar que T(n) ≥ 2n². Portanto T(n) está em Ο(n²) e também em Ω(n²).
Se deixarmos de lado a hipótese artificial de que cada linha "simples" do algoritmo consome 1 unidade de tempo, as conclusões ainda serão as mesmas. A recorrência pode ser reescrita como T(n) = max 0<k<n (T(k) + T(n−k)) + Ο(n) e daí se deduz que T(n) está em Ο(n²). Conclusão: no pior caso, o algoritmo Quicksort é quadrático. Por que, então, o algoritmo é tão popular?
O melhor desempenho do Quicksort ocorre quando todas as invocações de Separe dividem o vetor na proporção (1/2)-para-(1/2), ou seja, quando todas as invocações devolvem um índice que está a meio caminho entre p e r. O consumo de tempo do algoritmo nesse caso, digamos S(n), satisfaz a recorrência
S(n) = S(⌈n/2⌉) + S(⌊n/2⌋) + 5n + 7
para todo natural n ≥ 2 (veja a definição de teto). A exemplo do que fizemos em outra ocasião, podemos mostrar que
S(n) ≤ 12 n log2 n
para todo natural n ≥ 3.
O comportamento não é muito diferente quando o vetor é dividido de maneira menos equilibrada. Suponha, por exemplo, que todas as invocações de Separe dividem o vetor na proporção (1/9)-para-(8/9). Nesse caso, o consumo de tempo, digamos R(n), satisfaz recorrência da forma
R(n) = R(⌈n/9⌉) + R(⌊8n/9⌋) + 5n + 7
para todo natural n ≥ 2. Mostremos que
R(n) ≤ 7 n log9/8 n
para todo n ≥ 2. Supondo R(1) = 1, é fácil verificar que a desigualdade vale quando n = 2, 3. Agora tome n ≥ 4. Então, por hipótese de indução, e usando sempre log na base 9/8,
| R(n) | = | 7 ⌈n/9⌉ log ⌈n/9⌉ + 7 ⌊8n/9⌋ log ⌊8n/9⌋ + 5n + 7 |
| ≤ | 7 (⌈n/9⌉ + ⌊8n/9⌋) log ⌊8n/9⌋ + 5n + 7 | |
| = | 7 n log (8n/9) + 5n + 7 | |
| = | 7 n log (n) + 7 n log (8/9) + 5n + 7 | |
| = | 7 n log n − 7 n + 5n + 7 | |
| = | 7 n log n − 2n + 7 | |
| < | 7 n log n . |
(Como seria de se esperar, o coeficiente de n lg n é maior nesse caso que no anterior: 7 log9/8 n > 7×5.884 log2 n > 41 log2 n > 12 log2 n.)
A análise dos dois casos acima — a divisão na proporção (1/2)-para-(1/2) e a divisão na proporção (1/9)-para-(8/9) — sugere a seguinte conclusão: se Separe sempre divide o vetor em alguma proporção tn-para-(1−t)n, o consumo de tempo do Quicksort é
Ο(n lg n).
(É claro que a constante escondida sob a notação Ο é tanto maior quanto mais t se afasta de 1/2.)
As conclusões valem mesmo que o valor de t seja diferente em cada invocação de Separe. Essas observações sugerem que o consumo de tempo "típico" do Quicksort está em Ο(n lg n).
Se o vetor A[p..r] for crescente ou aproximadamente crescente, o algoritmo Quicksort consome Ω(n²) unidades de tempo. Para evitar casos desfavoráveis como esses, podemos escolher o pivô aleatoriamente, como faremos a seguir.
Suponha dado um algoritmo auxiliar Random que funciona assim: ao receber um par p ≤ r de números naturais, devolve um número aleatório no intervalo p..r, sendo todos os números do intervalo igualmente prováveis. Existem implementações (aproximadas) de Random que consomem uma quantidade de tempo constante, ou seja, independente de p e r. Esse algoritmo auxiliar pode ser usado para construir versões aleatorizadas (= randomized) de Separe e Quicksort:
| Separe-Aleatorizado (A, p, r) |
| 1 o i ← Random(p, r) |
| 2 o troque A[p] ↔ A[i] |
| 3 o Separe (A, p, r) |
| Quicksort-Aleatorizado (A, p, r) |
| 1 o se p < r |
| 2 oooo então q ← Separe-Aleatorizado (A, p, r) |
| 3 oooo então Quicksort-Aleatorizado (A, p, q) |
| 4 oooo então Quicksort-Aleatorizado (A, q+1, r) |
No pior caso, Quicksort-Aleatorizado consome tanto tempo quanto Quicksort. Em média, entretanto, Quicksort-Aleatorizado é muito mais rápido: seu consumo médio é de Ο(n lg n) unidades de tempo, como mostraremos a seguir.
A aplicação do subalgoritmo Separe-Aleatorizado ao vetor A[p..r] determina dois subvetores. Diremos que o Separe-Aleatorizado produz resultado (i, n−i) se os dois vetores resultantes tiverem tamanhos i e n−i, onde n = r−p+1. Os possíveis resultados são
(1, n−1), (2, n−2), … , (n−2, 2), (n−1, 1) .
Ao todo, temos n−1 possíveis resultados. Resta saber qual a probabilidade de cada um.
Trataremos apenas do caso em que o vetor não tem elementos repetidos. (Acho que os resultados não valem sem essa hipótese.) Sob essa hipótese, a probabilidade de cada caso só depende do valor de A[p] antes no fim da linha 2 de Separe-Aleatorizado. Não é difícil verificar que
(Note que Separe-Aleatorizado produz o mesmo resultado quer A[p] seja o menor ou o segundo menor elemento do vetor.)
Em virtude da aleatorização, A[p] tem igual probabilidade de ser o menor, o segundo menor, etc., o n-ésimo menor elemento do vetor. Concluímos que o resultado (1,n−1) tem probabilidade 2/n e cada um dos demais resultados tem probabilidade 1/n.
Denotemos por E(n) o valor esperado do consumo de tempo do Quicksort-Aleatorizado. Então
| E(n) = 5n + 9 + | s1 + s1 + s2 + … + sn−1 | , |
| n |
onde si = E(i)+E(n−i) para i = 1,2,3,…,n−1. (O termo s1 aparece duas vezes, mas nossos cálculos mostrarão que isso não faz diferença para a solução assintótica da recorrência.) Se agruparmos termos iguais teremos a recorrência
| (**) |
A análise de uma recorrência mais simples (veja exercício abaixo) sugere que a solução está em Ο(n lg n). Alguns cálculos confirmam esta suspeita:
E(n) ≤ 20 n lg n
para n = 2, 3, …