Algoritmos de Ordenacao em Python: sorted(), sort() e Implementacoes
Ordenacao em Python: Do Basico ao Avancado
Ordenar dados e uma das operacoes mais fundamentais da computacao. Em Python, voce tem acesso a ferramentas de ordenacao extremamente eficientes com sorted() e .sort(), alem de poder implementar algoritmos classicos para entender como funcionam por dentro.
Neste guia, vamos cobrir tudo: desde o uso pratico das funcoes built-in ate implementacoes de bubble sort, merge sort e quick sort, com analise de complexidade de cada um.
Se voce ainda nao domina listas em Python, recomendamos comecar por la antes de mergulhar nos algoritmos de ordenacao.
sorted() e .sort(): Ordenacao Built-in
sorted() — Retorna Nova Lista
numeros = [3, 1, 4, 1, 5, 9, 2, 6]
# Ordenar em ordem crescente
ordenada = sorted(numeros)
# [1, 1, 2, 3, 4, 5, 6, 9]
# Lista original nao muda
print(numeros) # [3, 1, 4, 1, 5, 9, 2, 6]
# Ordem decrescente
decrescente = sorted(numeros, reverse=True)
# [9, 6, 5, 4, 3, 2, 1, 1]
# Funciona com qualquer iteravel
texto = sorted("python") # ['h', 'n', 'o', 'p', 't', 'y']
tupla = sorted((5, 2, 8, 1)) # [1, 2, 5, 8]
.sort() — Ordena In-Place
numeros = [3, 1, 4, 1, 5, 9, 2, 6]
# Ordena a lista diretamente (retorna None)
resultado = numeros.sort()
print(resultado) # None
print(numeros) # [1, 1, 2, 3, 4, 5, 6, 9]
Ordenacao Customizada com key
# Ordenar strings por tamanho
palavras = ["python", "go", "javascript", "c", "rust"]
por_tamanho = sorted(palavras, key=len)
# ['c', 'go', 'rust', 'python', 'javascript']
# Ordenar case-insensitive
nomes = ["ana", "Carlos", "maria", "Bruno"]
por_nome = sorted(nomes, key=str.lower)
# ['ana', 'Bruno', 'Carlos', 'maria']
# Ordenar lista de dicionarios
pessoas = [
{"nome": "Ana", "idade": 28},
{"nome": "Carlos", "idade": 22},
{"nome": "Maria", "idade": 35}
]
por_idade = sorted(pessoas, key=lambda p: p["idade"])
# Carlos(22), Ana(28), Maria(35)
# Ordenacao multipla (por cidade, depois por nome)
funcionarios = [
{"nome": "Ana", "cidade": "SP"},
{"nome": "Carlos", "cidade": "RJ"},
{"nome": "Maria", "cidade": "SP"},
{"nome": "Bruno", "cidade": "RJ"}
]
ordenados = sorted(funcionarios, key=lambda f: (f["cidade"], f["nome"]))
operator.itemgetter e attrgetter
from operator import itemgetter, attrgetter
# Mais rapido que lambda para dicionarios
por_idade = sorted(pessoas, key=itemgetter("idade"))
# Ordenar por multiplas chaves
por_cidade_nome = sorted(funcionarios, key=itemgetter("cidade", "nome"))
Para mais sobre funcoes lambda e o modulo operator, consulte nosso glossario.
Timsort: O Algoritmo Interno do Python
O Python usa internamente o Timsort, criado por Tim Peters em 2002. E um algoritmo hibrido que combina o melhor de merge sort e insertion sort:
- Divide os dados em “runs” (subsequencias ja ordenadas)
- Usa insertion sort para runs pequenos (< 64 elementos)
- Combina runs usando merge sort otimizado
- Aproveita dados parcialmente ordenados para ser mais rapido
| Caracteristica | Valor |
|---|---|
| Melhor caso | O(n) — dados ja ordenados |
| Caso medio | O(n log n) |
| Pior caso | O(n log n) |
| Espaco extra | O(n) |
| Estavel? | Sim |
O Timsort e estavel, ou seja, elementos com a mesma chave de ordenacao mantem sua posicao relativa original.
Bubble Sort
O bubble sort e o algoritmo mais simples de entender, ideal para fins didaticos. Compara pares adjacentes e troca se estiverem na ordem errada:
def bubble_sort(lista):
n = len(lista)
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
# Se nao houve troca, ja esta ordenada
if not trocou:
break
return lista
# Exemplo
numeros = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(numeros))
# [11, 12, 22, 25, 34, 64, 90]
| Caracteristica | Valor |
|---|---|
| Melhor caso | O(n) — ja ordenado |
| Caso medio | O(n^2) |
| Pior caso | O(n^2) |
| Espaco extra | O(1) |
| Estavel? | Sim |
Na pratica: Nunca use bubble sort em producao. E apenas didatico. Para listas pequenas, insertion sort e melhor.
Selection Sort
Encontra o menor elemento e coloca na posicao correta, repetidamente:
def selection_sort(lista):
n = len(lista)
for i in range(n):
menor_idx = i
for j in range(i + 1, n):
if lista[j] < lista[menor_idx]:
menor_idx = j
lista[i], lista[menor_idx] = lista[menor_idx], lista[i]
return lista
numeros = [64, 25, 12, 22, 11]
print(selection_sort(numeros))
# [11, 12, 22, 25, 64]
| Caracteristica | Valor |
|---|---|
| Todos os casos | O(n^2) |
| Espaco extra | O(1) |
| Estavel? | Nao |
Merge Sort
Algoritmo eficiente baseado em “dividir para conquistar”. Divide a lista ao meio recursivamente, ordena as metades e combina:
def merge_sort(lista):
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(esq, dir):
resultado = []
i = j = 0
while i < len(esq) and j < len(dir):
if esq[i] <= dir[j]:
resultado.append(esq[i])
i += 1
else:
resultado.append(dir[j])
j += 1
resultado.extend(esq[i:])
resultado.extend(dir[j:])
return resultado
# Exemplo
numeros = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(numeros))
# [3, 9, 10, 27, 38, 43, 82]
| Caracteristica | Valor |
|---|---|
| Todos os casos | O(n log n) |
| Espaco extra | O(n) |
| Estavel? | Sim |
Merge sort e a base do Timsort e e muito usado em aplicacoes que exigem ordenacao estavel.
Quick Sort
O quick sort escolhe um “pivo” e particiona a lista em elementos menores e maiores que o pivo:
def quick_sort(lista):
if len(lista) <= 1:
return lista
pivo = lista[len(lista) // 2]
menores = [x for x in lista if x < pivo]
iguais = [x for x in lista if x == pivo]
maiores = [x for x in lista if x > pivo]
return quick_sort(menores) + iguais + quick_sort(maiores)
# Exemplo
numeros = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort(numeros))
# [1, 1, 2, 3, 6, 8, 10]
Versao In-Place (mais eficiente em memoria)
def quick_sort_inplace(lista, inicio=0, fim=None):
if fim is None:
fim = len(lista) - 1
if inicio >= fim:
return
pivo_idx = particionar(lista, inicio, fim)
quick_sort_inplace(lista, inicio, pivo_idx - 1)
quick_sort_inplace(lista, pivo_idx + 1, fim)
def particionar(lista, inicio, fim):
pivo = lista[fim]
i = inicio - 1
for j in range(inicio, fim):
if lista[j] <= pivo:
i += 1
lista[i], lista[j] = lista[j], lista[i]
lista[i + 1], lista[fim] = lista[fim], lista[i + 1]
return i + 1
| Caracteristica | Valor |
|---|---|
| Melhor/medio | O(n log n) |
| Pior caso | O(n^2) — pivo ruim |
| Espaco extra | O(log n) a O(n) |
| Estavel? | Nao |
Tabela Comparativa de Algoritmos
| Algoritmo | Melhor | Medio | Pior | Espaco | Estavel |
|---|---|---|---|---|---|
| Timsort (built-in) | O(n) | O(n log n) | O(n log n) | O(n) | Sim |
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) | Sim |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | Nao |
| 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^2) | O(log n) | Nao |
Qual Usar na Pratica?
- Sempre use
sorted()ou.sort()— o Timsort embutido e implementado em C e sera mais rapido que qualquer implementacao em Python puro - Merge sort e bom para entender dividir-para-conquistar e para cenarios onde estabilidade importa
- Quick sort e importante para entrevistas tecnicas — veja nosso guia de entrevistas Python
- Bubble sort so para fins didaticos
Ordenacao com Dados Reais
# Ordenar arquivos CSV carregados
import csv
def ordenar_por_coluna(arquivo, coluna, reverso=False):
with open(arquivo) as f:
leitor = csv.DictReader(f)
dados = sorted(leitor, key=lambda x: x[coluna], reverse=reverso)
return dados
# Ordenar objetos com multiplos criterios
from dataclasses import dataclass
@dataclass
class Funcionario:
nome: str
departamento: str
salario: float
funcionarios = [
Funcionario("Ana", "TI", 8000),
Funcionario("Carlos", "TI", 12000),
Funcionario("Maria", "RH", 7000),
Funcionario("Pedro", "TI", 8000),
]
# Ordenar por departamento, depois por salario decrescente
ordenados = sorted(funcionarios, key=lambda f: (f.departamento, -f.salario))
Para mais sobre dataclasses, consulte nosso glossario. Para trabalhar com dados tabulares, veja nosso guia sobre Pandas.
Conclusao
Entender algoritmos de ordenacao e fundamental para qualquer desenvolvedor Python. Na pratica, use sempre as ferramentas built-in (sorted() e .sort()), mas conhecer merge sort, quick sort e suas complexidades e essencial para entrevistas tecnicas e para tomar decisoes informadas sobre performance.
Continue aprendendo: busca binaria complementa perfeitamente o conhecimento de ordenacao, ja que busca binaria requer dados ordenados. Veja tambem listas, dicionarios e pilhas e filas.
Compare como outras linguagens lidam com ordenacao: Go, Rust e Kotlin.