Quicksort

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, isto é, 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.  O algoritmo é muito rápido em geral, mas é lento em algumas raras instâncias especiais.  O algoritmo consome tempo proporcional a  n log(n)  em média e proporcional a  n²  no pior caso.

Usaremos duas abreviaturas ao discutir o algoritmo.  A expressão  "v[h..j] ≤ x"  será usada como abreviatura de  "v[i] ≤ x para todo i no conjunto de índices h..j".  Analogamente, a expressão  "v[h..j] ≤ v[k..m]"  será interpretada como "v[i] ≤ v[l] para todo i no conjunto h..j e todo l no conjunto k..m".

Veja o verbete Quicksort na Wikipedia.   Veja também minha página "Análise do Quicksort".  Veja também o capítulo 11 do "Programming Pearls".

O problema da separação

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 deste problema é a escolha de um "pivô", 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 cada uma das duas partes do vetor rearranjado seja estritamente menor que o vetor todo.  A dificuldade está em construir um algoritmo que resolva o problema de maneira rápida e não use vetor auxiliar.

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.   Outra formulação concreta do problema:  rearranjar v[p..r] de modo que

v[p..j-1]  ≤  v[j]  <  v[j+1..r]

para algum j em p..r.  Esta página usa a segunda formulação; outras formulações são mencionadas nos exercícios.

Exercícios preliminares

O algoritmo da separação

Eis como D. Gries [The Science of Programming, 1981, pag.345] escreve o algoritmo 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
   v[p] = v[j], v[j] = c;                         // 9
   return j;                                      // 10
}

A função 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] .

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

Eis algumas perguntas que chamam a atenção para detalhes importantes:  Que acontece se executarmos a função com p igual a r?  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?

O algoritmo da separação: análise

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                 
   v[p] = v[j], v[j] = c;
   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:

• i == j+1
• p ≤ j ≤ r
• v[p+1..j] ≤ c  e  v[j+1..r] > c.

Portanto,  v[p..j-1] ≤ v[j] < v[j+1..r]  na fim da execução da função.

O algoritmo da separação: desempenho

Qual o desempenho da função separa?  Quanto tempo a função consome?   O consumo de tempo é proporcional ao número de comparações entre elementos do vetor e portanto proporcional ao número

r - p + 1

de elementos do vetor.

Exercícios

Quicksort básico

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".

// A função recebe um vetor v[p..r], com p <= r+1,
// e rearranja o vetor em ordem crescente.

void quicksort( int v[], int p, int r)
{
   int j;                         // 1
   if (p < r) {                   // 2
      j = separa( v, p, r);       // 3
      quicksort( v, p, j-1);      // 4
      quicksort( v, j+1, r);      // 5
   }
}

(Note que a função está correta mesmo quando p > r, ou seja, quando o vetor está vazio.)

Quicksort básico: desempenho

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 número de elementos do vetor.  Caso contrário, o número de comparações estará na ordem de  n² .  (Isso acontece, por exemplo, se o vetor já estiver ordenado ou quase ordenado.)  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 minha página "Análise do Quicksort".)

Exercícios

Quicksort: altura da pilha de execução

Na versão básica do Quicksort, o código cuida imediatamente do subvetor v[p..j-1] e trata do subvetor v[j+1..r] somente depois que v[p..j-1] estiver ordenado.  Dependendo do valor de j nas sucessivas invocações da função, a pilha de execução pode crescer muito, atingindo altura  n := r-p+1 .  (Isso acontece, por exemplo, se o vetor estiver em ordem decrescente.)  O fenômeno não afeta o consumo de tempo do algoritmo, mas pode esgotar o espaço de memória.  Para controlar o crescimento da pilha de execução é preciso tomar duas providências:

1. cuidar primeiro do menor dos subvetores v[p..j-1] e v[j+1..r]  e
2. eliminar a segunda invocação recursiva da função (veja exercício acima).

Se adotarmos estas providências, o tamanho do subvetor que está no topo da pilha de execução será menor que a metade do tamanho do subvetor que está logo abaixo na pilha.  De modo mais geral, o subvetor que está em qualquer das posições da pilha de execução será menor que metade do subvetor 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], 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;
      }
   }
}

Animações do Quicksort

• Sorting Algorithms Animation by David R. Martin
• Demonstração animada do Quicksort, copiada da página da disciplina COS226 de R. Sedgewick (Universidade de Princeton)
• Página Sorting Algorithms, mantida por Jason Harrison na Universidade de British Columbia
• Sorting Algorithms, página de Pat Morin na Universidade de Carlton, Canadá
• Quick-sort with Hungarian (Küküllömenti legényes) folk dance, created at Sapientia University (Romania)

APÊNDICE: outras formas do Quicksort

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.  (Em todas as implementações abaixo, o mecanismo de controle da altura da pilha de execução foi omitido para tornar o código mais legível.)

1. A versão abaixo começa por rearranjar v[p..r] de modo que   v[p..i-1] ≤ v[i] ≤ v[i+1..r]    e    p ≤ i ≤ r   (compare com o resultado da separação feita acima).

   // A função rearranja o vetor v[p..r], com p <= r+1,
   // de modo que ele fique em ordem crescente.
   
   void quick_FlipFlop( int v[], int p, int r)
   {
      int i, j, t, ff;
      if (p < r) {      
         i = p, j = r;
         ff = -1;
         while (i < j) {
            if (v[i] > v[j] {
               t = v[i], v[i] = v[j], v[j] = t;
               ff = -ff;
            }
            if (ff == -1) --j;
            else ++i;
         }
         quick_FlipFlop( v, p, i-1);
         quick_FlipFlop( v, i+1, r);
      }
   }
   

2. 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 quick_CLR( 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;
         }
         quick_CLR( v, p, j);
         quick_CLR( v, j+1, r);
      }
   }
   

3. Eis outra 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 quick_S( 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;
            }
         }
         quick_S( v, p, j);
         quick_S( v, i, r);
      }
   }
   

   Exercício: formule com precisão o subproblema da separação que quick_S resolve.

4. A seguinte implementação do Quicksort é sugerida no livro de Sedgewick (página 307).

   #define troca( A, B) { int t = A; A = B; B = t; } 
   void quick_S2( int v[], int p, int r) {
       if (p < r) {
          int i = p-1, j = r, c = v[r];
          while (1) { 
              while (v[++i] < c) ;
              while (c < v[--j]) if (j == p) break;
              if (i > j) break;
              troca( v[i], v[j]);
          }
          troca( v[i], v[r]);
          quick_S2( v, p, j);
          quick_S2( v, i+1, r);
       }
   }
   

Exercícios