Como funciona
Ordenar é colocar itens em ordem — do menor para o maior, de A a Z. Todos os algoritmos abaixo resolvem o mesmo problema; diferem só na estratégia, e é a estratégia que você observa. Escolha um algoritmo (ou o modo disputa para os seis de uma vez), escolha uma entrada e aperte o play. As barras acendem enquanto o motor trabalha: amarelo marca comparação, vermelho marca movimento ou troca, roxo marca o pivô e verde marca posições prontas.
Os controles lembram um reprodutor de vídeo porque o motor é um: play e pause com a barra de espaço, um passo por vez com a seta para a direita, reiniciar com R, nova lista com N, embaralhar comS e velocidades de 0,25× a 8×. Um painel de código destaca cada linha do pseudocódigo enquanto ela executa, então animação e programa andam juntos. Experimente a mesma disputa duas vezes: uma com lista invertida, outra quase ordenada, e veja o Insertion Sort sair do fim do pelotão para a frente.
Os seis algoritmos
Três são métodos quadráticos simples — fáceis de escrever, dolorosos em escala. Três são métodos eficientes que chegam a O(n log n) com divisão e conquista ou uma estrutura de dados esperta. Cada exemplo abaixo é um Python completo e executável, operando sobre uma lista comum.
Bubble Sort — a troca de vizinhos
Percorra a lista comparando vizinhos e trocando pares fora de ordem. A cada passada, o maior item não ordenado “flutua” para seu lugar final, então a passada seguinte pode ser um passo mais curta. Se uma passada completa não fizer trocas, a lista já está ordenada e o algoritmo para cedo — sua única qualidade redentora, que dá O(n) em entradas já ordenadas.
def bubble_sort(a):
n = len(a)
for end in range(n - 1, 0, -1):
swapped = False
for i in range(end):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
swapped = True
if not swapped:
break
return aSelection Sort — escolha o menor, repita
Divida a lista em frente ordenada e resto não ordenado. A cada passo, varra todo o resto à procura do mínimo e troque-o para o lugar. Ele sempre faz o mesmo número de comparações — cerca de n²/2 — por mais ordenada que a entrada já esteja; por isso melhor, médio e pior casos são todos O(n²). Sua virtude é fazer no máximo n trocas, útil quando trocar era caro.
def selection_sort(a):
n = len(a)
for i in range(n):
m = i
for j in range(i + 1, n):
if a[j] < a[m]:
m = j
a[i], a[m] = a[m], a[i]
return aInsertion Sort — o método de quem joga cartas
Como quem ordena cartas na mão: pegue o próximo item e deslize-o para a esquerda passando por tudo que for maior, até encaixar. Em dados quase ordenados quase nada se move, então roda em O(n) — o mais rápido da sala nesse caso, e o motivo de ordenações híbridas reais o usarem em sublistas pequenas. Em dados invertidos cada item viaja a distância toda: pior caso O(n²). É estável e não usa memória extra.
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return aMerge Sort — dividir, conquistar, mesclar
Divida a lista ao meio, ordene cada metade do mesmo jeito (a recursão chega a itens únicos, já ordenados por definição) e mescle as metades comparando sempre os primeiros itens. A divisão é sempre equilibrada, então cada nível custa O(n) e há log n níveis: O(n log n) garantido, em todos os casos. O preço é O(n) de memória extra na mesclagem, e ele é estável — itens iguais nunca se cruzam.
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:]Quick Sort — divisão por pivô
Escolha um pivô e particione: tudo que é menor vai para a esquerda, tudo que é maior para a direita. Ordene cada lado do mesmo jeito. Quando os pivôs caem perto do meio, a recursão tem log n níveis e o total é O(n log n) com constantes minúsculas e só O(log n) de memória extra para a recursão — em geral o mais rápido na prática. Quando caem num extremo, um lado fica com quase tudo e ele degrada para O(n²). Este simulador escolhe pivôs pela mediana de três (primeiro, meio e último itens), o que torna o caso ruim raro em dados reais. O exemplo em Python abaixo usa simplesmente o último item como pivô, para ficar curto.
def quick_sort(a, lo=0, hi=None):
if hi is None:
hi = len(a) - 1
if lo < hi:
p, i = a[hi], lo
for j in range(lo, hi):
if a[j] < p:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
quick_sort(a, lo, i - 1)
quick_sort(a, i + 1, hi)
return aHeap Sort — uma fila de prioridades disfarçada
Transforme a lista num max-heap: uma árvore binária compactada no vetor em que todo pai é maior que os filhos, então o máximo fica na posição zero. Retire o máximo repetidamente, troque-o para o fim, encolha o heap em um e restaure a propriedade descendo o novo topo. O(n log n) garantido com O(1) de memória extra — mas o acesso saltitante não agrada os caches do processador, então costuma perder para Quick e Merge Sort no cronômetro, apesar de empatar no papel.
def heap_sort(a):
def sift(lo, n, i):
while True:
l, r, m = 2 * i + 1, 2 * i + 2, i
if l < n and a[lo + l] > a[lo + m]:
m = l
if r < n and a[lo + r] > a[lo + m]:
m = r
if m == i:
return
a[lo + i], a[lo + m] = a[lo + m], a[lo + i]
i = m
n = len(a)
for i in range(n // 2 - 1, -1, -1):
sift(0, n, i)
for end in range(n - 1, 0, -1):
a[0], a[end] = a[end], a[0]
sift(0, end, 0)
return aLendo a tabela
Big-O descreve crescimento, não cronômetro: constantes e hardware são ignorados de propósito para que aforma da escala apareça. A tabela abaixo é a referência padrão (Cormen et al.,Introduction to Algorithms; Dicionário de Algoritmos e Estruturas de Dados do NIST). “Estável” significa que itens iguais mantêm a ordem original.
| Algoritmo | Melhor | Médio | Pior | Espaço extra | Estável |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Sim |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | Não |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Sim |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Sim |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | Não |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Não |
Experimente no simulador: dispute os seis com lista invertida e depois com lista quase ordenada. A ordem de chegada inverte — o Insertion Sort sai do fim do pelotão para a frente — e nenhuma fórmula ensina isso como ver acontecer.
Três erros comuns
“O Quick Sort é sempre o mais rápido.” Em média ele está entre os mais rápidos, mas um Quick Sort simples tem pior caso O(n²), por exemplo quando o pivô cai sempre em uma ponta da lista. O Merge Sort e o Heap Sort ficam em O(n log n) qualquer que seja a entrada.
“Os métodos quadráticos simples não servem para nada.” O Insertion Sort é muito usado em listas pequenas e vai muito bem em listas quase ordenadas. As rotinas de ordenação usadas na prática costumam ser híbridas e passam para o Insertion Sort nos pedaços pequenos.
“Ordenação estável é a que nunca falha.” Estabilidade tem um sentido preciso: itens com chaves iguais mantêm a ordem que tinham antes da ordenação. O Merge Sort e o Insertion Sort são estáveis; o Quick Sort e o Heap Sort, nas formas usuais, não são.
Perguntas dos visitantes
Qual algoritmo de ordenação devo usar no código real?
Quase sempre a ordenação nativa da linguagem: sorted() do Python, Array.sort() do JavaScript ou Arrays.sort() do Java para objetos. São híbridos de engenharia (Python e Java usam Timsort) com tempo O(n log n), estáveis e testados por milhões de usuários. Os seis algoritmos desta página ensinam as ideias por trás dessas ferramentas, não as substituem.
Se o Bubble Sort é lento, por que ainda é ensinado?
Porque é a ideia de ordenação mais simples possível: compare vizinhos, troque se estiverem fora de ordem, repita. Vê-lo sofrer ao lado do Merge Sort no modo disputa ensina mais sobre o crescimento O(n²) do que qualquer fórmula. A parada antecipada também mostra que o mesmo algoritmo pode ser O(n) em entradas já ordenadas e O(n²) no caso geral.
O que significa uma ordenação ser estável?
Uma ordenação estável mantém itens iguais na ordem relativa original. Isso importa ao ordenar por mais de uma chave: ordene uma turma por nome e depois por nota com um algoritmo estável, e alunos com a mesma nota continuam em ordem alfabética. Merge, Insertion e Bubble Sort são estáveis; Selection, Quick e Heap Sort, como normalmente implementados, não são.
Por que o Quick Sort nem sempre é o mais rápido se é O(n log n) em média?
Porque seu pior caso é O(n²): com pivôs azarados, cada partição separa apenas um item. Boas implementações evitam isso com pivô pela mediana de três (como neste simulador) ou aleatorização. O Merge Sort garante O(n log n), mas usa O(n) de memória extra; o Heap Sort garante O(n log n) no lugar, mas salta pela memória, de que os caches modernos não gostam.
O simulador executa mesmo os algoritmos ou é só animação?
Executa de verdade. Cada algoritmo roda sua lógica genuína e emite eventos de passo — comparação, troca, sobrescrita, pivô, mesclagem, heapify — que o gráfico animado reproduz. No modo disputa, os seis rodam a mesma entrada lado a lado, então a comparação é justa. O modo de palavras ordena texto sem diferenciar acentos nem maiúsculas.
O que a notação Big-O está contando, de fato?
Como o número de passos básicos cresce com a entrada, ignorando fatores constantes. O(n²) significa que dobrar a entrada quase quadruplica o trabalho; O(n log n) significa que dobrar pouco mais que dobra. Com n = 1.000.000, é a diferença entre cerca de um trilhão de operações e vinte milhões — minutos ou até horas contra uma fração de segundo.
Fontes e leitura complementar
- Introduction to Algorithms — MIT Press (Cormen et al.)
- Sorting algorithm — Wikipedia
- Dictionary of Algorithms and Data Structures — NIST
- Algorithms course — Khan Academy
Cite esta exposição
Eurekarium. (2026). Laboratório de Ordenação. https://eurekarium.com/pt/computing/sorting-lab/
Última atualização: