Comparações
Trocas
Partições

  • Parte a particionar
  • Pivô
  • Comparados
  • Trocados
  • No lugar

Mais sobre o quicksort

Quicksort

O quicksort, ou ordenação rápida, escolhe um pivô, coloca todos os valores menores antes dele e todos os outros depois, e ordena os dois lados da mesma forma. Após cada partição, o pivô fica na posição final. Escolha a regra do pivô, reproduza a ordenação a qualquer velocidade ou avance uma comparação de cada vez, e veja porque é que um mau pivô numa lista ordenada torna o quicksort lento. Prima Reproduzir para ver a ordenação, ou Avançar e Recuar para ir uma comparação de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Os contadores mostram comparações, trocas e partições. Escolha quantas barras, como começam, ou escreva os seus próprios números, e como é escolhido o pivô. Com o quadro selecionado, as setas avançam e recuam, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.

Como funciona

  1. Escolha o número de barras e a ordem inicial: aleatória, quase ordenada, invertida ou com poucos valores distintos. Ou escreva os seus próprios números.
  2. Prima Reproduzir, ou use Avançar e Recuar para ir uma comparação de cada vez. Arraste a barra de passos para saltar para qualquer ponto da ordenação.
  3. Escolha a regra do pivô: o último valor, o valor do meio, um valor aleatório ou a mediana de três. Experimente cada uma numa lista ordenada.

Como funciona o quicksort

Escolha um valor da parte a ordenar como pivô e mova-o para o fim. Percorra os outros valores da esquerda para a direita; cada um que seja menor do que o pivô é trocado para uma parte esquerda que cresce a partir do início. Depois, troque o pivô para logo a seguir à parte esquerda. Tudo o que está antes dele é agora menor e nada do que está depois o é, por isso o pivô está na posição final. Ordene da mesma forma a parte antes e a parte depois, até cada parte ter um só valor.

Porque é que o pivô importa

Quando o pivô fica perto do meio, cada partição reduz o problema a metade e as comparações crescem como n log n: para 40 valores aleatórios, cerca de 190. Quando o pivô é o menor ou o maior valor, um lado fica vazio e o outro fica com todo o resto. Com o último valor como pivô, isso acontece em cada passo numa lista ordenada ou invertida, e a ordenação precisa de n(n − 1)/2 comparações, 780 para 40 valores. Um pivô aleatório ou a mediana do primeiro valor, do valor do meio e do último evita isso na prática.

Perguntas frequentes

Como funciona o quicksort?

Escolhe um pivô, particiona a lista para que os valores menores fiquem antes do pivô e os restantes depois, e ordena ambos os lados com o quicksort. Após cada partição, o pivô está na posição final.

Porque é que o quicksort é lento numa lista ordenada?

Com o primeiro ou o último valor como pivô, uma lista ordenada dá sempre o menor ou o maior valor como pivô. Um lado da partição fica então vazio, por isso cada partição só retira um valor, e a ordenação precisa de n(n − 1)/2 comparações. Um pivô aleatório ou a mediana de três resolve isto na prática.

O quicksort é mais rápido do que o merge sort?

Muitas vezes, na prática: ordena in situ, não precisa de buffer e o seu ciclo interno é muito simples. Em média faz um pouco mais de comparações do que o merge sort, e o seu pior caso é n², enquanto o merge sort é sempre n log n. As ordenações das bibliotecas, como o introsort, começam com o quicksort e passam para o heap sort se as divisões ficarem demasiado desiguais.

O quicksort é estável?

Não. Uma partição troca valores a grandes distâncias, por isso valores iguais podem mudar de ordem.

Os meus números são enviados para algum lado?

Não. A ordenação corre no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor