Quicksort

[auto_racing_-_car_04.gif]

O problema da ordenação consiste em rearranjar um vetor v[0..n-1] em ordem crescente, ou seja, permutar os elementos do vetor de modo que tenhamos v[0]v[1] ≤ . . . ≤ v[n-1].   O algoritmo Quicksort, inventado por C.A.R. Hoare em 1962, resolve o problema.

Em algumas raras instâncias, o Quicksort pode ser tão lento quanto os algoritmos elementares; mas em geral é muito mais rápido.  Mais precisamente, o algoritmo consome tempo proporcional a  n log n  em média e proporcional a  n2  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.  Analogamente, 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.

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ô (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 de maneira rápida sem usar muito 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 outra 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ô.)   Neste capítulo, usaremos a segunda formulação.  Segue um exemplo do resultado da separação:

777 222 111 777 999 444 555 666 555 888
              j    
666 222 111 777 555 444 555 777 999 888

Exercícios 1

  1. Positivos e negativos.  Escreva uma função que rearranje um vetor v[p..r] de números inteiros de modo que tenhamos   v[p..j-1] ≤ 0   e   v[j..r] > 0   para algum j em p..r+1.  Faz sentido exigir que j esteja em p..r?  Procure escrever uma função rápida que não use vetor auxiliar.   Repita o exercício depois de trocar v[j..r] > 0 por v[j..r] ≥ 0.  Faz sentido exigir que v[j] seja 0?
  2. Lista.  Suponha dada uma lista encadeada que armazena números inteiros.  Escreva uma função que transforme a lista em duas: a primeira contendo os números pares e a segunda contendo os ímpares.
  3. Critique a seguinte tentativa de resolver o problema da separação:
    int sep (int v[], int p, int r) {
       int i, t;
       for (i = p+1; i <= r; i++) 
          if (v[p] > v[i]) {
             t = v[p]; v[p] = v[i]; v[i] = t; }   
       return p; }
    
  4. Critique a seguinte solução do problema da separação:
    int sep (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; }
    
  5. Um programador inexperiente afirma que a seguinte função resolve a primeira formulação do problema da separação, ou seja, rearranja qualquer vetor v[p..r] (com p < r) de tal forma que v[p..i] ≤ v[i+1..r] para algum i em p..r-1.
    int sep (int v[], int p, int r) {
       int q, i, j, t;
       i = p; q = (p + r) / 2; j = r;
       do {
          while (v[i] < v[q]) ++i;
          while (v[j] > v[q]) --j;
          if (i <= j) {
             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?

  6. ⚠ Digamos que um vetor v[p..r] está separado se existe j em p..r tal que  v[p..j-1] ≤ v[j] < v[j+1..r].  Escreva um algoritmo que decida se v[p..r] está separado. Em caso afirmativo, o seu algoritmo deve devolver o índice j.

O algoritmo da separação

Eis como D. Gries (The Science of Programming, 1981, pag.345) implementa o algoritmo da separação.  A função rearranja o vetor v[p..r] e devolve um elemento j do conjunto 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;         // 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
}

Gostaríamos que j ficasse a meio caminho entre pr, mas devemos estar preparados para aceitar os casos extremos em que j vale p ou r.

p       j         r
≤ c ≤ c ≤ c ≤ c c > c > c > c > c > c

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 910?

Análise do algoritmo da separação.   Eu prefiro implementar a função separa de maneira um pouco diferente a fim de 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].

static 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; 
}

(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.)   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 pelo ponto A, teremos uma das configurações a seguir:

p       i j       r
c ≤ c ≤ c ≤ c > c ≤ c > c > c > c > c
p         i=j       r
c ≤ c ≤ c ≤ c ≤ c ? > c > c > c > c

Portanto, na última passagem pelo ponto A, valem as seguintes relações:

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

(Observe que a variável i serve de sentinela para j e vice-versa. Isso torna desnecessárias as comparações de i com r toda vez que i é incrementado e torna desnecessárias as comparações de j com p toda vez que j é decrementado. Esse detalhe contribui para tornar a função particularmente rápida.)

Desempenho do algoritmo da separação.   Quanto tempo a função 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.

Exercícios 2

  1. Mostre o resultado da operação separa (v, 0, 15), sendo v[0..15] o vetor
    33 22 55 33 44 22 99 66 55 11 88 77 33 88 66 66
    
  2. Qual o resultado da função  separa  quando os elementos de v[p..r] são todos iguais?  E quando v[p..r] é crescente?  E quando v[p..r] é decrescente?  E quando cada elemento de v[p..r] tem um de dois valores possíveis?
  3. Versão recursiva.  Escreva uma versão recursiva da função separa
  4. Reescreva o código de separa de modo que v[r] seja escolhido para servir de pivô.
  5. A função separa produz um rearranjo estável do vetor, ou seja, preserva a ordem relativa de elementos de mesmo valor?
  6. Separação de Lomuto.  ⚠ Analise e discuta a seguinte versão da função separa. (O livro de Cormen, Leiserson, Rivest e Stein e atribui essa versão a N. Lomuto.)
    int separa_L (int v[], int p, int r) {
       int c = v[r], j = p, k, t;
       for (k = p; 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; }
    
  7. Critique a seguinte variante da função separa:
    int separa (int v[], int p, int r) {
       int c = v[p], i = p+1, j = r, t;
       while (i <= j) {
          if (v[i] <= c) ++i;
          else {
             t = v[i], v[i] = v[j], v[j] = t;
             --j; } }
       v[p] = v[j], v[j] = c;
       return j; }
    
  8. Critique a seguinte variante da função separa:
    int separa (int v[], int p, int r) {
       int c = v[p], i = p+1, j = r, t;
       while (i <= j) 
          if (v[i] <= c) {
             v[i-1] = v[i];
             ++i; }
          else {
             t = v[i], v[i] = v[j], v[j] = t;
             --j; }
       v[j] = c;
       return j; }
    
  9. Critique a seguinte solução do probleam da separação (extraída do livro de E. Roberts).
    int separa_R (int v[], int p, int r) {
       int c = v[p], i = p+1, j = r, t;
       while (1) {
          while (i < j && c < v[j]) --j;
          while (i < j && v[i] <= c) ++i;
          if (i == j) break;
          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; }
    
  10. Desafio.  Escreva uma solução do problema da separação que devolva um índice j tal que (r-p)/10 ≤ j-p ≤ 9(r-p)/10,
  11. Um vetor é binário se cada um de seus elementos vale 0 ou 1.  Escreva uma função que rearranje um vetor binário v[0..n-1] em ordem crescente e consuma tempo proporcional ao tamanho do vetor.

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:

// Esta função rearranja qualquer vetor
// v[p..r] 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
   }
}

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 4 e v[j+1..r] estará em ordem crescente no fim da linha 5. 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 5, como promete a documentação da função.

Se eliminarmos a segunda chamada recursiva e trocarmos o if por um while, teremos uma versão inteiramente equivalente:

void quicksrt (int v[], int p, int r) {
   int j;
   while (p < r) {          
      j = separa (v, p, r); 
      quicksrt (v, p, j-1);
      p = j + 1;            
   }
}

Exercícios 3

  1. Que acontece se trocarmos p < r por p != r na linha 2 do quicksort?  Que acontece se trocarmos j-1 por j na linha 4 do código?  Que acontece se trocarmos j+1 por j na linha 5?
  2. Pegadinha.  Quais são os invariantes da função quicksort?
  3. Submeta o vetor  77 55 33 99  indexado por  1..4  à função quicksort. Teremos a seguinte sequência de chamadas da função:
    quicksort (v,1,4)
        quicksort (v,1,2)
            quicksort (v,1,0)
            quicksort (v,2,2)
        quicksort (v,4,4)
    

    (observe a indentação).  Repita o exercício com o vetor  55 44 22 11 66 33  indexado por  1..6.

  4. Escreva uma função com protótipo  quick_sort (int v[], int n)  que rearranje um vetor v[0..n-1] em ordem crescente. (Basta invocar quicksort da maneira correta.)
  5. A função quicksort produz uma ordenação estável do vetor?
  6. Discuta a seguinte implementação do algoritmo Quicksort (supondo p < r):
    void qcksrt (int v[], int p, int r) {
       int j;                   
       j = separa (v, p, r);
       if (p < j-1) qcksrt (v, p, j-1);
       if (j+1 < r) qcksrt (v, j+1, r);
    }
    
  7. Formulação alternativa da separação.  ⚠ Suponha dada uma função que resolve a primeira das formulação do problema da separação dadas acima (ou seja, rearranja v[p..r] e devolve j tal que v[p..j] ≤ v[j+1..r].)  Escreva uma versão do algoritmo Quicksort que use essa função de separação. Que restrições devem ser impostas sobre j?
  8. Versão iterativa.  ⚠ Escreva uma versão não recursiva do algoritmo Quicksort.   [Solução.]
  9. Quicksort aleatorizado.  ⚠ Escreva uma versão aleatorizada (= randomized) do algoritmo Quicksort.
  10. Testes com vetor aleatório.  Escreva um programa que teste, experimentalmente, a correção de sua implementação do algoritmo Quicksort. Use permutações aleatórias de 1..n para os testes. Compare o resultado da ordenação com 1..n.

Animações do Quicksort

Desempenho do Quicksort básico

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 minha página Análise do Quicksort.)

Exercícios 4

  1. Cronometragem.  Escreva um programa que cronometre sua implementação do Quicksort (use a função clock da biblioteca time).  Divida os tempos por n log n para comparar com as previsões teóricas.
  2. Versão 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 de inserção.  O valor de M pode ficar entre 10 e 20.   (Esse truque é usado na prática porque o algoritmo de inserção é 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.)
  3. [Pedro Rey]  A seguinte função promete rearranjar o vetor v[p..r] em ordem crescente.  Mostre que a função está correta.  Estime o consumo de tempo da função.
    void psort (int v[], int p, int r) {
       if (p >= r) return;
       if (v[p] > v[r]) {
          int t;
          t = v[p], v[p] = v[r], v[r] = t; }
       psort (v, p, r-1);
       psort (v, p+1, r); }
    

Altura da pilha de execução do Quicksort

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:

  1. cuidar primeiro do menor ⚠ dos segmentos v[p..j-1] e v[j+1..r]  e
  2. eliminar a segunda chamada recursiva da função (trocando o if por um while) como já fizemos acima.

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)
{
   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;
      }
   }
}

Exercícios 5

  1. Suponha que a seguinte função é aplicada a um vetor com n elementos. Mostre que a altura da pilha de execução pode passar de por log n.
    void quicks (int v[], int p, int r) {
       int j;
       if (p < r) {      
          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); } } }
    
  2. Familiarize-se com a função qsort da biblioteca stdlib.

 

APÊNDICE: outras formas do Quicksort

O algoritmo Quicksort pode ser implementado de várias outras maneiras além da discutida acima. A diferença entre as várias versões está no modo de resolver o problema da separação.  (Em todas as versõ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 usa uma formulação do problema da separação quase igual à que adotamos acima: rearranja v[p..r] de modo que tenhamos  v[p..j-1] ≤ v[j] ≤ v[j+1..r]  (note o segundo )  para algum j em p..r.
    // A função rearranja o vetor v[p..r]
    // em ordem crescente.
    
    void quick_FlipFlop (int v[], int p, int r)
    {
       int j, k, t, ff;
       if (p < r) {      
          j = p, k = r;
          ff = -1;
          while (j < k) {
             if (v[j] > v[k] {
                t = v[j], v[j] = v[k], v[k] = t;
                ff = -ff;
             }
             if (ff == -1) --k;
             else ++j;
          }
          quick_FlipFlop (v, p, j-1);
          quick_FlipFlop (v, j+1, r);
       }
    }
    
  2. A versão seguinte (veja livro de Cormen, Leiserson e Rivest) usa a primeira das duas formulações do problema da separação mencionadas acima: rearranja v[p..r] de modo que  v[p..j] ≤ v[j+1..r]  para algum j em p..r-1.
    // A função rearranja o vetor v[p..r]
    // 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 versão (se não me engano, ela está no livro de Sedgewick).  Exercício: formule com precisão o problema da separação que essa versão resolve.
    // A função rearranja o vetor v[p..r]
    // 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);
       }
    }
    
  4. A seguinte versão do Quicksort é sugerida no livro de Sedgewick.  Exercício: formule com precisão o problema da separação que essa versão resolve.
    #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);
        }
    }