Ordenação
Colocando itens em ordem
- Sorting organiza uma lista em ordem, geralmente do menor para o maior.
- O movimento chave é um swap: trocar dois itens.
- No Python:
a[i], a[j] = a[j], a[i]troca dois itens de lista em uma linha.
Bubble sort
- Compare cada par de vizinhos; troque-os se estiverem fora de ordem.
- Após uma passagem completa, o maior item "borbulhou" até o final.
- Repita as passagens. Após
n − 1passagens a lista está certamente ordenada; você pode parar antes se uma passagem não realizar trocas.
data = [3, 1, 2]
n = len(data)
for i in range(n - 1):
for j in range(n - 1 - i):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
print(data)
Insertion sort
- Trate a parte esquerda da lista como já ordenada.
- Pegue o próximo item e deslize-o para a esquerda até ficar no lugar certo.
- Como organizar cartas de baralho na mão, uma de cada vez.
data = [3, 1, 2]
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0 and data[j] > key:
data[j + 1] = data[j]
j = j - 1
data[j + 1] = key
print(data)
Compare-os
- Ambos verificam aproximadamente
n × npares, então ambos são lentos em listas grandes. - Insertion sort é rápido quando a lista já está quase ordenada.
- Métodos mais rápidos existem, mas bubble e insertion são fáceis de entender.
Em pseudocódigo do Cambridge
- Ordenação bolha com uma variável
temppara a troca, sobre um arraylist[1:n].
FOR i ← 1 TO n - 1
FOR j ← 1 TO n - i
IF list[j] > list[j + 1] THEN
temp ← list[j]
list[j] ← list[j + 1]
list[j + 1] ← temp
ENDIF
NEXT j
NEXT i
Erros comuns
- Bubble e insertion sort são ambos O(n²).
- Rastreie uma lista pequena à mão para verificar se seu sort funciona.
Agora você tenta
- Cada tarefa altera a lista in place — não há necessidade de retorná-la.
- Clique em Check answer para testar seu código.
Watch a sort run
Sorting repeatedly compares and swaps until everything is in order.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Write swap(items, i, j) that exchanges the items at index i and index j in the list. Change the list in place (no return).
Clique em Executar para ver a saída aqui.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Write bubble_sort(items) that sorts the list into ascending order using bubble sort. Change the list in place.
Clique em Executar para ver a saída aqui.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Write insertion_sort(items) that sorts the list into ascending order using insertion sort. Change the list in place.
Clique em Executar para ver a saída aqui.