Considere problema de permutar os elementos de um vetor v[0 .. n-1] de modo que ele fique em ordem crescente, ou seja, o problema de rearranjar o vetor de tal modo que tenhamos v[0] ≤ . . . ≤ v[n-1]. Alguns algoritmos simples para o problema são quadráticos, ou seja, consomem uma quantidade de tempo proporcional a n2. O algoritmo Quicksort, inventado por C.A.R. Hoare em 1962, é, em geral, mais rápido.
Em algumas raras instâncias, o Quicksort pode ser tão lento quanto os algoritmos elementares; mas em geral é muito mais rápido. Mais exatamente, o algoritmo é linearítmico em média mas quadrático no pior caso.
Usaremos duas abreviaturas ao discutir o algoritmo.
A expressão
v[i..k] ≤ x
será usada como abreviatura de
v[j] ≤ x para todo j
no conjunto de índices i..k
.
A expressão
v[i..k] ≤ v[p..r]
será interpretada como
v[j] ≤ v[q]
para todo j no conjunto i..k
e todo q no conjunto p..r
.
Sumário:
O núcleo do algoritmo Quicksort é o seguinte problema da separação (= partition subproblem), que formularemos de maneira propositalmente vaga:
rearranjar um vetor 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 desse problema
é a escolha de um pivô (ou fulcro),
digamos c .
Os elementos do vetor que forem maiores que c
serão considerados grandes e os demais serão considerados pequenos.
É importante escolher c
de tal modo que as duas partes do vetor rearranjado sejam
estritamente menores que o vetor todo.
A dificuldade está em resolver o problema da separação
rápidamente sem usar um vetor auxiliar
(como espaço de trabalho
).
O problema da separação admite muitas formulações concretas. Eis uma primeira: rearranjar v[p..r] de modo que tenhamos v[p..j] ≤ v[j+1..r] para algum j em p..r-1. (Nessa formulação, o pivô não é explícito.) Eis uma segunda formulação: rearranjar v[p..r] de modo que
v[p..j-1] ≤ v[j] < v[j+1..r]
para algum j em p..r. (Aqui, v[j] é o pivô.) Exemplo:
j | |||||||||
666 | 222 | 111 | 777 | 555 | 444 | 555 | 777 | 999 | 888 |
Neste capítulo, usaremos a segunda formulação do problema da separação.
v[j..r] > 0por
v[j..r] ≥ 0. Faz sentido exigir que v[j] seja 0?
int sep (int v[], int p, int r) { int j = r; for (int i = r-1; i >= p; i--) if (v[i] > v[r]) { int t = v[r]; v[r] = v[i]; v[i] = t; j = i; } return j; }
int sep (int v[], int p, int r) {
int w[1000], i = p, j = r, c = v[r];
for (int k = p; k < r; ++k)
if (v[k] <= c) w[i++] = v[k];
else w[j--] = v[k];
// agora i == j
w[j] = c;
for (int k = p; k <= r; ++k) v[k] = w[k];
return j; }
int sep (int v[], int p, int r) { int i = p, j = r; int q = (p + r)/2; do { while (v[i] < v[q]) ++i; while (v[j] > v[q]) --j; if (i <= j) { int t = v[i], v[i] = v[j], v[j] = t; ++i, --j; } } while (i <= j); return i; }
Mostre um exemplo em que essa função
não dá o resultado prometido.
E se trocarmos return i
por
return i-1
?
É possível fazer algumas poucas correções
de modo que a função dê o resultado esperado?
Eis como o livro de Cormen, Leiserson, Rivest e Stein implementa o algoritmo da separação. (A implementação é atribuída a N. Lomuto.) A função resolve a segunda formulação do problema da separaçã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]. static int separa (int v[], int p, int r) { int c = v[r]; // pivô int t, j = p; for (int k = p; /*A*/ k < r; ++k) if (v[k] <= c) { t = v[j], v[j] = v[k], v[k] = t; ++j; } t = v[j], v[j] = v[r], v[r] = t; return j; }
(A palavra-chave static está aí apenas para indicar que separa é uma função auxiliar e não deve ser invocada diretamente pelo usuário final do Quicksort.)
Para mostrar que a função separa está correta, basta verificar que no início de cada iteração — ou seja, a cada passagem pelo ponto A — temos a seguinte configuração:
p | j | k | r | ||||||
≤ c | ≤ c | ≤ c | > c | > c | ? | ? | ? | ? | c |
(Note que podemos ter j == p bem como k == j, ou seja, o primeiro ou o segundo segmento do vetor podem estar vazios.) Mais exatamente, valem os seguintes invariantes: no início de cada iteração,
Na última passagem pelo ponto A, teremos k == r e portanto a seguinte configuração:
p | j | k | |||||||
≤ c | ≤ c | ≤ c | ≤ c | ≤ c | > c | > c | > c | > c | c |
Assim, na fim da execução da função, teremos p ≤ j ≤ r e v[p..j-1] ≤ v[j] < v[j+1..r], como prometido.
p | j | r | |||||||
≤ c | ≤ c | ≤ c | ≤ c | ≤ c | c | > c | > c | > c | > c |
Gostaríamos j que ficasse a meio caminho entre p e r, mas devemos estar preparados para aceitar os casos extremos em que j vale p ou r.
Desempenho. Quanto tempo a função separa consome? O consumo de tempo é proporcional ao número de comparações entre elementos do vetor. Não é difícil perceber que esse número é proporcional ao tamanho r - p + 1 do vetor. A função é, portanto, linear.
int separa_Gries (int v[], int p, int r) { int c = v[p], i = p+1, j = r; while (true) { while (i <= r && v[i] <= c) ++i; while (c < v[j]) --j; if (i >= j) break; int t = v[i], v[i] = v[j], v[j] = t; ++i; --j; } v[p] = v[j], v[j] = c; return j; }
int sep (int v[], int p, int r) { int c = v[p], i = p+1, j = r; while (i <= j) { if (v[i] <= c) ++i; else { int t = v[i], v[i] = v[j], v[j] = t; --j; } } v[p] = v[j], v[j] = c; return j; }
int separa_R (int v[], int p, int r) { int c = v[p], i = p+1, j = r; while (1) { while (i < j && c < v[j]) --j; while (i < j && v[i] <= c) ++i; if (i == j) break; int t = v[i], v[i] = v[j], v[j] = t; } if (v[j] > c) return p; v[p] = v[j], v[j] = c; return j; }
Agora que resolvemos o problema da separação,
podemos cuidar do Quicksort propriamente dito.
O algoritmo usa a estratégia da
divisão e conquista
e tem a aparência de um Mergesort
ao contrário
:
// Esta função rearranja qualquer vetor // v[p..r] em ordem crescente. void quicksort (int v[], int p, int r) { if (p < r) { // 1 int j = separa (v, p, r); // 2 quicksort (v, p, j-1); // 3 quicksort (v, j+1, r); // 4 } }
Se p ≥ r (essa é a base recursão) não é preciso fazer nada. Se p < r, o código reduz a instância v[p..r] do problema ao par de instâncias v[p..j-1] e v[j+1..r]. Como p ≤ j ≤ r, essas duas instâncias são estritamente menores que a instância original. Assim, por hipótese de indução, v[p..j-1] estará em ordem crescente no fim da linha 3 e v[j+1..r] estará em ordem crescente no fim da linha 4. Como v[p..j-1] ≤ v[j] < v[j+1..r] graças à função separa, o vetor todo estará em ordem crescente no fim da linha 4, como promete a documentação da função.
Podemos eliminar a segunda chamada recursiva (linha 4) e trocar o if por um while. Isso produz uma função equivalente ao quicksort acima:
void qcksrt (int v[], int p, int r) { while (p < r) { int j = separa (v, p, r); qcksrt (v, p, j-1); p = j + 1; } }
p < rpor
p != rna linha 1 do quicksort? Que acontece se trocarmos
j-1por
jna linha 3 do código? Que acontece se trocarmos
j+1por
jna linha 4?
quicksort (v,1,4) quicksort (v,1,2) quicksort (v,1,0) quicksort (v,2,2) quicksort (v,4,4)
Repita o exercício com o vetor v[1..6] = 55 44 22 11 66 33 .
void qsrt (int v[], int p, int r) { int j = separa (v, p, r); if (p < j-1) qsrt (v, p, j-1); if (j+1 < r) qsrt (v, j+1, r); }
A animação à direita (copiada da Simon Waldherr / Golang Sorting Visualization) mostra a aplicação do Quicksort a um vetor v[0..79] de números positivos. Cada elemento v[i] do vetor é representado pelo ponto de coordenadas (i, v[i]).
A primeira das figuras abaixo (copiada da Wikimedia) mostra a aplicação do Quicksort a uma permutação v[0..249] do conjunto 0..249. A figura mostra o estado do vetor em 8 momentos da ordenação. A segunda figura (copiada da Wikipedia) mostra a aplicação do Quicksort a uma permutação v[0..32] do conjunto 0..32.
Veja outras animações de algoritmos de ordenação:
Não é difícil perceber que 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, o número de comparações será aproximadamente n log n , sendo n o tamanho r-p+1 do vetor. Por outro lado, se o vetor já estiver ordenado ou quase ordenado, o número de comparações será aproximadamente
n2 .
Portanto, o pior caso do quicksort não é melhor que o dos algoritmos elementares. Felizmente, o pior caso é muito raro: em média, o consumo de tempo do quicksort é proporcional a
n log n .
(Veja detalhes na página Análise do Quicksort do meu sítio Análise de Algoritmos.) Portanto, o algoritmo é linearítmico em média e quadrático no pior caso.
truncada. Escreva uma versão do algoritmo Quicksort com cutoff para vetores pequenos: quando o vetor a ser ordenado tiver menos que M elementos, a ordenação passa a ser feita pelo algoritmo Insertionsort. O valor de M pode ficar entre 10 e 20. (Esse truque é usado na prática porque o algoritmo Insertionsort é mais rápido que o Quicksort puro quando o vetor é pequeno. O fenômeno é muito comum: algoritmos sofisticados são tipicamente mais lentos que algoritmos simplórios quando o volume de dados é pequeno.)
void psort (int v[], int p, int r) { if (p >= r) return; if (v[p] > v[r]) { int t = v[p], v[p] = v[r], v[r] = t; } psort (v, p, r-1); psort (v, p+1, r); }
Na versão básica do Quicksort, o código cuida imediatamente do segmento v[p..j-1] e trata do segmento v[j+1..r] somente depois que v[p..j-1] estiver ordenado. Dependendo do valor de j nas sucessivas chamadas da função, a pilha de execução pode crescer muito, atingindo altura igual ao tamanho do vetor. (Isso acontece, por exemplo, se o vetor estiver em ordem decrescente.) Esse fenômeno pode esgotar o espaço de memória. Para controlar o crescimento da pilha de execução é preciso tomar duas providências:
Se adotarmos essas providências, o tamanho do segmento que está no topo da pilha de execução será menor que a metade do tamanho do segmento que está logo abaixo na pilha. De modo mais geral, o segmento que está em qualquer das posições da pilha de execução será menor que metade do segmento que está imediatamente abaixo. Assim, se a função for aplicada a um vetor com n elementos, a altura da pilha não passará de log n.
// A função rearranja o vetor v[p..r]
// em ordem crescente.
void
quickSort (int v[], int p, int r)
{
while (p < r) {
int 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 quicks (int v[], int p, int r) { if (p < r) { int j = separa (v, p, r); if (j - p < r - j) { quicks (v, p, j-1); quicks (v, j+1, r); } else { quicks (v, j+1, r); quicks (v, p, j-1); } } }