Ordenações sem Comparação e o sort() do Python
Explore a ordenação por contagem e por radix para arrays de inteiros e entenda como o Timsort do Python funciona internamente nas chamadas de sort integradas.
Ordenações sem Comparação e o sort() do Python é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O limite inferior O(n log n) para comparações
Qualquer algoritmo de ordenação que determine a ordem apenas por meio de comparações entre elementos exige pelo menos Ω(n log n) comparações no pior caso. Isso é demonstrado pelo argumento da árvore de decisão: ordenar n elementos exige distinguir entre n! ordenações possíveis. Uma árvore de decisão binária (cada nó é uma comparação) precisa de pelo menos log₂(n!) ≈ n log₂(n) níveis. Para superar esse limite, precisamos de informações adicionais sobre os elementos — por exemplo, que sejam inteiros limitados.
import math
for n in [5, 10, 100, 1000]:
lower_bound = n * math.log2(n)
factorial_log = sum(math.log2(i) for i in range(1, n+1))
print(f'n={n}: n*log2(n)={lower_bound:.1f}, log2(n!)={factorial_log:.1f}')
# n log n is a tight bound on comparison-based sortingOrdenação por contagem: ordenar por frequência
A ordenação por contagem funciona contando a frequência de cada valor e, depois, reconstruindo o vetor ordenado a partir das contagens. É necessário conhecer antecipadamente o intervalo [0, k) dos valores. Complexidade de tempo: O(n + k); complexidade de espaço: O(k). Para valores de k pequenos em relação a n (por exemplo, ao ordenar idades de 0 a 120 ou algarismos únicos), a ordenação por contagem supera todas as ordenações por comparação. Para k grande, o custo de espaço O(k) torna o método impraticável.
def counting_sort(arr, k=None):
if not arr: return []
if k is None: k = max(arr) + 1
count = [0] * k
for n in arr:
count[n] += 1
result = []
for val, freq in enumerate(count):
result.extend([val] * freq)
return result
arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr)) # [1, 2, 2, 3, 3, 4, 8]
# O(n + k) where k = 9 (max value + 1)Sort de contagem estável com contagens cumulativas
Para um sort de contagem estável (importante ao ordenar objetos por uma chave), calcule as contagens cumulativas para que cum[v] forneça a posição inicial do valor v na saída. Percorra o vetor de entrada da direita para a esquerda, colocando cada elemento na posição cum[key] - 1 e decrementando essa posição. Isso produz um sort estável — os elementos com a mesma chave aparecem na ordem relativa original.
def counting_sort_stable(arr, k):
count = [0] * k
for n in arr: count[n] += 1
# Cumulative counts: count[v] = first position for value v
for i in range(1, k): count[i] += count[i-1]
output = [0] * len(arr)
# Fill from right to maintain stability
for n in reversed(arr):
count[n] -= 1
output[count[n]] = n
return output
print(counting_sort_stable([4,2,2,8,3,3,1], 9))
# [1, 2, 2, 3, 3, 4, 8]Radix sort: ordenar dígito a dígito
Radix sort ordena inteiros dígito a dígito, do dígito menos significativo (LSD) ao mais significativo (MSD), usando um sort estável (como o sort de contagem) em cada posição de dígito. Após d passagens (uma por dígito), o vetor fica totalmente ordenado. Complexidade de tempo: O(d × (n + k)), em que d = número de dígitos e k = base (geralmente 10). Para n inteiros limitados por W, d = log_k(W), resultando em O(n log_k(W)) no total.
def radix_sort(arr):
if not arr: return []
max_val = max(arr)
exp = 1 # current digit position (1, 10, 100, ...)
while max_val // exp > 0:
arr = counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for n_ in arr: count[(n_ // exp) % 10] += 1
for i in range(1, 10): count[i] += count[i-1]
for n_ in reversed(arr):
d = (n_ // exp) % 10
count[d] -= 1
output[count[d]] = n_
return output
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]Bucket sort: distribuir em compartimentos
Bucket sort distribui os elementos em um número fixo de compartimentos com base no intervalo de valores, ordena cada compartimento (com sort por inserção para compartimentos pequenos) e os concatena. Para dados distribuídos uniformemente em [0, 1), n compartimentos proporcionam tempo médio O(n). Tempo: O(n + k) em média, O(n²) no pior caso (todos os elementos em um único compartimento). É mais útil quando a distribuição dos dados é conhecida e aproximadamente uniforme.
def bucket_sort(arr):
if not arr: return []
n = len(arr)
min_v, max_v = min(arr), max(arr)
if min_v == max_v: return arr[:]
buckets = [[] for _ in range(n)]
# Map each value to a bucket index
for v in arr:
idx = int((v - min_v) / (max_v - min_v + 1e-9) * n)
idx = min(idx, n - 1)
buckets[idx].append(v)
result = []
for bucket in buckets:
bucket.sort() # insertion sort for small buckets
result.extend(bucket)
return result
print(bucket_sort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21]))
# sorted listO Timsort do Python por baixo dos panos
sorted() e list.sort() do Python usam o Timsort, criado por Tim Peters em 2002. O Timsort é um híbrido de sort de intercalação e sort por inserção. Ele procura por “sequências naturais” (subsequências já ordenadas) e usa sort por inserção para construir sequências de até 64 elementos. Em seguida, intercala as sequências usando sort de intercalação com várias otimizações: saltos (ignorando muitos elementos de uma vez quando uma sequência é dominante) e empilhamento baseado no comprimento das sequências.
# Timsort properties:
# - Stable
# - O(n log n) worst case
# - O(n) best case (data already sorted)
# - O(n) auxiliary space
# - Highly optimised for real-world data with runs
import time
# Nearly sorted data: Timsort is extremely fast
nearly_sorted = list(range(10000))
nearly_sorted[-1] = 0 # one mis-placed element
t = time.perf_counter()
not_used = sorted(nearly_sorted)
elapsed = time.perf_counter() - t
print(f'Timsort on nearly-sorted n=10000: {elapsed*1000:.3f} ms')sort() do Python versus sorted(): diferenças principais
list.sort() ordena no próprio lugar, retorna None e funciona apenas com listas. sorted(iterable) funciona com qualquer iterável (tuplas, geradores, dicionários) e retorna uma nova lista. Ambos aceitam os parâmetros key e reverse. Um erro comum é atribuir o retorno de lst.sort() a uma variável e perguntar-se por que ele é None. Use sempre sorted() quando precisar da versão ordenada e quiser manter o original.
nums = [3, 1, 4, 1, 5, 9]
# in-place: returns None
result = nums.sort()
print(result) # None (common bug!)
print(nums) # [1, 1, 3, 4, 5, 9] (modified)
nums2 = [3, 1, 4, 1, 5, 9]
# out-of-place: returns new list
result2 = sorted(nums2)
print(result2) # [1, 1, 3, 4, 5, 9]
print(nums2) # [3, 1, 4, 1, 5, 9] (unchanged)Chaves de ordenação personalizadas em entrevistas
O sort do Python aceita uma função key que é avaliada uma vez por elemento (ao contrário do comparador de C, chamado para cada par). Chaves de ordenação comuns em entrevistas: len para o comprimento de uma cadeia de caracteres, lambda x: -x para ordem decrescente, lambda x: (x[1], x[0]) para ordenação por várias chaves e str.lower para ignorar maiúsculas e minúsculas. O sort do Python tem estabilidade garantida, portanto as ordenações por várias chaves funcionam corretamente.
# Sort by length, then alphabetically
words = ['banana', 'fig', 'apple', 'date', 'kiwi']
print(sorted(words, key=lambda w: (len(w), w)))
# ['fig', 'date', 'kiwi', 'apple', 'banana']
# Sort integers as strings (largest concatenation first)
nums = [3, 30, 34, 5, 9]
print(sorted(map(str, nums), key=lambda a: a*10, reverse=True))
# ['9', '5', '34', '3', '30'] => '9534330'
# Descending sort
print(sorted([3,1,4,1,5], reverse=True)) # [5,4,3,1,1]Quando usar cada sort em entrevistas
Escolha o sort adequado ao contexto:
- Use o sorted()/list.sort() do Python: padrão para todos os problemas de entrevista — o Timsort é ideal
- Sort de contagem: quando os valores são inteiros pequenos dentro de um limite (de 0 a k, com k pequeno)
- Radix sort: ao ordenar muitos inteiros com largura de bits ou quantidade de dígitos conhecida
- Bucket sort: quando os dados são números de ponto flutuante distribuídos uniformemente em um intervalo conhecido
- Implemente sort de intercalação: quando for solicitado escrever do zero um sort estável O(n log n)
# Problem: sort array of 0s, 1s, 2s efficiently
# Counting sort: O(n), O(1) space (k=3 is tiny)
def sort_012(arr):
count = [0, 0, 0]
for n in arr:
count[n] += 1
i = 0
for val in range(3):
for _ in range(count[val]):
arr[i] = val; i += 1
arr = [2, 0, 2, 1, 1, 0]
sort_012(arr)
print(arr) # [0, 0, 1, 1, 2, 2]Sort sem sort: os k maiores com um montículo
Muitos problemas de entrevista pedem resultados “semelhantes a uma ordenação” sem exigir um sort completo. Para encontrar os k maiores elementos, um montículo mínimo de tamanho k executa em O(n log k) — mais rápido que O(n log n) quando k << n. Para encontrar o k-ésimo maior elemento, o quickselect tem tempo médio O(n). Para encontrar a mediana, a abordagem com dois montículos tem custo O(log n) por inserção. Vale conhecer essas abordagens de ordenação parcial como alternativas mais rápidas ao sort completo.
import heapq
# Top-k with heap: O(n log k)
def top_k(nums, k):
return heapq.nlargest(k, nums) # uses heap of size k internally
print(top_k([3,2,1,5,6,4], 2)) # [6, 5]
# kth largest: quickselect O(n) average
import random
def kth_largest(nums, k):
def _select(lo, hi, target):
if lo >= hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]; i = lo - 1
for j in range(lo, hi):
if nums[j] >= pivot: i+=1; nums[i],nums[j]=nums[j],nums[i]
nums[i+1],nums[hi]=nums[hi],nums[i+1]
p = i + 1
if p == target: return nums[p]
return _select(lo, p-1, target) if target < p else _select(p+1, hi, target)
return _select(0, len(nums)-1, k-1)
print(kth_largest([3,2,1,5,6,4], 2)) # 5Estabilidade do sort em ordenações por várias chaves
A estabilidade permite fazer uma ordenação correta por várias chaves: ordene primeiro pela chave secundária (de forma estável) e depois pela chave primária (também de forma estável). A ordem secundária é preservada em caso de empate na chave primária. Essa técnica é usada em bancos de dados (ORDER BY col1, col2) e no radix sort (cada passagem pelos dígitos precisa ser estável para que o algoritmo geral esteja correto). O sort do Python é sempre estável, portanto esse padrão funciona de modo confiável.
data = [
('Alice', 'Math', 90),
('Bob', 'Science', 85),
('Carol', 'Math', 90),
('Dave', 'Science', 90),
]
# Sort by score DESC, then by subject ASC (for ties)
# Step 1: sort by subject (secondary)
data.sort(key=lambda x: x[1])
# Step 2: sort by score DESC (primary, stable)
data.sort(key=lambda x: x[2], reverse=True)
for row in data:
print(row)
# All score=90 rows: Math before Science (preserved from step 1)Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação desta lição.
Resumo da lição
Nesta lição, você aprendeu: sorts baseados em comparação têm limite inferior O(n log n) — romper esse limite exige informações que não sejam de comparação, como inteiros limitados; o sort de contagem alcança O(n + k) ao contabilizar frequências, o radix sort processa dígitos com O(d × (n + k)) no total e o bucket sort aproveita a distribuição uniforme para obter O(n) em média; e o Timsort do Python é a opção padrão na prática — estável, O(n log n) no pior caso, O(n) no melhor caso e mais rápido que qualquer alternativa codificada manualmente para dados reais. A seguir, vamos dominar a busca binária clássica.
Perguntas Frequentes
A aula “Ordenações sem Comparação e o sort() do Python” é grátis?
Sim — o texto completo de “Ordenações sem Comparação e o sort() do Python” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Ordenações sem Comparação e o sort() do Python”?
Explore a ordenação por contagem e por radix para arrays de inteiros e entenda como o Timsort do Python funciona internamente nas chamadas de sort integradas. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Ordenações sem Comparação e o sort() do Python”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Ordenação por Bolhas e por Inserção
- Ordenação por Intercalação: Dividir, Ordenar, Intercalar
- Quick Sort e Seleção do Pivô
- Ordenações sem Comparação e o sort() do Python