Algoritmos de Ordenação e Busca

Ordenar e buscar dados são duas das operações mais fundamentais da computação. Todo sistema que lida com listas de produtos, rankings, resultados de pesquisa ou registros de banco de dados precisa dessas operações. Neste artigo vamos estudar os algoritmos clássicos, entender como funcionam internamente e aprender quando usar as ferramentas nativas do Python — que já os implementam de forma otimizada.

Complexidade de Algoritmos: uma Introdução Rápida

Antes de comparar algoritmos, precisamos de uma forma de medir sua eficiência. A notação Big O descreve como o tempo de execução cresce em relação ao tamanho da entrada n:

O(1)       — constante: independe do tamanho da entrada
O(log n)   — logarítmico: cresce lentamente (busca binária)
O(n)       — linear: proporcional ao tamanho (busca linear)
O(n log n) — linearítmico: eficiente para ordenação (Timsort)
O(n²)      — quadrático: lento para entradas grandes (bubble sort)

Para n = 1.000.000 de elementos, a diferença entre O(n log n) e O(n²) é a diferença entre segundos e horas.

Algoritmos de Busca

Busca Linear

Percorre a lista elemento por elemento até encontrar o alvo. Simples, mas lento para listas grandes.

def busca_linear(lista, alvo):
    """
    Busca linear — O(n).
    Funciona em listas não ordenadas.
    """
    for indice, elemento in enumerate(lista):
        if elemento == alvo:
            return indice
    return -1


numeros = [42, 7, 19, 3, 88, 55, 21]
print(busca_linear(numeros, 88))   # 4
print(busca_linear(numeros, 100))  # -1

Quando usar: listas pequenas ou não ordenadas. Para listas ordenadas, use a busca binária.

Busca Binária

Divide o espaço de busca pela metade a cada passo. Requer que a lista esteja ordenada.

def busca_binaria(lista, alvo):
    """
    Busca binária — O(log n).
    Requer lista ordenada.
    """
    esquerda = 0
    direita = len(lista) - 1

    while esquerda <= direita:
        meio = (esquerda + direita) // 2   # em Python isto é seguro

        if lista[meio] == alvo:
            return meio
        elif lista[meio] < alvo:
            esquerda = meio + 1
        else:
            direita = meio - 1

    return -1


ordenados = [3, 7, 15, 22, 36, 48, 61, 79, 94]
print(busca_binaria(ordenados, 48))   # 5
print(busca_binaria(ordenados, 50))   # -1

A exigência de lista ordenada não é uma formalidade, e o modo como ela é violada é o que a torna perigosa: a busca binária numa lista desordenada não levanta erro. Ela devolve uma resposta errada, e a resposta errada mais comum é dizer que o elemento não existe.

desordenada = [42, 7, 19, 3, 88, 55, 21]

busca_binaria(desordenada, 88)   # -1  — mas o 88 está no índice 4
busca_binaria(desordenada, 7)    # -1  — e o 7 está no índice 1

O algoritmo faz o que lhe foi pedido: compara com o elemento do meio e descarta metade da lista. Se a lista não está ordenada, a metade descartada pode ser justamente a que continha o alvo, e não há como perceber. Num sistema de verdade isso vira um relatório que diz que o cadastro não existe enquanto ele está lá. A defesa prática é não deixar a ordenação implícita: ou a estrutura é mantida ordenada por construção, ou a ordenação acontece imediatamente antes da busca, no mesmo trecho de código, onde quem lê consegue ver.

Vale ainda uma observação sobre a linha que calcula o meio, porque ela é famosa. Em C e em Java, (esquerda + direita) / 2 manteve um defeito de estouro de inteiro na busca binária da biblioteca padrão por quase duas décadas: com listas grandes o bastante, a soma ultrapassa o limite do tipo e vira um número negativo, e o índice calculado aponta para fora da lista. A correção canônica é esquerda + (direita - esquerda) // 2. Em Python o problema não existe, porque int tem precisão arbitrária e cresce conforme o necessário — somar dois índices na casa dos quintilhões devolve o valor exato. Vale saber disso não para escrever diferente aqui, mas porque a versão defensiva aparece muito em material traduzido de outras linguagens, e convém entender que ali ela resolve um problema que o Python não tem.

Para listas muito grandes, o Python oferece o módulo bisect — uma implementação nativa e otimizada de busca binária:

import bisect

lista = [10, 20, 30, 40, 50]
posicao = bisect.bisect_left(lista, 30)
print(posicao)  # 2

# Inserindo mantendo a ordem
bisect.insort(lista, 25)
print(lista)  # [10, 20, 25, 30, 40, 50]

Duas ressalvas sobre o bisect, porque o nome engana. A primeira: o insort faz a busca em tempo logarítmico, mas a inserção continua sendo O(n) — inserir no meio de uma lista obriga o Python a deslocar todos os elementos seguintes. Medindo vinte mil inserções numa lista de vinte mil itens na 3.14, o insort levou 0,0311 s contra 0,0002 s do append, uma diferença de 126 vezes. Manter uma lista ordenada a cada inserção é caro; quando as inserções são muitas e as buscas poucas, sai mais barato acumular e ordenar uma vez no fim.

A segunda: até a 3.10 as funções do bisect comparavam os elementos diretamente, o que impedia usá-las sobre listas de dicionários ou de objetos. Hoje elas aceitam key, como o sorted:

registros = [{"id": 1, "n": 10}, {"id": 2, "n": 20}, {"id": 3, "n": 30}]

bisect.bisect_left(registros, 20, key=lambda r: r["n"])   # 1

bisect.bisect_left(registros, 20)
# TypeError: '<' not supported between instances of 'dict' and 'int'

A lista precisa estar ordenada pela mesma chave que se passa ao bisect. Ordenada por outro critério, cai-se de volta na falha silenciosa da seção anterior.

Algoritmos de Ordenação

Bubble Sort

Compara pares adjacentes e os troca se estiverem fora de ordem. Intuitivo para aprender, mas ineficiente — O(n²).

def bubble_sort(lista):
    """Bubble sort — O(n²). Apenas didático."""
    n = len(lista)
    lista = lista.copy()

    for i in range(n):
        trocou = False
        for j in range(0, n - i - 1):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
                trocou = True
        if not trocou:
            break  # lista já ordenada — otimização de parada antecipada

    return lista


print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
# [11, 12, 22, 25, 34, 64, 90]

Selection Sort

Encontra o menor elemento e o coloca na posição correta a cada passagem. Também O(n²), mas faz menos trocas que o bubble sort.

def selection_sort(lista):
    """Selection sort — O(n²). Apenas didático."""
    lista = lista.copy()
    n = len(lista)

    for i in range(n):
        idx_minimo = i
        for j in range(i + 1, n):
            if lista[j] < lista[idx_minimo]:
                idx_minimo = j
        lista[i], lista[idx_minimo] = lista[idx_minimo], lista[i]

    return lista


print(selection_sort([29, 10, 14, 37, 13]))
# [10, 13, 14, 29, 37]

Insertion Sort

Constrói a lista ordenada inserindo cada elemento na posição correta. Eficiente para listas pequenas ou quase ordenadas — O(n²) no pior caso, O(n) no melhor.

def insertion_sort(lista):
    """Insertion sort — O(n²) pior caso, O(n) melhor caso."""
    lista = lista.copy()

    for i in range(1, len(lista)):
        chave = lista[i]
        j = i - 1
        while j >= 0 and lista[j] > chave:
            lista[j + 1] = lista[j]
            j -= 1
        lista[j + 1] = chave

    return lista


print(insertion_sort([5, 2, 4, 6, 1, 3]))
# [1, 2, 3, 4, 5, 6]

Merge Sort

Divide a lista ao meio recursivamente, ordena cada metade e as mescla. Eficiente — O(n log n) garantido.

def merge_sort(lista):
    """Merge sort — O(n log n). Estável e previsível."""
    if len(lista) <= 1:
        return lista

    meio = len(lista) // 2
    esquerda = merge_sort(lista[:meio])
    direita  = merge_sort(lista[meio:])

    return merge(esquerda, direita)

def merge(esquerda, direita):
    resultado = []
    i = j = 0

    while i < len(esquerda) and j < len(direita):
        if esquerda[i] <= direita[j]:
            resultado.append(esquerda[i])
            i += 1
        else:
            resultado.append(direita[j])
            j += 1

    resultado.extend(esquerda[i:])
    resultado.extend(direita[j:])
    return resultado


print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]

O Algoritmo do Python: Timsort

Na prática, você raramente precisa implementar um algoritmo de ordenação — o Python já possui um dos melhores: o Timsort, criado por Tim Peters em 2002 especialmente para o Python.

O Timsort é uma combinação de merge sort e insertion sort, com complexidade O(n log n) no pior caso e O(n) para listas já ordenadas. É estável — elementos com valores iguais mantêm sua ordem relativa original.

# sort() — ordena in-place
numeros = [5, 2, 8, 1, 9, 3]
numeros.sort()
print(numeros)  # [1, 2, 3, 5, 8, 9]

numeros.sort(reverse=True)
print(numeros)  # [9, 8, 5, 3, 2, 1]

# sorted() — retorna nova lista, preserva a original
original = [5, 2, 8, 1, 9, 3]
nova = sorted(original)
print(original)  # [5, 2, 8, 1, 9, 3] — intacta
print(nova)      # [1, 2, 3, 5, 8, 9]

A estabilidade do Timsort não é curiosidade de rodapé: ela habilita uma técnica. Como elementos de mesma chave preservam a ordem em que estavam, é possível ordenar por vários critérios em passadas sucessivas, da chave menos importante para a mais importante:

dados = [("Ana", "TI", 3), ("Bruno", "RH", 1), ("Carla", "TI", 1), ("Diego", "RH", 3)]

p = sorted(dados, key=lambda x: x[2])   # primeiro o critério secundário
p = sorted(p,     key=lambda x: x[1])   # depois o principal

# [('Bruno', 'RH', 1), ('Diego', 'RH', 3), ('Carla', 'TI', 1), ('Ana', 'TI', 3)]
# idêntico a sorted(dados, key=lambda x: (x[1], x[2]))

A chave em tupla resolve o mesmo caso em uma passada e é o que se deve preferir quando dá. As passadas sucessivas ganham quando os critérios não cabem numa tupla — um deles é decrescente e o outro crescente sobre texto, por exemplo, em que o truque do sinal negativo não funciona porque não existe texto negativo.

Um detalhe que costuma aparecer como erro em produção: o Python 3 recusa comparar tipos diferentes, e ordenar uma lista com dados heterogêneos falha em vez de inventar um critério.

sorted([1, "a"])
# TypeError: '<' not supported between instances of 'str' and 'int'

sorted([1, True, 2.5])   # [1, True, 2.5] — funciona: bool e int são comparáveis

Ordenação por Chave Personalizada

A função key permite ordenar por qualquer critério:

alunos = [
    {"nome": "Carlos", "nota": 8.5},
    {"nome": "Ana",    "nota": 9.2},
    {"nome": "Bruno",  "nota": 7.8},
    {"nome": "Diana",  "nota": 9.2},
]

# Ordenando por nota (decrescente), depois por nome (crescente)
alunos_ordenados = sorted(
    alunos,
    key=lambda a: (-a["nota"], a["nome"])
)

for aluno in alunos_ordenados:
    print(f"{aluno['nome']:10} — {aluno['nota']}")

# Ana        — 9.2
# Diana      — 9.2
# Carlos     — 8.5
# Bruno      — 7.8

Para casos mais complexos, use operator.itemgetter ou operator.attrgetter:

from operator import itemgetter

alunos_ordenados = sorted(alunos, key=itemgetter("nota"), reverse=True)

Comparativo dos Algoritmos

Os algoritmos deste artigo têm dois papéis distintos, e confundi-los é o erro mais comum de quem sai daqui. Bubble, selection, insertion e merge sort estão aqui para serem entendidos, não usados: implementá-los ensina a enxergar por que um percurso aninhado custa quadrático e por que dividir ao meio custa logarítmico, e é esse raciocínio que se leva para o resto da carreira. Em código de produção a resposta é sempre sort() ou sorted(), que executam o Timsort — estável, O(n log n) no pior caso e O(n) quando a lista já está quase ordenada, que é o caso mais frequente em dados reais.

Do lado prático, três pontos valem mais que a tabela de complexidades. A busca binária em lista desordenada não dá erro: devolve resposta errada, em geral dizendo que o elemento não existe, e por isso a ordenação nunca deve ficar implícita. O bisect.insort busca em tempo logarítmico mas insere em tempo linear, o que o torna caro para muitas inserções — medido, 126 vezes mais lento que um append. E a estabilidade do Timsort é uma ferramenta, não um detalhe: ela permite ordenar por vários critérios em passadas sucessivas, da chave menos importante para a mais importante, quando uma chave em tupla não dá conta.

Fontes e leituras recomendadas

• Timsort — documentação e análise — https://docs.python.org/3/howto/sorting.html
• Módulo bisect — https://docs.python.org/3/library/bisect.html
• Módulo operator — https://docs.python.org/3/library/operator.html
• Visualização de algoritmos de ordenação — https://visualgo.net/en/sorting
• CORMEN, Thomas H. et al. Introduction to Algorithms. 4. ed. MIT Press, 2022. Cap. 2 e 6 — análise formal de ordenação e complexidade.
• GOODRICH, Michael T. et al. Data Structures and Algorithms in Python. Wiley, 2013. Cap. 12 — sorting e searching com exemplos em Python.
• SEDGEWICK, Robert; WAYNE, Kevin. Algorithms. 4. ed. Addison-Wesley, 2011. Cap. 2 — análise comparativa detalhada de algoritmos de ordenação.

Exercícios

Exercício 1

Um sistema de estoque mantém uma lista de códigos e usa busca binária para localizar itens. Um relatório começou a informar que certos produtos não existem, embora o time consiga vê-los na tela de listagem. Ninguém mudou o código da busca. Investigando, descobre-se que semanas antes foi acrescentado um cadastro rápido que faz codigos.append(novo). Explique a ligação.

Exercício 2

Um serviço recebe eventos e precisa manter uma lista sempre ordenada por horário, para depois exibir os cem primeiros. Alguém troca lista.append(evento) seguido de um sort() no fim por bisect.insort(lista, evento) a cada chegada, argumentando que busca binária é O(log n) e portanto mais rápido. O serviço ficou mais lento. Explique.

Exercício 3

Uma listagem precisa sair ordenada por departamento em ordem alfabética crescente e, dentro de cada departamento, por nome também crescente — mas os departamentos vazios devem aparecer por último. Um colega escreve sorted(dados, key=lambda x: (x.departamento, x.nome)) e depois tenta key=lambda x: (-x.departamento, x.nome) para inverter, e recebe um erro. Explique o erro e mostre duas formas corretas de resolver ordenações com critérios de direções diferentes.

Exercício 4

Uma rotina de importação ordena uma lista de valores lidos de um arquivo com valores.sort(). Funcionou por meses e agora levanta TypeError. O arquivo de entrada mudou: uma coluna que trazia só números passou a trazer também a palavra N/A em algumas linhas. Explique por que o Python se recusa a ordenar, por que isso é uma decisão acertada da linguagem, e como tratar.

Exercício 5

Explique por que implementar bubble sort tem valor mesmo sendo um algoritmo que ninguém deve usar, e em seguida analise a afirmação: o insertion sort é O(n²), logo é sempre pior que o merge sort, que é O(n log n). Diga em que situação concreta a afirmação falha, e como isso se relaciona com o algoritmo que o Python realmente usa.