Corrida de Algoritmos de Ordenação

acompanhe passo a passo dois algoritmos competindo na mesma entrada — comparações, trocas, complexidade

A carregar a simulação interativa...

o Big-O não conta toda a história 🖖

O bubble sort faz exatamente n(n−1)/2 comparações no pior caso — cerca de 2.000 para n=64. Cada passagem precisa varrer toda a região restante não ordenada, sem saída antecipada. A partição do quicksort coloca o pivô em sua posição final e divide o problema em dois subproblemas; cada nível de recursão realiza trabalho O(n) ao longo de O(log n) níveis, totalizando O(n log n). A pegadinha: se o pivô sempre cai em uma extremidade — por exemplo, entrada ordenada com o último elemento como pivô — a partição degenera em n subproblemas de tamanho n−1, n−2, ... somando O(n²). O pivô do elemento central usado aqui evita isso, motivo pelo qual a entrada invertida permanece rápida. Valores com poucos elementos únicos são o caso interessante: quando muitos elementos são iguais ao pivô, trocar valores idênticos desperdiça trabalho e pode empurrar em direção ao comportamento quadrático. O Big-O indica a classe de crescimento; as constantes, a sensibilidade à entrada e o comportamento do cache determinam qual algoritmo você realmente deve usar.

Por que conta passos, não segundos 🖖

Esta corrida pontua cada algoritmo contando comparações e trocas, não com um cronômetro. O tempo real depende da sua CPU, do navegador e do que mais estiver rodando, então o mesmo código pode parecer rápido ou lento em máquinas diferentes. Contar operações dá uma medida limpa e reproduzível do trabalho de fato realizado: a mesma entrada sempre produz as mesmas contagens, permitindo comparar os algoritmos em si, e não o hardware.

Quicksort nasceu traduzindo russo 🖖

Tony Hoare inventou o Quicksort em 1959, como estudante visitante em Moscou, enquanto trabalhava num projeto de tradução automática. Para procurar uma frase russa no dicionário, precisava antes ordenar suas palavras em ordem alfabética — e o método usual era desesperadamente lento. Sua solução, particionar em torno de um pivô, tornou-se um dos algoritmos mais usados de todos os tempos. As barras que disputam aqui vêm de um problema de linguagem, não de computação.

Problema resolvido na íntegra

Previsão exata da contagem de trocas do bubble sort em 64 elementos invertidos 7 passos
Execute a corrida na predefinição invertido — 64 elementos, o maior primeiro. Preveja a contagem de trocas do bubble sort exatamente, não a sua ordem de crescimento; depois diga o que impede qualquer algoritmo de troca de vizinhos de o superar.
1. Uma inversão é um par que está na ordem relativa errada. A entrada invertida é o extremo: para cada i < j o elemento anterior é o maior, pelo que todos os pares estão invertidos e a contagem é a totalidade deles. Obtenha este número antes que algo se mova — revela-se ser a totalidade do problema.
  
  $I = # {(i, j) : i < j, a_{i} > a_{j}} = (2 64) = \frac{64 \times 63}{2} = 2, 016$
2. O bubble sort troca apenas vizinhos, e apenas quando estão fora de ordem. Tal troca repara esse único par e não perturba nenhum outro, porque os dois elementos que se movem mantêm a mesma relação com tudo o que está fora deles. Uma troca, uma inversão — nunca duas, nunca nenhuma.
  
  $a_{k} > a_{k + 1} ⟶ I \mapsto I - 1$
3. Estar ordenado significa zero inversões. Começar em 2.016 e remover exatamente uma por troca não deixa margem de manobra: o número de trocas é forçado. O painel apresenta 2.016 trocas, e isso é uma identidade em vez de um limite de pior caso.
  
  $S = I_{0} - 0 = 2, 016$
4. As comparações são uma contagem separada que por acaso coincide aqui. A passagem i analisa j = 0 … 62 − i, pelo que o total é 63 + 62 + ⋯ + 1 — os mesmos 2.016 que a linha pior caso do bubble n(n−1)/2 mostra. Contagens iguais significam que cada comparação individual encontrou uma inversão, que é o que "pior caso" significa aqui. O contador sob o título de cada painel conta um passo por comparação mais um por troca, pelo que indica passo 0 / 4.032 antes de começar, e o botão › consome exatamente um desses passos por clique. O O(n²) ao lado do título é um rótulo, não uma contagem.
  
  $C = i = 0 \sum 62 (63 - i) = 63 + 62 + \dots + 1 = \frac{63 \times 64}{2} = 2, 016 = \frac{n ( n - 1 )}{2}, C + S = 4, 032$
5. Agora generalize o passo 2, pois é isto que o quicksort explora. Trocar duas entradas distanciadas por d posições deixa cada par formado com um elemento fora do intervalo inalterado no total: tal elemento é recomparado com a outra extremidade, as duas comparações trocam de lugar e a sua contribuição permanece inalterada. O que se pode mover é o próprio par, mais os 2(d − 1) pares que cada extremidade forma com as d − 1 entradas intermédias. No máximo 2d − 1 inversões podem ser eliminadas por troca, e definir d = 1 devolve a inversão única do passo 2.
  
  $1 + 2 (d - 1) = 2 d - 1 (d = 1 \Rightarrow 1)$
6. A primeira partição do quicksort toma o elemento central como pivô, a[31] = 33, e troca (0, 63), (1, 62), … , (31, 32) — 32 trocas a distâncias de 63, 61, … , 1. O passo 5 limita o seu efeito combinado a 2.016 inversões, e essa única passagem deixa o vetor completamente ordenado, pelo que foram removidas exatamente 2.016. O limite é atingido com igualdade: cada uma das 32 trocas alcançou o seu próprio máximo.
  
  $p = a_{31} = 33, d = 63, 61, \dots, 1 : m = 1 \sum 32 (2 (2 m - 1) - 1) = m = 1 \sum 32 (4 m - 3) = 2, 112 - 96 = 2, 016$
7. Assim, os dois algoritmos não estão a competir em astúcia, estão a competir em alcance. As 334 comparações e 64 trocas apresentadas pelo quicksort somam os 398 no seu contador — e apenas 32 dessas trocas movem algo, sendo as outras 32 o pivô trocado consigo mesmo em trechos que já estão ordenados. Os seus 334 também ficam abaixo da referência apresentada de 384 para n·log₂n, porque o elemento central de uma sequência invertida é a sua mediana, pelo que cada divisão é uniforme.
  
  $334 + 64 = 398, 64 lo g_{2} 64 = 384, \frac{2 , 016}{32} = 63$
Resposta

2.016 trocas e 2.016 comparações — os 4.032 passos no contador. E 2.016 não é um facto sobre o bubble sort: é um limite inferior para toda uma família. Qualquer algoritmo restrito a trocar elementos adjacentes — insertion sort, cocktail shaker, gnome sort, ou um que ninguém tenha escrito ainda — elimina no máximo uma inversão por troca pelo passo 2, pelo que todos eles precisam de pelo menos 2.016 trocas nesta entrada e todos eles são Ω(n²) em dados invertidos devido ao modelo em que trabalham, e não por serem desajeitados. O quicksort escapa a esse limite inferior por lhe ser permitido mover um elemento 63 posições de uma só vez: 2.016 inversões eliminadas por 32 trocas reais são 63 inversões por troca, e o passo 5 indica que isso é o máximo que qualquer troca individual nessa distância poderia ter conseguido. O painel não calcula a contagem de inversões nem o limite inferior que ela implica.

$S \geq I_{0} = (2 64) = 2, 016 (d = 1), \frac{I _{0}}{32} = 63$

Percurso de aprendizagem

Contar trabalho, não segundos

Conduz a recursion-tree

Referências (1)

Insight block 3 — quicksort as its author published it: C. A. R. Hoare, "Quicksort." The Computer Journal 5(1), 10–16, 1962. The algorithm first appeared the year before as C. A. R. Hoare, "Algorithm 64: Quicksort", Communications of the ACM 4(7), 321, 1961.

Pela equipa 42Math · Atualizado 2026-05-27

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Computação →

Problemas de exemplo

quase ordenado - A distribuição da entrada altera a eficiência relativa dos algoritmos.
invertido - O Bubble sort efetua 2.016 comparações e 2.016 trocas: cada comparação encontra o seu par fora de ordem, pois a inversão de 64 elementos inverte todos os 2.016 pares de uma só vez. O Quicksort resolve a questão em 334 comparações e 64 trocas, abaixo da sua referência n·log₂n de 384, já que o elemento central de um vetor invertido é exatamente a mediana em cada partição.
poucos valores únicos - Oitenta elementos extraídos de apenas oito valores distintos. O Quicksort precisa de 534 comparações face à sua referência n·log₂n de 506, a única das três predefinições em que acaba acima da sua própria linha: elementos iguais ao pivô são trocados e não se ganha nada com isso. O Bubble sort continua a realizar as suas 3.160 comparações fixas e apenas 1.330 trocas, porque tantos pares vizinhos já são iguais.