Projeto de Algoritmos  |  Linguagem C  |  Índice  |  English

Quicksort

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 n².  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.

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 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:

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, o primeiro ou o segundo segmento do vetor podem estar vazios.)  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.

Veja outras animações de algoritmos de ordenação:

• Comparison Sorting Algorithms, de David Galles (University of San Francisco).
• Animação de 15 algoritmos de ordenação, de Timo Bingmann, no YouTube.
• Animação do Quicksort, de C. Parsons, no YouTube.
• Animação do Quicksort produzida por Mike Bostock  (veja também uma visualização estática, uma variante, e uma outra forma de visualização). [Link sugerido por Yoshiharu Kohayakawa.]
• Sorting Algorithms Animations da Toptal.
• Quick-sort com dança folclórica húngara, Universidade Sapientia (Romênia).

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