Esta página mostra como calcular o consumo de tempo do algoritmo de ordenação conhecido como Quicksort. O algoritmo é recursivo, e portanto a análise exige a resolução de uma recorrência.
O problema de ordenação consiste em colocar em ordem um vetor A[1 .. n]. Nesta página, convém trocar o primeiro índice do vetor por uma variável e apresentar o problema assim:
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 método da divisão e conquista para resolver o problema. O algoritmo é rápido (linearítmico) em média, mas lento (quadrático) no pior caso.
O coração do algoritmo Quicksort é o seguinte subproblema, que formularemos de maneira propositalmente vaga:
rearranjar A[p .. r] de modo que todos os elementos pequenos fiquem no início do vetor e todos os elementos grandes fiquem no fim.
Este é o subproblema da divisão (também conhecido como partition problem). 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 menor que o vetor todo.
Este capítulo usará a seguinte versão específica do subproblema da divisão: rearranjar os elementos de A[p .. r] e encontrar um índice q no intervalo p .. r tal que
A[p .. q−1] ≤ A[q] < A[q+1 .. r] .
Essa notação deve ser entendida assim: A[i] ≤ A[q] para cada i no intervalo p .. q−1 e A[q] ≤ A[ j] para cada j no intervalo q+1 .. r. Portanto, A[q] é o pivô. Toda instância desse subproblema tem solução se admitirmos que os subvetores A[p .. q−1] ou A[q+1 .. r] possam ser vazios (ou seja, que possamos ter p = q ou q = r).
| p | q | r | |||||||
| ≤ x | ≤ x | ≤ x | ≤ x | ≤ x | = x | > x | > x | > x | > x |
O seguinte algoritmo Divide resolve o subproblema da divisão adotando como pivô o valor original de A[r]:
| Divide (A, p, r) ▷ p ≤ r |
| 1 . x := A[r] ▷ pivô |
| 2 . i := p − 1 |
| 3 . para j := p até r − 1 |
| 4 .ooo se A[ j] ≤ x |
| 5 .ooooooo i := i + 1 |
| 6 .ooooooo troque A[i] com A[ j] |
| 7 . troque A[i+1] com A[r] |
| 8 . devolva i + 1 |
Para entender como e por que o algoritmo funciona, observe que no início de cada repetição do bloco de linhas 4 a 6 valem as seguintes propriedades invariantes:
(Eu deveria embutir estas relações, como comentário, entre as linhas 3 e 4 do pseudocódigo.) A primeira das figuras abaixo mostra o estado do vetor no início de uma iteração qualquer. A segunda mostra o estado do vetor no início da linha 7:
| p | i | j | r | ||||||
| ≤ x | ≤ x | ≤ x | > x | > x | > x | > x | > x | > x | = x |
| p | i | j | |||||||
| ≤ x | ≤ x | ≤ x | ≤ x | ≤ x | > x | > x | > x | > x | = x |
Na linha 8 temos A[p .. i] ≤ A[i+1] < A[i+2 .. r] e p ≤ i+1 ≤ r, como prometemos acima.
Consumo de tempo. Quanto tempo o algoritmo Divide consome em função do número n = r−p+1 de elementos do vetor A[p .. r]? Comecemos por contar quantas vezes cada linha do código é executada. As linhas 1 e 2 são executadas uma vez cada. A linha 3 é executada n vezes. A linha 4 é executada n−1 vezes. As linhas 5 e 6 são executadas no máximo n−1 vezes cada. As linhas 7 e 8 são executadas uma vez cada. É razoável supor que cada execução de cada linha de código consome tempo constante (ou seja, independente de n). A seguinte tabela resume os cálculos, mostrando, para cada linha de código, o consumo de tempo de todas as execuções da linha ao longo da execução do algoritmo:
| Divide (A, p, r) | ||
| 1 . x := A[r] | Θ(1) | |
| 2 . i := p − 1 | Θ(1) | |
| 3 . para j := p até r − 1 | Θ(n) | |
| 4 .ooo se A[ j] ≤ x | Θ(n) | |
| 5 .ooooooo i := i + 1 | Ο(n) | |
| 6 .ooooooo troque A[i] com A[ j] | Ο(n) | |
| 7 . troque A[i+1] com A[r] | Θ(1) | |
| 8 . devolva i + 1 | Θ(1) |
A soma da coluna direita da figura é Θ(n) e portanto o consumo de tempo do algoritmo Divide está em Θ(n) . Como n é o tamanho de uma instância do problema da divisão, podemos dizer que o algoritmo é linear.
Número de comparações.
Poderíamos calcular o consumo de tempo do algoritmo
de uma maneira ligeiramente diferente,
e talvez mais prática.
Considere as comparações entre elementos do vetor
que ocorrem na linha 4 do algoritmo
e observe que o número dessas comparações
é proporcional
ao consumo de tempo do algoritmo
(tanto no pior quanto no melhor caso).
Mais precisamente, o número de comparações
está na mesma ordem Θ que o consumo de tempo.
O número dessas comparações é
n − 1 ,
e portanto o algoritmo Divide consome Θ(n) unidades de tempo.
Exemplo A: A figura abaixo mostra o estado de um vetor antes e depois de passar pelo o algoritmo Divide, com p = 1 e r = 8.
[1 3 6 2 8 5 7 4] [1 3 2] 4 [8 5 7 6]
≤por
<na linha 4?
antes depois devolve [1 2 3] [1 2] 3 3
O algoritmo Quicksort recebe um vetor A[p .. r] e rearranja o vetor em ordem crescente. O algoritmo supõe que p ≤ r+1, estando portanto preparado para receber um vetor vazio.
| Quicksort (A, p, r) ▷ p ≤ r+1 |
| 1 . se p ≤ r |
| 2 .ooo q := Divide (A, p, r) |
| 3 .ooo Quicksort (A, p, q − 1) |
| 4 .ooo Quicksort (A, q+1, r) |
No fim de cada execução da linha 2 temos p ≤ q ≤ r. Nas linhas 3 e 4, o tamanho dos vetores A[p .. q−1] e A[q+1 .. r] é estritamente menor que o tamanho do vetor original A[p .. r]; isso garante que a execução do algoritmo termina, mais cedo ou mais tarde.
Depois da linha 2, temos A[p .. q−1] ≤
A[q] <
A[q+1 .. r]
(e portanto A[q] está na posição correta
).
Segue daí, por indução no tamanho do vetor,
que o algoritmo rearranja o vetor em ordem crescente,
como prometeu fazer.
O algoritmo Quicksort implementa a estratégia da divisão e conquista. A fase da divisão — executada por Divide — é a que consome mais tempo. A fase da combinação dos resultados das duas chamadas recursivas é trivial. (No algoritmo Mergesort, ao contrário, a fase da divisão é trivial, enquanto a fase da combinação é a que consome mais tempo.)
Exemplo B: A figura abaixo mostra a evolução de um vetor com 8 elementos à medida que é ordenado pelo algoritmo Quicksort. Os colchetes indicam subvetores que ainda não foram ordenados. Os elementos fora dos colchetes já estão em sua posição definitiva.
[1 3 6 2 8 5 7 4] [1 3 2] 4 [8 5 7 6] [1] 2 [3] 4 [5] 6 [7 8] 1 2 3 4 5 6 [7] 8 1 2 3 4 5 6 7 8
O algoritmo executa um total de 7 + 2 + 3 + 0 + 0 + 0 + 1 + 0 = 13 comparações entre elementos do vetor.
enquanto. 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 Ο(lg n) elementos, mesmo no pior caso.
Mostraremos abaixo que o consumo de tempo do algorimo Quicksort fica entre Ο(n lg n) e Ο(n²). Procuraremos mostrar também que o consumo médio é Ο(n lg n).
Como já observamos acima,
é conveniente medir o consumo de tempo do Quicksort
pelo número total de comparações entre elementos do vetor.
Para simplificar, diremos simplesmente comparações
,
deixando a expressão entre elementos do vetor
subentendida.
Todas essas comparações ocorrem na linha 4 da rotina Divide.
Cada aplicação de Divide
a um vetor com n elementos faz n − 1 comparações.
O número de comparações ao longo da execução do Quicksort depende criticamente do tamanho relativo dos dois subvetores — A[p .. q−1] e A[q+1 .. r] — produzidos por Divide. Isso, por sua vez, depende do valor do pivô usado por Divide. (Veja exercício acima.)
A intuição sugere que o desempenho é melhor quando o resultado de Divide é equilibrado, ou seja, quando os subvetores A[p .. q−1] e A[q+1 .. r] são aproximadamente do mesmo tamanho. A mesma intuição sugere que o desempenho é pior quando o resultado de Divide é desequilibrado, ou seja, quando um dos subvetores A[p .. q−1] e A[q+1 .. r] é muito grande (e portanto o outro é muito pequeno).
Submeta um vetor A[p .. r] ao Quicksort. Seja n o número de elementos do vetor e denote por T*(n) o número de comparações que Quicksort faz, no pior caso. A intuição sugere que o pior caso ocorre quando todas as chamadas de Divide devolvem q = p ou q = r. Como Divide faz n − 1 comparações, a intuição sugere que T*(n) obedece a recorrência T*(n) = n − 1 + T*(0) + T*(n−1). Como T*(0) = 0, a recorrência se reduz a
| T*(n) = T*(n−1) + n − 1 . | (A) |
É fácil desenrolar essa recorrência:
| T*(n) | = | T*(n−1) + n − 1 |
| = | T*(n−2) + (n − 2) + (n − 1) | |
| = | T*(n−3) + (n − 3) + (n − 2) + (n − 1) | |
| = | T*(n−4) + (n − 4) + (n − 3) + (n − 2) + (n − 1) | |
| ⋮ | ||
| = | T*(0) + 0 + 1 + 2 + … + (n − 2) + (n − 1) | |
| = | n (n − 1) / 2 . |
Portanto, T*(n) = Θ(n²). Conclusão: o desempenho de pior caso do Quicksort é decepcionante (tão ruim quanto a do algoritmo de inserção).
Como a cota superior do pior caso aplica-se a todos os casos, podemos resumir esta seção assim: o número de comparações que Quicksort faz está em Ο(n²).
Exemplo C: A figura abaixo ilustra o pior caso do Quicksort. O algoritmo executa um total de 28 comparações.
[1 2 3 4 5 6 7 8] [1 2 3 4 5 6 7] 8 [1 2 3 4 5 6] 7 8 ⋮ [1] 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
T*(n) = maxi (T*(i−1) + T*(n−i)) + n − 1 ,
com max tomado sobre todos os valores de i no intervalo 1 .. n. (Observe que a soma (i−1) + (n−i) dos argumentos de T* vale n−1.) Mostre que T*(n) = Ο(n²). Mostre que T*(n) = Ω(n²).
Submeta ao algoritmo Quicksort um vetor A[p .. r] com n elementos. Denote por T*(n) o número de comparações que o algoritmo faz no melhor caso. A intuição sugere que o melhor caso ocorre quando todas as chamadas de Divide devolvem um índice q a meio caminho entre p e r, e portanto o vetor A[p .. q−1] tem ⌈(n − 1)/2⌉ elementos e o vetor A[q+1 .. r] tem ⌊(n − 1)/2⌋ elementos. Assim, T*(n) obedece a recorrência
| T*(n) = T*(⌈½ (n−1)⌉) + T*(⌊½ (n−1)⌋) + n − 1 | (B) |
onde o n − 1
final é o número de comparações que Divide faz.
Para resolver essa recorrência,
poderíamos usar o Teorema Mestre
(veja a página Recorrências)
e concluir que
T*(n) =
Θ(n lg n).
Mas é mais instrutivo fazer os cálculos explicitamente.
Podemos começar
resolvendo a recorrência bem mais simples
S(n) = 2 S(n/2) + n,
na esperança de que sua solução esteja na mesma classe assintótica que a de (B). Você pode supor que nessa nova recorrência os valores de n são potências de 2. Se desenrolarmos essa recorrência teremos
| S(n) | = | 2 S(n/2) + n |
| = | 2 (2 S(n/2/2) + n/2) + n | |
| = | 4 S(n/4) + n + n | |
| = | 4 (2S(n/8) + n/4) + n + n | |
| = | 8 S(n/8) + n + n + n | |
| = | 2k S(n/2k) + n k . |
Quando k atinge lg n, temos S(n) = n S(1) + n lg n. Supondo que S(1) = 1, teremos S(n) = n + n lg n. Segue daí que n lg n ≤ S(n) ≤ 2 n lg n e portanto S(n) = Θ(n lg n).
Isso faz supor que a solução da recorrência (B) também está em Θ(n lg n). Vamos confirmar essa suspeita. Comece por observar que T*(0) = 0 e portanto T*(1) = T*(0) + T*(0) + 0 = 0. Em seguida, vamos mostrar, por indução, que
T*(n) ≤ n lg n
para todo natural n ≥ 1. Quando n = 1, a desigualdade vale pois T*(1) = 0 ≤ 1⋅lg 1. Agora tome n > 1 e suponha que a desigualdade vale para argumentos de T* menores que n. Então
| T*(n) | = | T*(⌈½ (n−1)⌉) + T*(⌊½ (n−1)⌋) + n − 1 |
| = | T*(⌊n/2⌋) + T*(⌈n/2⌉−1) + n − 1 | |
| ≤ | ⌊n/2⌋ lg ⌊n/2⌋ + (⌈n/2⌉−1) lg (⌈n/2⌉−1) + n − 1 | |
| < | (n/2) lg (n/2) + (n/2) lg (n/2) + n − 1 | |
| = | n lg (n/2) + n − 1 | |
| = | n (lg n − 1) + n − 1 | |
| = | n lg n − n + n − 1 | |
| < | n lg n , |
como prometemos mostrar.
Portanto, T*(n) = Ο(n lg n). Com algum esforço adicional, é possível mostrar que T*(n) = Ω(n lg n). O Teorema Mestre confirma que a solução da recorrência (B) está em Θ(n lg n).
Como a cota inferior do melhor caso aplica-se a todos os casos, podemos resumir esta seção assim: o número de comparações que Quicksort faz está em Ω(n lg n).
Exemplo D: O exemplo B ilustra o melhor caso do Quicksort. O algoritmo faz 13 comparações.
T*(n) = mini (T*(i−1) + T*(n−i)) + n − 1
onde min é tomado sobre todos os valores de i no intervalo 1 .. n. Mostre que T*(n) = Ω(n lg n). Mostre que T*(n) = Ο(n lg n).
Como vimos nas seções anteriores,
o número de comparações que Quicksort
faz
fica entre Ω(n lg n)
e Ο(n²).
Qual será o número médio
de comparações?
Quem sabe algo entre próximo de Θ(n1.5)?
Ou talvez algo próximo de
Θ(n lg² n)?
Uma análise cuidadosa e a experiência prática
mostram que a situação é bem mais favorável:
o número médio
é
Θ(n lg n),
como no melhor caso! (Mas é claro que a constante escondida sob a notação Θ é maior no caso médio que no melhor caso.)
Esse desempenho médio linearítmico tem a seguinte explicação informal. Em muitas execuções da rotina Divide, uma porcentagem dos elementos do vetor fica em um dos subvetores e a porcentagem complementar no outro. Mais precisamente, para muitas execuções de Divide existe um número a entre 0 e 1, independente de n, tal que um dos subvetores fica com cerca de an elementos e o outro com cerca de (1 − a)n elementos. Por exemplo, uma execução de Divide pode deixar cerca de 0.2n elementos em um dos subvetores e cerca de 0.8n elementos no outro. (Estamos desprezando o fato de que a soma dos tamanhos dos dois subvetores é n − 1 e não n.) Outra execução (já com valor diferente de n) pode deixar cerca de 0.99n elementos em um dos subvetores e cerca de 0.01n elementos no outro. E assim por diante. Isso garante um número linearítmico de comparações por motivo análogo ao do melhor caso.
Para dar uma ilustração concreta, suponha que todas as execuções de Divide dividem o vetor na proporção 1/9-para-8/9. Nesse caso, o número de comparações, digamos R(n), satisfaz uma recorrência semelhante a
R(n) = R(n/9) + R(8n/9) + n .
(Compare com a correspondente recorrência do melhor caso.) (Nessa ilustração, estamos sendo vagos a respeito dos possíveis valores de n. Quem sabe deveríamos supor que n é racional e R(n) = 0 para todo n entre 0 e 1.) Uma indução grosseira mostra que a solução da recorrência satisfaz a cota superior R(n) ≤ n log9/8 n . Com efeito, tomando sempre logaritmos na base 9/8, temos
| R(n) | = | R(n/9) + R(8n/9) + n |
| ≤ | (n/9) log (n/9) + (8n/9) log (8n/9) + n | |
| ≤ | (n/9 + 8n/9) log (8n/9) + n | |
| = | n log (8n/9) + n | |
| = | n log n + n log (8/9) + n | |
| = | n log n − n + n | |
| = | n log n . |
Portanto, R(n) ≤ n log9/8 n . Como log9/8 n < 5.89 log2 n, temos R(n) ≤ 6 n lg n. Em resumo, R(n) = Ο(n lg n), ainda que a constante escondida sob a notação Ο seja maior que a do melhor caso.
As seções anteriores mostraram o efeito negativo que um mau pivô tem sobre o número de comparações que Quicksort faz. (Veja, em particular, o que acontece quando o pivô é sistematicamente o menor elemento do vetor.) Para tentar evitar um mau pivô, podemos escolher o pivô aleatoriamente. Essa ideia leva a uma versão aleatorizada (= randomized) de Divide e Quicksort:
| Rand-Divide (A, p, r) |
| 1 . i := Random (p, r) |
| 2 . troca A[i] com A[r] |
| 3 . q := Divide (A, p, r) |
| 4 . devolva q |
| Rand-Quicksort (A, p, r) |
| 1 . se p ≤ r |
| 2 .ooo q := Rand-Divide (A, p, r) |
| 3 .ooo Rand-Quicksort (A, p, q − 1) |
| 4 .ooo Rand-Quicksort (A, q + 1, r) |
O algoritmo auxiliar Random
escolhe um número aleatório no intervalo p .. r
de modo que todos os números do intervalo sejam igualmente prováveis.
Existem implementações de Random
que conseguem uma boa aproximação do igualmente prováveis
e consomem uma quantidade de tempo constante, ou seja,
independente de p e r.
Não faz sentido discutir o desempenho de Rand-Quicksort no pior caso nem no melhor caso. Devemos tratar do desempenho esperado, ou seja, do número esperado de comparações.
O ponto de partida para o cálculo do número esperado de comparações é a seguinte observação fundamental: o número de comparações que o algoritmo executa não depende dos valores dos elementos do vetor A[p .. r] mas apenas do índice de seu menor elemento, do índice do segundo menor elemento, do índice do terceiro menor elemento, etc. Assim, por exemplo, o vetor [88 55 99 22] é equivalente ao vetor [3 2 4 1]. Podemos, portanto, restringir nossa atenção aos vetores cujos elementos pertencem ao conjunto 1 .. n, sendo n o número de elementos do vetor. Para tornar as coisas mais simples, suporemos também que os elementos do vetor são distintos dois a dois, e portanto que A[1 .. n] é uma permutação de 1 .. n.
| 1, 2, 3 | 3 |
| 1, 3, 2 | 2 |
| 2, 1, 3 | 3 |
| 2, 3, 1 | 3 |
| 3, 1, 2 | 2 |
| 3, 2, 1 | 3 |
Exemplo E: A tabela mostra o número médio de comparações para cada uma das 3! permutações de 1 .. 3. O número total é 3 + 2 + 3 + 3 + 2 + 3 = 16. Portanto, o número médio é 16/6. Veja a seguir, para alguns valores de n, o número médio de comparações para todas as n! permutações de 1 .. n:
| n | comparações | ||
| 0 | 0 | / | 1 |
| 1 | 0 | / | 1 |
| 2 | 2 | / | 2 |
| 3 | 16 | / | 6 |
| 4 | 116 | / | 24 |
| 5 | 888 | / | 120 |
| 6 | 7416 | / | 720 |
| 7 | 67968 | / | 5040 |
Suponha que A[p .. r] é uma permutação aleatória de 1 .. n e seja E(n) o número esperado de comparações que Rand-Quicksort executa supondo que todas as n! permutações são igualmente prováveis. (Em outras palavras, E(n) é o número médio de comparações para as n! permutações de 1 .. n. Veja a página Análise probabilística e algoritmos aleatorizados.) Um cálculo probabilístico cuidadoso (veja o capítulo 7 de CLRS e um dos exercícios abaixo) mostra que
| E(n) = ∑1 ≤ i < n ∑ i+1 ≤ j ≤ n | 2 | . |
| j − i + 1 |
Por exemplo, E(4) = (2/2 + 2/3 + 2/4) + (2/2 + 2/3) + (2/2) = 116/24. A segunda somatória da fórmula é essencialmente o dobro de um número harmônico e portanto
E(n) = Θ(n lg n).
Esse resultado é consistente com a discussão na seção anterior sobre o desempenho médio do Quicksort não aleatorizado.
Exemplo F: A tabela mostra os valores de E(n) para n de 0 a 7. Verifique esses números! Escreva os números em notação ponto-flutuante.
| n | E(n) | ||
| 0 | 0 | / | 1 |
| 1 | 0 | / | 1 |
| 2 | 2 | / | 2 |
| 3 | 16 | / | 6 |
| 4 | 116 | / | 24 |
| 5 | 888 | / | 120 |
| 6 | 7416 | / | 720 |
| 7 | 67968 | / | 5040 |
a+b+c=d, sendo a o número de comparações da primeira aplicação de Divide, sendo b o número total de comparações que Quicksort executa ao ser aplicado ao vetor A[p .. q−1]; sendo c o número total de comparações que Quicksort executa ao ser aplicado ao vetor A[q+1 .. r]; e sendo d o valor da soma a+b+c. (Dica: Para calcular b e c, use as tabelas de n−1, n−2, etc.)
[2 1 3] [2 1] 3 2+1+0=3
| E(n) = n − 1 + | 2 | ∑0 ≤ i < n E(i) . |
| n |
Suponha que E(0) = 0 e calcule E(n) para n = 1, 2, 3, 4, 5. Compare o resultado com o do exercício Números de comparações para todas as permutações.