Projeto de Algoritmos  |  Linguagem C  |  Índice  |  English

Quicksort

Considere o problema da ordenação discutido em outro capítulo. O problema consiste em permutar os elementos de um vetor v[0 .. n-1] para colocá-los em ordem crescente, i.e., rearranjar os elementos do vetor de tal modo que tenhamos v[0] ≤ . . . ≤ v[n-1].

O outro capítulo analisou alguns algoritmos simples para o problema. O presente capítulo examina um algoritmo mais sofisticado — o Quicksort — inventado por C. A. R. Hoare em 1962.  Em algumas raras instâncias, o Quicksort é tão lento quanto os algoritmos simples, mas em geral é muito mais rápido. Mais exatamente, o algoritmo é linearítmico em média, embora seja quadrático no pior caso.

Eis a ideia básica do algoritmo: se todos os elementos pequenos estiverem na metade esquerda do vetor e todos os elementos grandes estiverem na metade direita, basta ordenar cada metade independentemente.

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.

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 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 cada parte do vetor rearranjado seja estritamente menor que o vetor todo.  O desafio é resolver o problema da separação rapidamente e 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:

Neste capítulo, usaremos a segunda formulação do problema da separação.

Exercícios 1

O algoritmo da separação

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:

(Note que podemos ter j == p bem como k == j, ou seja, a metade esquerda ou a metade direita do vetor podem estar vazias.)  Mais exatamente, valem os seguintes invariantes: no início de cada iteração,

1. p ≤ j ≤ k ,
2. v[p..j-1] ≤ c ,
3. v[j..k-1] > c  e
4. v[p..r] é uma permutação do vetor original.

Na última passagem pelo ponto A, teremos k == r e portanto a seguinte configuração:

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.

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.

Exercícios 2

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

Exercícios 3

Animações do Quicksort

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.

Há muitas outras animações do Quicksort. Veja alguns exemplos:

• Animation of Quicksort, de C. Parsons, on YouTube.
• Animation of Quicksort produzido por Mike Bostock. [Link sugerido por Yoshiharu Kohayakawa.] O vetor é representado por uma vassoura. Cada cerda da vassoura é um elemento do vetor e a inclinação da cerda é o valor do elemento.  Seguem algumas apresentações autônomas da animação:
  • Quicksort. O pivô está destacado em vermelho. (Veja o código.)
  • Quicksort IV. Mostra o bloco ativo da partição em preto e o pivô ativo em vermelho. O algoritmo intercambia v[(p+r)/2] e v[r] antes de fazer a separação, ou seja, usa o valor do elemento do meio do vetor como pivô. (Veja o código.)
  • Quicksort II. Uma visualização estática da versão iterativa. Cada linha corresponde ao estado do vetor antes de uma separação. As linhas vermelhas representam os pivôs. Recarregue para variar os dados. (Veja o código.)
  • Quicksort V. Uma visualização estática usando fitas coloridas que se entrelaçam. Cada linha representa o estado do vetor depois de uma operação se separação. Recarregue para mudar os dados. (Veja o código.)
  • Quicksort VI. Uma versão animada de Quicksort V. (Veja o código.)
• Quick-sort com dança folclórica húngara, Universidade Sapientia (Romênia).
• Animação de 15 algoritmos de ordenação, de Timo Bingmann, no YouTube.
• Comparison Sorting Algorithms, de David Galles (University of San Francisco).
• Sorting Algorithms Animations da Toptal.

Desempenho do Quicksort básico

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

n² .

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.

Exercícios 4

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.

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

Exercícios 5