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
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
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]
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]
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
| Algoritmo | Melhor caso | Caso médio | Pior caso | Estável |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | ✅ |
| Selection Sort | O(n²) | O(n²) | O(n²) | ❌ |
| Insertion Sort | O(n) | O(n²) | O(n²) | ✅ |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | ✅ |
| Timsort (Python) | O(n) | O(n log n) | O(n log n) | ✅ |
Resumo
- Busca linear percorre todos os elementos — O(n), funciona em listas não ordenadas
- Busca binária divide o espaço pela metade — O(log n), exige lista ordenada
- Bubble, selection e insertion sort são didáticos mas ineficientes para grandes volumes — O(n²)
- Merge sort garante O(n log n) com divisão e conquista recursiva
- Timsort é o algoritmo nativo do Python — use sempre
sort()ousorted()em produção - A função
keydesorted()permite ordenar por qualquer critério de forma elegante
Referências e Leituras Complementares
- 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.