Aberto dia e noiteEntrada gratuitaPode tocar nas exposições

Sala F1 · Computação

Veja seis algoritmos de ordenação disputando.

Execute Bubble, Selection, Insertion, Merge, Quick e Heap Sort lado a lado. Veja cada comparação e troca, e entenda por que alguns escalam para milhões de itens enquanto outros ficam para trás.

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 a

Selection 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 a

Insertion 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 a

Merge 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 a

Heap 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 a

Lendo 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.

AlgoritmoMelhorMédioPiorEspaço extraEstável
Bubble SortO(n)O(n²)O(n²)O(1)Sim
Selection SortO(n²)O(n²)O(n²)O(1)Não
Insertion SortO(n)O(n²)O(n²)O(1)Sim
Merge SortO(n log n)O(n log n)O(n log n)O(n)Sim
Quick SortO(n log n)O(n log n)O(n²)O(log n)Não
Heap SortO(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

Cite esta exposição

Eurekarium. (2026). Laboratório de Ordenação. https://eurekarium.com/pt/computing/sorting-lab/

Última atualização: