O problema desta página é o mesmo das três páginas anteriores: Rearranjar um vetor v[0..n-1] (ou seja, permutar os elementos do vetor) de modo que ele fique em ordem crescente, ou seja, de modo que tenhamos v[0] ≤ ... ≤ v[n-1].
O algoritmo Quicksort, inventado por C.A.R. Hoare [Computer Journal, 5, pp.10-15, 1962], resolve o problema. Ele é muito rápido em média, mas lento no pior caso; felizmente, o pior caso é raro. O algoritmo consome tempo proporcional a n log(n) em média e a n2 no pior caso.
Veja o verbete Quicksort na Wikipedia.
v[p..j-1] ≤ 0 e v[j..r] > 0 .
A expressão "v[p..j-1] ≤ 0" significa "v[i] ≤ 0 para todo i no conjunto p..j-1". Faz sentido exigir que j esteja em p..r? Não use vetor auxiliar. Procure fazer uma função rápida. Repita o exercício depois de trocar "v[j..r] > 0" por "v[j..r] > 0". Faz sentido exigir que v[j] seja 0?
v[p..j-1] ≤ v[j] < v[j+1..r] .
Escreva um algoritmo que decida se v[p..r] está arrumado. Em caso afirmativo, o seu algoritmo deve devolver o valor de j.
O coração do Quicksort é o problema da separação (= partition subproblem), que formularemos de maneira propositalmente vaga: rearranjar v[p..r] de modo que todos os elementos pequenos fiquem na parte esquerda do vetor e todos os elementos grandes fiquem na parte direita.
O ponto de partida para a solução do subproblema é a escolha de uma "chave", digamos c: os elementos do vetor que forem maiores que c serão considerados grandes e os demais serão considerados pequenos. A dificuldade está em escolher c de tal modo que cada uma das duas partes do vetor rearranjado seja estritamente menor que o vetor todo.
Eis como D. Gries [The Science of Programming, 1981, pag.345] escreve o subalgoritmo da separação:
int separa (int v[], int p, int r)
{
int c = v[p], i = p+1, j = r, t; // 1
while (1) { // 2
while (i <= r && v[i] <= c) ++i; // 3
while (c < v[j]) --j; // 4
if (i >= j) break; // 5
t = v[i]; v[i] = v[j]; v[j] = t; // 6
++i; --j; // 7
} // 8
t = v[p]; v[p] = v[j]; v[j] = t; // 9
return j; // 10
}
Esta função separa só faz sentido se p < r. Ela devolve um elemento j do conjunto p..r depois de rearranjar o vetor v[p..r] de tal que de modo que
v[p..j-1] ≤ v[j] < v[j+1..r] .
(Minha taquigrafia deve ser interpretada com cuidado: a expressão "v[p..j-1]≤v[j]", por exemplo, significa "v[i]≤v[j] para todo i no conjunto p..j-1".) Gostaríamos que j ficasse a meio caminho entre p e r, mas devemos estar preparados para aceitar os casos extremos j == p e j == r.
| p | j | r | |||||||
| ≤ c | ≤ c | ≤ c | ≤ c | = c | > c | > c | > c | > c | > c |
(Como se vê, a função acima foge um pouco da formulação vaga do subproblema: além de uma parte esquerda v[p..j-1] e de uma parte direita v[j+1..r], o vetor rearranjado tem um "centro" v[j].)
Eis algumas perguntas que chamam a atenção para detalhes importantes: Que acontece se eliminarmos "i <= r" na linha 3? Por que não há um "j >= p" na linha 4? Que acontece se escrevermos "i > j" na linha 5? Que acontece se trocarmos "j" por "i" nas linhas 9 e 10?
Eu prefiro escrever a função separa de maneira um pouco diferente, para facilitar a análise de sua correção:
// Recebe vetor v[p..r] com p < r. Rearranja os // elementos do vetor e devolve j em p..r tal que // v[p..j-1] <= v[j] < v[j+1..r]. int separa (int v[], int p, int r) { int c = v[p], i = p+1, j = r, t; while (/*A*/ i <= j) { if (v[i] <= c) ++i; else if (c < v[j]) --j; else { t = v[i]; v[i] = v[j]; v[j] = t; ++i; --j; } } // agora i == j+1 t = v[p]; v[p] = v[j]; v[j] = t; return j; }
No início de cada iteração, ou seja, a cada passagem pelo ponto A, temos a seguinte configuração:
| p | i | j | r | ||||||
| = c | ≤ c | ≤ c | ? | ? | ? | ? | ? | > c | > c |
Na penúltima passagem por A, teremos
| p | i=j | r | |||||||
| = c | ≤ c | ≤ c | ≤ c | ≤ c | ? | > c | > c | > c | > c |
Na última passagem por A valem as seguintes relações:
Portanto, v[p..j-1] ≤ v[j] < v[j+1..r] na fim da execução da função.
Qual o desempenho da função separa? Quanto tempo a função consome? Esse tempo é proporcional ao número de comparações entre elementos do vetor. E esse número é essencialmente igual ao
número de elementos do vetor,
ou seja, r - p + 1 .
int separa (int v[], int p, int r) {
int w[1000], i = p, j = r, c = v[p], k;
for (k = p+1; k <= r; ++k)
if (v[k] <= c) w[i++] = v[k];
else w[j--] = v[k];
// agora i == j
w[i] = c;
for (k = p; k <= r; ++k) v[k] = w[k];
return i;
}
int separa (int v[], int p, int r) {
int c = v[p], i = p+1, j = r;
while (i <= j) {
if (v[i] <= c) ++i;
else {
troca (v[i], v[j]);
--j;
}
}
v[p] = v[j], v[j] = c;
return j;
}
int separa (int v[], int p, int r) {
int c = v[p], i = p+1, j = r;
while (i <= j) {
if (v[i] <= c) {
v[i-1] = v[i];
++i;
}
else {
troca (v[i], v[j]);
--j;
}
}
v[j] = c;
return j;
}
int separa (int v[], int p, int r) {
int j;
j = (p + r) / 2;
do {
while (v[p] < v[j]) p++;
while (v[r] > v[j]) r--;
if (p <= r) {
troca (v[p], v[r]);
p++, r--;
}
} while (p <= r)
return p;
}
Mostre um exemplo onde essa função não dá o resultado esperado. E se trocarmos "return p" por "return p-1"? É possível fazer algumas poucas correções de modo que a função dê o resultado esperado?
struct celula {
int chave;
struct celula *prox;
} ;
Escreva uma função que transforme a lista em duas: a primeira contendo as células cuja chave é par e a segunda aquelas cuja chave é impar.
Agora que resolvemos o problema da separação, podemos cuidar do Quicksort propriamente dito. O algoritmo se assemelha a um Mergesort "de trás pra diante". Nosso algoritmo recebe um vetor v[p..r], possivelmente com p > r, e rearranja o vetor de modo que ele fique em ordem crescente.
// A função rearranja o vetor v[p..r]
// de modo que ele fique em ordem crescente.
// A função aceita qualquer p <= r+1.
void quicksort (int v[], int p, int r)
{
int j;
if (p < r) {
j = separa (v, p, r);
quicksort (v, p, j-1);
quicksort (v, j+1, r);
}
}
Poderíamos eliminar o segundo apelo à recursão e reescrever a função assim:
void quicksort (int v[], int p, int r)
{
int j;
while (p < r) {
j = separa (v, p, r);
quicksort (v, p, j-1);
p = j + 1;
}
}
O consumo de tempo da função quicksort é proporcional ao número de comparações entre elementos do vetor. Se o índice j devolvido por separa estiver sempre mais-ou-menos a meio caminho entre p e r então o número de comparações será aproximadamente n log2n , sendo n o número de elementos do vetor. Caso contrário, o algoritmo pode consumir tempo proporcional a n2.
Em média, o consumo de tempo do quicksort é
proporcional a n log n ,
onde n é r-p+1. Mas no pior caso — em particular, se o vetor dado já estiver ordenado ou quase-ordenado — o consumo de tempo é proporcional a n2, ou seja, tão elevado quanto o dos algoritmos elementares.
#define troca(A, B) { int t = A; A = B; B = t; }
void quicksort (int a[], int p, int r) {
if (p < r) {
int i = p-1, j = r, v = a[r];
while (1) {
while (a[++i] < v) ;
while (v < a[--j]) if (j == p) break;
if (i > j) break;
troca (a[i], a[j]);
}
troca (a[i], a[r]);
quicksort (a, p, j);
quicksort (a, i+1, r);
}
}
Nas duas versões do Quicksort vistas acima, o algoritmo cuida imediatamente da parte esquerda do vetor, enquanto o resto do problema é colocado na pilha da recursão. (Poderia, igualmente bem, tem feito o contrário.) Com isso, a pilha de recursão pode crescer muito (por exemplo, se o vetor estiver em ordem decrescente), atingindo tamanho n . Isso não afeta o consumo de tempo do algoritmo, mas pode esgotar o espaço de memória.
O remédio está na seguinte política: processe imediatamente a parte menor do vetor, deixando a outra parte na pilha. Com isso, cada subproblema que está na pilha é menor ou igual que a metade do subproblema que está logo abaixo na pilha. Resultado: o tamanho da pilha nunca passa de log2n.
Eis o resultado dessa política aplicada à versão recursiva:
// A função rearranja o vetor v[p..r], com p <= r+1,
// de modo que ele fique em ordem crescente.
void quicksort (int v[], int p, int r)
{
int j;
while (p < r) {
j = separa (v, p, r);
if (j - p < r - j) {
quicksort (v, p, j-1);
p = j + 1;
} else {
quicksort (v, j+1, r);
r = j - 1;
}
}
}
void quicksort (int v[], int p, int r) {
int j;
if (p < r) {
j = separa (v, p, r);
if (j - p < r - j) {
quicksort (v, p, j-1);
quicksort (v, j+1, r);
} else {
quicksort (v, j+1, r);
quicksort (v, p, j-1);
}
}
}
v[p..j] ≤ v[j+1..r].
Escreva uma versão do quicksort que use essa implementação do separa. Que restrições devem ser impostas sobre j?
A algoritmo Quicksort pode ser escrito de várias outras maneiras, diferentes da discutida acima. A diferença entre as várias versões está no modo de resolver o subproblema da separação.
A versão abaixo (Cormen, Leiserson e Rivest, Introduction to Algorithms, 1991) começa por rearranjar v[p..r] de modo que
v[p..j] ≤ v[j+1..r] e p ≤ j < r
(compare com o resultado da separação feita acima). Note que os tamanhos dos vetores v[p..j] e v[j+1..r] são ambos estritamente menores que o tamanho do vetor original.
// A função rearranja o vetor v[p..r], com p <= r+1,
// de modo que ele fique em ordem crescente.
void quickCLR (int v[], int p, int r)
{
int c, i, j, t;
if (p < r) {
c = v[p];
i = p-1, j = r+1;
while (1) {
do --j; while (v[j] > c);
do ++i; while (v[i] < c);
if (i >= j) break;
t = v[i], v[i] = v[j], v[j] = t;
}
quickCLR (v, p, j);
quickCLR (v, j+1, r);
}
}
(O mecanismo de controle do tamanho da pilha de recursão foi omitido para tornar o código mais legível.)
Eis mais uma implementação (se não me engano, ela consta do livro de Sedgewick).
// A função rearranja o vetor v[p..r], com p <= r+1,
// de modo que ele fique em ordem crescente.
void quickSedg (int v[], int p, int r) {
int c, i, j, t;
if (p < r) {
c = v[(p+r)/2];
i = p, j = r;
while (i <= j) {
while (v[i] < c) ++i;
while (c < v[j]) --j;
if (i <= j) {
t = v[i], v[i] = v[j], v[j] = t;
++i, --j;
}
}
quickSedg (v, p, j);
quickSedg (v, i, r);
}
}
Exercício: formule com precisão o subproblema da separação que quickSedg resolve.
(Convém acrescentar a esta versão o mecanismo de controle do tamanho da pilha de recursão que já discutimos acima.)