Quick sort: pivô e partição

A ideia do pivô

O merge sort divide a lista no meio geométrico, sem olhar os valores. O quick sort faz diferente: ele escolhe um valor, o pivô, e usa esse valor para dividir. A escolha do pivô pode ser o primeiro elemento, o último, o do meio ou um aleatório. Uma vez escolhido, o algoritmo reorganiza a lista de modo que tudo que é menor que o pivô fique de um lado e tudo que é maior fique do outro. Essa reorganização é a partição. Note que os dois lados ainda não estão ordenados entre si; só está garantido que um lado tem os pequenos e o outro tem os grandes em relação ao pivô.

O detalhe mais elegante é o que acontece com o pivô. Depois da partição, com os menores à esquerda e os maiores à direita, o pivô é encaixado bem no meio, entre os dois grupos. E aí ele já está no lugar definitivo da lista ordenada, porque nenhum elemento menor pode estar à sua direita e nenhum maior à sua esquerda. Isso significa que a cada partição pelo menos um elemento, o pivô, fica resolvido para sempre. O quick sort então repete a mesma receita nos dois lados: escolhe um novo pivô na parte esquerda, particiona, e faz o mesmo na parte direita. Quando os pedaços chegam a um elemento, tudo está ordenado.

A partição passo a passo

A partição parece complicada, mas é um caminhar simples pela lista. Escolha o último elemento como pivô. Mantenha um marcador que aponta onde termina a região dos menores, começando antes do início. Percorra a lista do começo até o penúltimo. Sempre que encontrar um elemento menor ou igual ao pivô, avance o marcador e troque esse elemento para dentro da região dos menores. Ao terminar a varredura, o marcador aponta o fim dos menores; troque o pivô para logo depois dele. Pronto: à esquerda ficaram os menores, à direita os maiores, e o pivô no meio, no seu lugar final. É esse ponto de corte que o algoritmo devolve para dividir a lista.

FUNÇÃO quick_sort(lista, inicio, fim)
  SE inicio < fim ENTÃO
    p <- particionar(lista, inicio, fim)   // p e a posicao final do pivo
    quick_sort(lista, inicio, p - 1)       // ordena o lado dos menores
    quick_sort(lista, p + 1, fim)          // ordena o lado dos maiores
  FIM
FIM

FUNÇÃO particionar(lista, inicio, fim)
  pivo <- lista[fim]
  i <- inicio - 1
  PARA j DE inicio ATÉ fim - 1 FAÇA
    SE lista[j] <= pivo ENTÃO
      i <- i + 1
      trocar(lista, i, j)
    FIM
  FIM
  trocar(lista, i + 1, fim)   // poe o pivo depois dos menores
  RETORNE i + 1
FIM

A partição varre a lista trocando os menores para a frente; no fim, o pivô vai para o ponto de corte e a função devolve essa posição.

lista <- [4, 2, 7, 1]
// pivo = 1 (ultimo elemento)
// menores ou iguais a 1: nenhum antes do pivo
// entao o pivo vai para o inicio (posicao 0)
// resultado apos a particao:
escreva([1, 4, 2, 7])

Rápido, mas com um pior caso

Na média, o quick sort é O(n log n) e costuma bater o merge sort no relógio, porque particiona no próprio lugar da lista, sem gastar memória extra para uma cópia. Mas ele tem um calcanhar. Se o pivô escolhido for quase sempre o menor ou o maior elemento, a partição fica desbalanceada: um lado quase vazio, o outro quase inteiro. Aí, em vez de cortar pela metade, o algoritmo tira só um elemento por vez, e o custo desaba para O(n ao quadrado), o mesmo dos métodos simples. Esse pior caso aparece, por exemplo, ao rodar o quick sort ingênuo (pivô no último) sobre uma lista já ordenada. A defesa é escolher o pivô com esperteza: pegar o do meio, um aleatório, ou a mediana de três candidatos.