Ordenação por Bolhas e por Inserção
Programe os dois algoritmos de ordenação quadráticos, entenda por que são O(n²) e reconheça o caso em que a ordenação por inserção supera a ordenação por intercalação.
Ordenação por Bolhas e por Inserção é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 1 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 DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
Por Que Estudar Ordenações O(n²)?
A ordenação por bolha e a ordenação por inserção requerem O(n²) no pior caso, o que as torna impraticáveis para entradas grandes. Ainda assim, toda entrevista séria sobre algoritmos espera que você saiba implementá-las e analisá-las. Elas ensinam conceitos fundamentais — comparação, troca, ordenação estável e comportamento no melhor caso — que se aplicam a algoritmos mais avançados. Os entrevistadores usam esses algoritmos para testar se você consegue raciocinar sobre invariantes de laço e notação assintótica a partir dos primeiros princípios.
# When O(n^2) is acceptable:
# n <= 1000: 10^6 ops, runs in milliseconds
# nearly-sorted data: insertion sort beats merge sort
# constant factor so small (simple ops) that overhead matters
import time
def time_sort(sort_fn, data):
import copy
arr = copy.copy(data)
t = time.perf_counter()
sort_fn(arr)
return time.perf_counter() - t
print('Small n: quadratic sorts are fine')Ordenação por Bolha: Fazendo o Máximo Subir
A ordenação por bolha percorre repetidamente o vetor e troca elementos adjacentes que estão fora de ordem. Depois de cada passagem completa, o maior elemento ainda não ordenado "sobe como uma bolha" até sua posição final no fim do vetor. Após n-1 passagens, todo o vetor está ordenado. O nome vem da maneira como os elementos maiores flutuam para cima, como bolhas. É o algoritmo de ordenação mais simples de descrever, mas raramente é usado na prática.
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # n-1 passes
for j in range(n - 1 - i): # inner loop shrinks
if arr[j] > arr[j+1]: # out of order
arr[j], arr[j+1] = arr[j+1], arr[j] # swap
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # [11, 12, 22, 25, 34, 64, 90]Ordenação por Bolha com Saída Antecipada
Uma ordenação por bolha otimizada usa um sinalizador swapped: se uma passagem interna completa não produzir nenhuma troca, o vetor já estará ordenado e a execução será encerrada antecipadamente. Isso proporciona o melhor caso O(n) para uma entrada já ordenada — a única vantagem genuína da ordenação por bolha. Sem esse sinalizador, o algoritmo sempre realiza O(n²) comparações. A otimização de saída antecipada é o que os entrevistadores verificam quando perguntam sobre melhorias na ordenação por bolha.
def bubble_sort_optimised(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # already sorted!
print(f'Sorted after pass {i+1}')
break
arr1 = [1, 2, 3, 4, 5] # already sorted
bubble_sort_optimised(arr1) # exits after 1 passAnálise da Complexidade da Ordenação por Bolha
O laço externo da ordenação por bolha executa n-1 vezes. O laço interno executa n-1-i vezes por passagem: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 comparações. Isso resulta em O(n²) no caso médio e no pior caso. Com o sinalizador de saída antecipada, o melhor caso cai para O(n) quando a entrada já está ordenada. A complexidade espacial é O(1) — apenas a troca exige uma variável temporária. A ordenação por bolha é estável: elementos iguais mantêm sua ordem relativa, pois trocamos apenas elementos estritamente maiores.
def bubble_sort_counted(arr):
n = len(arr)
swaps = comparisons = 0
for i in range(n-1):
for j in range(n-1-i):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swaps += 1
return comparisons, swaps
arr = [5, 4, 3, 2, 1] # worst case: reversed
c, s = bubble_sort_counted(arr)
print(f'Comparisons: {c}, Swaps: {s}') # 10, 10 for n=5Ordenação por Inserção: Construindo uma Mão de Cartas Ordenada
A ordenação por inserção imita a ordenação de uma mão de cartas: pegue a próxima carta — o elemento — e insira-a na posição correta entre as cartas já ordenadas à esquerda. O invariante é que arr[0:i] está sempre ordenado. Para cada novo elemento, desloque os elementos maiores para a direita a fim de abrir espaço. Esse algoritmo estável e executado no próprio lugar tem pior caso O(n²), mas melhor caso O(n) para dados quase ordenados.
def insertion_sort(arr):
for i in range(1, len(arr)): # start from second element
key = arr[i] # element to insert
j = i - 1
# Shift larger elements to the right
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key # insert in correct position
return arr
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr) # [5, 6, 11, 12, 13]Ordenação por Inserção Passo a Passo
Acompanhe a ordenação por inserção em [3, 1, 4, 2]: i=1, chave=1, desloque 3 para a direita → [1, 3, 4, 2]. i=2, chave=4, nenhum deslocamento → sem alteração. i=3, chave=2, desloque 4 e depois 3 para a direita → [1, 2, 3, 4]. Cada elemento é comparado com os elementos à sua esquerda até encontrarmos sua posição correta. O laço interno while realiza os deslocamentos usando atribuições — mais rápidas que trocas, pois cada deslocamento requer uma atribuição, em vez das três necessárias para uma troca.
def insertion_sort_trace(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j] # shift right (1 assignment)
j -= 1
arr[j+1] = key
print(f'After inserting {key}: {arr}')
insertion_sort_trace([3, 1, 4, 2])
# After inserting 1: [1, 3, 4, 2]
# After inserting 4: [1, 3, 4, 2] (no change)
# After inserting 2: [1, 2, 3, 4]Ordenação por Inserção em Dados Quase Ordenados
A principal vantagem da ordenação por inserção é sua complexidade O(n + inversões). Uma inversão é um par (i,j) em que i < j, mas arr[i] > arr[j]. Para vetores quase ordenados com poucas inversões, a ordenação por inserção é extremamente rápida — às vezes mais rápida que a ordenação por intercalação na prática, devido à sua simplicidade e ao padrão de acesso favorável à memória cache. O Timsort do Python usa ordenação por inserção em subvetores pequenos exatamente por esse motivo.
# Nearly sorted: only 1 inversion
arr1 = [1, 2, 4, 3, 5] # 4>3 is the only inversion
def count_ops(arr):
arr = arr[:]
ops = 0
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1; ops += 1
arr[j+1] = key
return ops
print(count_ops([1,2,4,3,5])) # 1 op (nearly sorted)
print(count_ops([5,4,3,2,1])) # 10 ops (reversed = worst case)Estabilidade na Ordenação
Um algoritmo de ordenação é estável se elementos iguais mantiverem sua ordem relativa original após a ordenação. Tanto a ordenação por bolha quanto a ordenação por inserção são estáveis — elas nunca trocam elementos iguais. A estabilidade é importante quando você ordena por várias chaves sequencialmente: ordene primeiro pela chave secundária, de forma estável, e depois pela chave primária, também de forma estável, para preservar a ordem da chave secundária entre os empates. A ordenação por intercalação também é estável; a ordenação por heap e a ordenação rápida geralmente não são.
# Stable sort preserves order of equal elements
students = [
('Alice', 85),
('Bob', 92),
('Carol', 85),
('Dave', 78),
]
# Sort by score ascending (stable: Alice before Carol for same score)
students.sort(key=lambda x: x[1])
for s in students:
print(s)
# ('Dave',78) ('Alice',85) ('Carol',85) ('Bob',92)
# Alice still comes before Carol => stableOrdenação por Inserção como Busca Binária
O laço interno da ordenação por inserção encontra a posição correta e desloca os elementos. Você pode usar a busca binária para encontrar a posição em O(log i) comparações, mas os deslocamentos ainda levam tempo O(i) — portanto, a complexidade geral permanece O(n²). Essa otimização reduz o número de comparações, o que é útil para funções de comparação dispendiosas, mas não reduz o total de operações. A ordenação por inserção binária aparece no Timsort para tamanhos pequenos de blocos.
import bisect
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
# Find insertion point in O(log i)
pos = bisect.bisect_left(arr, key, 0, i)
# Shift elements to make room: still O(i)
arr[pos+1:i+1] = arr[pos:i]
arr[pos] = key
return arr
print(binary_insertion_sort([5, 2, 4, 6, 1, 3]))
# [1, 2, 3, 4, 5, 6]Bolha versus Inserção: Quando Usar Cada Uma
Em entrevistas, declare esta comparação com confiança: a ordenação por inserção é estritamente melhor que a ordenação por bolha — ambas requerem O(n²) no pior caso e espaço O(1), mas a ordenação por inserção realiza menos escritas (O(n+k) para k inversões, contra O(n²) para a ordenação por bolha), aproveita melhor a memória cache e é a escolha prática para valores pequenos de n — o Timsort a utiliza. A única vantagem real da ordenação por bolha é a simplicidade didática. Em produção, use sempre a função sort integrada à linguagem.
# Summary: when to use quadratic sorts
# Use insertion_sort when:
# - n <= 20 (small enough that O(n^2) is fine)
# - data is nearly sorted (few inversions => fast)
# - you need stable sort with O(1) space
# - implementing a hybrid (like Timsort)
# NEVER use bubble_sort in production code
# Python's built-in sort: O(n log n), stable, extremely fast
arr = [5, 2, 8, 1, 9]
print(sorted(arr)) # [1, 2, 5, 8, 9]
arr.sort()
print(arr) # [1, 2, 5, 8, 9]Contagem de Inversões como Métrica
O número de inversões em um vetor é igual ao número de pares (i,j) em que i < j, mas arr[i] > arr[j]. A ordenação por inserção realiza exatamente tantos deslocamentos quanto o número de inversões — uma observação útil. A contagem eficiente de inversões, em O(n log n), exige uma ordenação por intercalação modificada. Às vezes, os entrevistadores perguntam "o quanto seu algoritmo leva as inversões em consideração?" como extensão de discussões sobre ordenação.
# Count inversions: naive O(n^2)
def count_inversions_naive(arr):
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_naive([3, 1, 2])) # 2: (3,1) and (3,2)
print(count_inversions_naive([1, 2, 3])) # 0: already sorted
print(count_inversions_naive([3, 2, 1])) # 3: all pairs invertedVerificação Rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação apresentados nesta lição.
Resumo da Lição
Nesta lição, você aprendeu que: a ordenação por bolha faz n-1 passagens, cada uma levando o máximo atual à sua posição final, com pior caso O(n²), mas melhor caso O(n) quando se usa o sinalizador de saída antecipada; a ordenação por inserção desloca os elementos para a direita a fim de inserir a chave atual na posição ordenada correta, executando em tempo O(n + inversões), o que a torna ideal para dados quase ordenados; e ambos os algoritmos são estáveis, usam espaço O(1) e têm pior caso O(n²) — mas a ordenação por inserção é estritamente preferível à ordenação por bolha em todos os cenários práticos. A seguir, implementaremos a ordenação por intercalação do zero.
Perguntas Frequentes
A aula “Ordenação por Bolhas e por Inserção” é grátis?
Sim — o texto completo de “Ordenação por Bolhas e por Inserção” é 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 DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Ordenação por Bolhas e por Inserção”?
Programe os dois algoritmos de ordenação quadráticos, entenda por que são O(n²) e reconheça o caso em que a ordenação por inserção supera a ordenação por intercalação. Você pratica DSA 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 DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA 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 1 de 4.
Quanto tempo leva a aula “Ordenação por Bolhas e por Inserção”?
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 DSA Interview Prep?
Sim. Cada aula de DSA 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