Bubble sort e selection sort em Python, passo a passo

Ordenar uma lista é uma das tarefas mais antigas da programação: colocar notas em ordem, listar nomes em ordem alfabética, ordenar leituras de um sensor para achar a mediana. O Python já tem sorted() e sort() prontos, e é o que se usa no dia a dia, como o artigo seguinte mostra. Então por que aprender a ordenar à mão? Porque escrever um algoritmo de ordenação treina, num problema pequeno, tudo o que programar exige: laços aninhados, índices, troca de valores, contadores, casos de borda e testes. E porque entender o que acontece dentro do sorted() ajuda a perceber por que ordenar custa trabalho.

Este artigo apresenta os dois algoritmos mais simples. O bubble sort compara vizinhos e troca os que estão fora de ordem, repetidas vezes. O selection sort procura o menor elemento e o coloca na primeira posição, depois procura o menor entre os que sobraram e o coloca na segunda, e assim por diante. Os dois estão longe de ser os mais rápidos, mas são fáceis de enxergar, e é justamente isso que os torna bons para aprender. Todos os exemplos rodaram no simulador, e os resultados citados são os que ele produz.

A troca de dois valores

Os dois algoritmos são feitos de uma operação só, repetida: trocar dois elementos de lugar. Em Python, a troca se escreve numa linha, com atribuição múltipla:

lista = [10, 20, 30]
lista[0], lista[2] = lista[2], lista[0]
print(lista)
a = 1
b = 2
a, b = b, a
print(a, b)
print("fim")

A saída é [30, 20, 10], depois 2 1 e por fim fim. O lado direito, lista[2], lista[0], é calculado inteiro antes de qualquer atribuição, e só então os valores são guardados nas posições da esquerda. É a mesma tupla que o artigo sobre tuplas e desempacotamento apresentou. Em outras linguagens, a troca pede uma variável auxiliar, e aqui ela não é necessária. Mais adiante veremos o que acontece quando se tenta trocar com duas atribuições separadas, porque é um erro que quase todo mundo comete uma vez.

Bubble sort: trocar vizinhos

A ideia do bubble sort, ou ordenação por bolhas, é percorrer a lista comparando cada elemento com o vizinho da direita. Se estão fora de ordem, troca. Ao fim de uma passada completa, o maior valor chegou ao final da lista, como uma bolha que sobe. Repete-se a passada, agora ignorando a última posição, que já está certa, e depois as duas últimas, até a lista inteira ficar em ordem.

def bubble(lista):
    n = len(lista)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista

nums = [5, 1, 4, 2, 8]
print(bubble(nums))
print(nums)
print(bubble([3, 3, 1]), bubble([]), bubble([7]), bubble([1, 2, 3]))

def bubble_passos(lista):
    n = len(lista)
    for i in range(n - 1):
        trocou = False
        for j in range(n - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
                trocou = True
        print("passada", i + 1, lista, "trocou" if trocou else "sem trocas")
        if not trocou:
            break
    return lista
bubble_passos([5, 1, 4, 2, 8])
bubble_passos([1, 2, 3, 4, 5])

def bubble_conta(lista):
    comparacoes = 0
    trocas = 0
    n = len(lista)
    for i in range(n - 1):
        trocou = False
        for j in range(n - 1 - i):
            comparacoes += 1
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
                trocas += 1
                trocou = True
        if not trocou:
            break
    return comparacoes, trocas
print(bubble_conta([5, 1, 4, 2, 8]))
print(bubble_conta([1, 2, 3, 4, 5]))
print(bubble_conta([5, 4, 3, 2, 1]))
print("fim")

A saída começa com [1, 2, 4, 5, 8] duas vezes, e depois [1, 3, 3] [] [7] [1, 2, 3]. Em seguida vêm as passadas da primeira lista: passada 1 [1, 4, 2, 5, 8] trocou, passada 2 [1, 2, 4, 5, 8] trocou e passada 3 [1, 2, 4, 5, 8] sem trocas. A segunda lista, que já estava em ordem, dá só passada 1 [1, 2, 3, 4, 5] sem trocas. Depois vêm os três pares de contagens, (9, 4), (4, 0) e (10, 10), e por fim fim.

Vale ler a função bubble com calma, porque os dois limites dos laços são o ponto delicado:

• O laço de fora, for i in range(n - 1), conta as passadas. Uma lista de n elementos precisa de no máximo n - 1 passadas, porque a cada passada um elemento ganha seu lugar definitivo, e o último sobra sozinho, já certo.
• O laço de dentro, for j in range(n - 1 - i), percorre os pares. Compara lista[j] com lista[j + 1], e por isso j só pode ir até n - 2, para o vizinho existir. O - i reflete que, na passada i, os últimos i elementos já estão fixos e não precisam mais ser olhados.
• O if compara e, se o da esquerda for maior, troca os dois. A comparação com > e não com >= evita trocar valores iguais à toa.

O primeiro resultado mostra algo que quem vem de outras linguagens pode estranhar: o print(nums) mostra a lista já ordenada. A função alterou a própria lista, e não uma cópia, porque as listas são mutáveis e a função recebeu a lista inteira, não um valor copiado. O return lista é uma conveniência, para poder escrever print(bubble(nums)), mas a lista original foi mudada de qualquer jeito.

As linhas seguintes testam os casos de borda: valores repetidos, lista vazia, lista de um elemento e lista já ordenada. Todos funcionam. No de lista vazia, n - 1 vale -1, e o range de um número negativo não gera nenhuma volta, então nada acontece.

Parar quando nada mais troca

A versão bubble_passos mostra a melhoria mais conhecida do algoritmo. Se uma passada inteira não troca nada, a lista já está ordenada, e continuar seria perda de tempo. A variável trocou guarda isso: começa False a cada passada, vira True na primeira troca, e, se ao final continuar False, o break encerra tudo. Na lista [5, 1, 4, 2, 8], três passadas bastam, e a terceira só confirma. Na lista já ordenada, uma passada resolve.

A função bubble_conta mede o trabalho. Para a lista [5, 1, 4, 2, 8], foram 9 comparações e 4 trocas. Para a já ordenada, 4 comparações e nenhuma troca: é o melhor caso, e a parada antecipada o torna barato. Para a lista invertida [5, 4, 3, 2, 1], o pior caso, foram 10 comparações e 10 trocas, ou seja, toda comparação virou uma troca.

Selection sort: escolher o menor

O selection sort, ordenação por seleção, pensa de outro jeito. Em vez de trocar vizinhos o tempo todo, escolhe o elemento certo para cada posição. Na primeira passada, procura o menor valor de toda a lista e o coloca na posição 0. Na segunda, procura o menor entre os que sobraram, da posição 1 em diante, e o coloca na posição 1. A parte da esquerda, já ordenada, vai crescendo, e a da direita, ainda por ordenar, vai encolhendo.

def selection(lista):
    n = len(lista)
    for i in range(n - 1):
        menor = i
        for j in range(i + 1, n):
            if lista[j] < lista[menor]:
                menor = j
        if menor != i:
            lista[i], lista[menor] = lista[menor], lista[i]
    return lista

print(selection([64, 25, 12, 22, 11]))
print(selection([3, 3, 1]), selection([]), selection([7]), selection([1, 2, 3]))

def selection_passos(lista):
    n = len(lista)
    for i in range(n - 1):
        menor = i
        for j in range(i + 1, n):
            if lista[j] < lista[menor]:
                menor = j
        print("passada", i + 1, "menor", lista[menor], "na posicao", menor)
        if menor != i:
            lista[i], lista[menor] = lista[menor], lista[i]
        print("   ", lista)
    return lista
selection_passos([64, 25, 12, 22, 11])

def selection_conta(lista):
    comparacoes = 0
    trocas = 0
    n = len(lista)
    for i in range(n - 1):
        menor = i
        for j in range(i + 1, n):
            comparacoes += 1
            if lista[j] < lista[menor]:
                menor = j
        if menor != i:
            lista[i], lista[menor] = lista[menor], lista[i]
            trocas += 1
    return comparacoes, trocas
print(selection_conta([64, 25, 12, 22, 11]))
print(selection_conta([1, 2, 3, 4, 5]))
print(selection_conta([5, 4, 3, 2, 1]))
print("fim")

A saída começa com [11, 12, 22, 25, 64] e [1, 3, 3] [] [7] [1, 2, 3]. O passo a passo é passada 1 menor 11 na posicao 4 seguido de [11, 25, 12, 22, 64], depois passada 2 menor 12 na posicao 2 seguido de [11, 12, 25, 22, 64], depois passada 3 menor 22 na posicao 3 seguido de [11, 12, 22, 25, 64], e passada 4 menor 25 na posicao 3 com a lista igual. As contagens são (10, 3), (10, 0) e (10, 2), e por fim fim.

O coração da função é a variável menor, que guarda a posição do menor valor visto até agora. Ela começa em i, o primeiro lugar da parte não ordenada. O laço de dentro, for j in range(i + 1, n), olha todos os que vêm depois e atualiza menor quando acha um valor menor. Guardar a posição, e não o valor, é o que permite trocar no fim. Só depois do laço de dentro terminar é que se faz a troca, e só se menor != i: quando o menor já está no lugar, como na passada 4 do exemplo, não há o que trocar.

Esse laço é uma busca pelo mínimo, a mesma varredura do desafio Maior da Lista, só que pelo menor. O selection sort é, portanto, a busca do artigo anterior repetida várias vezes, cada uma sobre uma parte menor da lista.

Repare na diferença de comportamento nas contagens. O selection faz 10 comparações nas três listas de 5 elementos, não importa a ordem em que elas estão: ele sempre varre a parte que falta, mesmo quando a lista já está ordenada. Em compensação, as trocas são poucas: 3 para a primeira lista, 0 para a ordenada e 2 para a invertida. No máximo uma troca por passada, ou seja, nunca mais de n - 1 no total.

Os dois lado a lado

def bubble_conta(lista):
    comparacoes = 0
    trocas = 0
    n = len(lista)
    for i in range(n - 1):
        trocou = False
        for j in range(n - 1 - i):
            comparacoes += 1
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
                trocas += 1
                trocou = True
        if not trocou:
            break
    return comparacoes, trocas
def selection_conta(lista):
    comparacoes = 0
    trocas = 0
    n = len(lista)
    for i in range(n - 1):
        menor = i
        for j in range(i + 1, n):
            comparacoes += 1
            if lista[j] < lista[menor]:
                menor = j
        if menor != i:
            lista[i], lista[menor] = lista[menor], lista[i]
            trocas += 1
    return comparacoes, trocas
for n in [5, 10, 100]:
    inv = list(range(n, 0, -1))
    ord_ = list(range(1, n + 1))
    print(n, "bubble inv", bubble_conta(inv[:]), "ord", bubble_conta(ord_[:]), "| selection inv", selection_conta(inv[:]), "ord", selection_conta(ord_[:]))
dados = [37, 5, 91, 12, 5, 64, 28, 3, 77, 50]
a = dados[:]
b = dados[:]
bubble_conta(a)
selection_conta(b)
print(a)
print(b)
print(a == sorted(dados), b == sorted(dados), a == b)
print(dados)
print("fim")

A saída traz três linhas de contagem, 5 bubble inv (10, 10) ord (4, 0) | selection inv (10, 2) ord (10, 0), 10 bubble inv (45, 45) ord (9, 0) | selection inv (45, 5) ord (45, 0) e 100 bubble inv (4950, 4950) ord (99, 0) | selection inv (4950, 50) ord (4950, 0). Depois, duas vezes [3, 5, 5, 12, 28, 37, 50, 64, 77, 91], depois True True True, depois a lista original [37, 5, 91, 12, 5, 64, 28, 3, 77, 50] e fim.

Os números mostram um padrão que vale decorar. Numa lista de n elementos, o número de comparações da versão sem parada antecipada é n * (n - 1) / 2: com 5 elementos, 10; com 10, 45; com 100, 4950. Dez vezes mais elementos, de 10 para 100, e as comparações vão de 45 a 4950, mais de cem vezes mais. O trabalho cresce com o quadrado do tamanho da lista, e é por isso que esses dois algoritmos servem para listas pequenas e passam a pesar nas grandes. O artigo sobre a complexidade de algoritmos, no fim desta parte, dá um nome a esse crescimento.

As diferenças práticas entre os dois são estas:

• Lista já ordenada. O bubble com parada antecipada faz só n - 1 comparações e nenhuma troca. O selection continua fazendo todas as comparações.
• Lista invertida. O bubble troca em toda comparação, 4950 trocas para 100 elementos. O selection faz só 50, a metade do tamanho, porque cada troca coloca um elemento definitivamente no lugar e ainda tira outro do caminho.
• Troca é mais cara que comparação. Quando trocar custa caro, como mover registros grandes ou gravar numa memória lenta, o selection leva vantagem. Quando a lista já vem ordenada, ou quase, o bubble com parada antecipada costuma levar vantagem.

Na última parte do exemplo, as duas versões ordenam uma cópia da lista, feita com dados[:], e a original continua intacta. As duas dão o mesmo resultado, igual ao do sorted(dados), o que confirma que o código está certo. Comparar com o sorted é um bom teste para qualquer algoritmo de ordenação que você escrever.

Variações: decrescente, textos e registros

O mesmo esqueleto serve para outras ordens. Basta mudar a comparação, ou o que se compara:

def bubble_desc(lista):
    n = len(lista)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if lista[j] < lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista
print(bubble_desc([5, 1, 4, 2, 8]))
def bubble_texto(lista):
    n = len(lista)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista
print(bubble_texto(["caio", "ana", "dora", "bia"]))
print(bubble_texto(["b", "B", "a", "A"]))
alunos = [{"nome": "Ana", "nota": 8.5}, {"nome": "Bruno", "nota": 6.0}, {"nome": "Carla", "nota": 9.5}, {"nome": "Davi", "nota": 7.0}]
def ordenar_por_nota(lista):
    n = len(lista)
    for i in range(n - 1):
        menor = i
        for j in range(i + 1, n):
            if lista[j]["nota"] < lista[menor]["nota"]:
                menor = j
        if menor != i:
            lista[i], lista[menor] = lista[menor], lista[i]
    return lista
for a in ordenar_por_nota(alunos):
    print(a["nome"], a["nota"])
pares = [(3, "c"), (1, "a"), (2, "b")]
print(bubble_texto(pares))
print("fim")

A saída é [8, 5, 4, 2, 1], depois ['ana', 'bia', 'caio', 'dora'], depois ['A', 'B', 'a', 'b'], depois quatro linhas Bruno 6.0, Davi 7.0, Ana 8.5, Carla 9.5, depois [(1, 'a'), (2, 'b'), (3, 'c')] e fim.

Para a ordem decrescente, o > vira <, e o maior valor vai para o começo. Para textos, a mesma função funciona sem mudar uma letra, porque o > compara textos em ordem alfabética, como visto no artigo sobre strings. O resultado com "b", "B", "a" e "A" lembra que a comparação usa a tabela de caracteres: as maiúsculas vêm antes das minúsculas.

Para registros, como uma lista de dicionários, o que muda é o que se compara: em vez de lista[j] < lista[menor], escreve-se lista[j]["nota"] < lista[menor]["nota"], comparando o campo escolhido. Os alunos saem do menor ao maior em nota, e a troca continua sendo a dos dicionários inteiros, de modo que cada nome acompanha a sua nota. Já a lista de tuplas é ordenada pelo primeiro campo, e o segundo só desempata, porque a comparação de tuplas olha elemento a elemento.

Na ESP32: mediana de leituras e ranking

Sensores dão leituras ruidosas. O sensor de distância HC-SR04, por exemplo, pode devolver de vez em quando um valor absurdo. Uma saída comum é o filtro de mediana: lê-se o sensor algumas vezes, ordena-se as leituras e fica-se com a do meio, que ignora os extremos.

def ordenar(lista):
    n = len(lista)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista

def mediana(leituras):
    copia = leituras[:]
    ordenar(copia)
    return copia[len(copia) // 2]

distancias = [12.4, 12.6, 98.0, 12.5, 12.7]
print(mediana(distancias))
print(distancias)
print(round(sum(distancias) / len(distancias), 1))
temps = [("sala", 24.5), ("quarto", 22.0), ("cozinha", 27.5), ("varanda", 21.0)]
n = len(temps)
for i in range(n - 1):
    menor = i
    for j in range(i + 1, n):
        if temps[j][1] < temps[menor][1]:
            menor = j
    temps[i], temps[menor] = temps[menor], temps[i]
for nome, t in temps:
    print(nome, t)
print("fim")

A saída é 12.6, depois [12.4, 12.6, 98.0, 12.5, 12.7], depois 29.6, depois varanda 21.0, quarto 22.0, sala 24.5 e cozinha 27.5, e por fim fim.

A leitura 98.0 é um erro do sensor, e a média das cinco leituras dá 29.6, muito distante da realidade, porque um valor ruim puxa a conta. A mediana dá 12.6, que é o valor típico. A função mediana ordena uma cópia, com leituras[:], e por isso a lista distancias continua na ordem original, como a segunda linha mostra. O índice len(copia) // 2 pega o elemento do meio, e vale para quantidades ímpares de leituras. O artigo sobre sensores DHT22, HC-SR04 e PIR mostra como obter essas leituras na placa. Como a mediana pede ordenar pouquíssimos valores, um algoritmo simples é mais do que suficiente.

O segundo exemplo é um ranking: ordenar cômodos por temperatura, do mais frio ao mais quente. Cada item é uma tupla (nome, temperatura), e a comparação olha o campo [1]. O for nome, t in temps desempacota cada tupla, outro recurso do artigo sobre tuplas.

Erros comuns

O primeiro erro é deixar o laço de dentro ir longe demais:

def bubble_erro(lista):
    n = len(lista)
    for i in range(n):
        for j in range(n):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista
print(bubble_erro([3, 1, 2]))

IndexError: list index out of range

Com j indo até n - 1, o lista[j + 1] olha uma posição que não existe. O limite correto é n - 1, ou seja, range(n - 1) ou, melhor, range(n - 1 - i).

O segundo é comparar elementos de tipos diferentes, como um número e um texto:

lista = [3, "1", 2]
for i in range(len(lista) - 1):
    for j in range(len(lista) - 1 - i):
        if lista[j] > lista[j + 1]:
            lista[j], lista[j + 1] = lista[j + 1], lista[j]

TypeError: unsupported types for __gt__: 'int', 'str'

No Python de computador, a mensagem é '>' not supported between instances of 'int' and 'str'. Isso acontece quando as leituras vêm de input() e ninguém as converteu com int() ou float(). A ordenação só funciona entre valores comparáveis.

Armadilhas silenciosas

Os piores erros de ordenação são os que não dão mensagem. O mais clássico é a troca feita com duas atribuições:

def troca_errada(lista):
    for i in range(len(lista) - 1):
        for j in range(len(lista) - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j] = lista[j + 1]
                lista[j + 1] = lista[j]
    return lista
print(troca_errada([5, 1, 4, 2, 8]))
def bubble_sem_return(lista):
    for i in range(len(lista) - 1):
        for j in range(len(lista) - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
x = [3, 1, 2]
r = bubble_sem_return(x)
print(r, x)
y = [3, 1, 2]
print(y.sort(), y)
z = [3, 1, 2]
print(sorted(z), z)
print("fim")

A saída é [1, 1, 2, 2, 8], depois None [1, 2, 3], depois None [1, 2, 3], depois [1, 2, 3] [3, 1, 2] e por fim fim.

Na troca_errada, a primeira atribuição, lista[j] = lista[j + 1], apaga o valor antigo de lista[j]. A segunda copia o valor que acabou de ser copiado, e o valor original se perdeu. O resultado, [1, 1, 2, 2, 8], tem o tamanho certo e parece ordenado, mas o 5 e o 4 sumiram, e o 1 e o 2 aparecem duas vezes. É o erro que a atribuição múltipla evita: lista[j], lista[j + 1] = lista[j + 1], lista[j] calcula os dois lados antes de guardar.

A segunda armadilha é a função que ordena no lugar mas não tem return. Ela funciona, a lista x fica ordenada, mas quem escreve r = bubble_sem_return(x) recebe None. O mesmo vale para o método sort() das listas: ele ordena no lugar e devolve None, como a terceira linha mostra. Quem escreve y = y.sort() perde a lista. Já o sorted() devolve uma lista nova e deixa a original como estava, como a última linha mostra.

A terceira armadilha são os limites dos laços:

def limite_errado(lista):
    n = len(lista)
    for i in range(n - 1):
        for j in range(n - 1):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista
print(limite_errado([5, 1, 4, 2, 8]))
def passada_curta(lista):
    n = len(lista)
    for i in range(n - 2):
        for j in range(n - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista
print(passada_curta([5, 4, 3, 2, 1]))
print("fim")

A saída é [1, 2, 4, 5, 8], depois [2, 1, 3, 4, 5] e por fim fim. Na limite_errado, o laço de dentro vai sempre até o fim, sem o - i. Isso não quebra nada, porque comparar posições já ordenadas não altera nada. Só faz comparações a mais. Na passada_curta, o laço de fora tem uma passada a menos, n - 2 em vez de n - 1, e a lista invertida sai quase ordenada, [2, 1, 3, 4, 5], sem nenhum aviso. Testar só com listas fáceis não revela esse defeito, e por isso vale sempre testar com uma lista invertida.

O que costuma aparecer em sala

São padrões que se repetem com quem aprende ordenação. Não são relato de uma turma específica.

Trocar com duas atribuições. É o campeão, como mostrado. O resultado tem valores repetidos, e a pessoa procura o defeito na comparação, quando o problema está na troca.

O IndexError do j + 1. Aparece quando o laço de dentro usa range(n). Entender por que o último elemento não tem vizinho à direita resolve de vez.

Esquecer de olhar a segunda passada. Muita gente testa uma lista que se ordena numa passada só, e conclui que o código está certo. Uma lista invertida, que exige todas as passadas, é o teste que importa.

Confundir menor com o valor. No selection sort, guardar o valor do menor em vez da posição. Sem a posição, não há como trocar, e o programa ou falha ou ordena errado.

Trocar dentro do laço de busca. No selection, fazer a troca a cada novo "menor" encontrado, em vez de só no fim. O algoritmo vira uma mistura dos dois e faz trocas demais.

Ordenar a lista original sem querer. A função altera a lista recebida. Quem precisava da ordem original perde os dados. A cópia com lista[:] antes de ordenar é o remédio.

y = y.sort(). A lista vira None e o programa continua até falhar mais adiante, longe do erro.

Achar que o sorted() é "trapaça". Na prática, é o que se usa. Escrever à mão serve para entender, e não para substituir a função pronta. O próximo artigo mostra quando cada um se aplica.

Exercício: ordenar e relatar

Escreva um programa que leia a quantidade n de números, depois os n valores, ordene-os com bubble sort com parada antecipada, e mostre a lista antes e depois, o número de passadas feitas, o menor e o maior valor. O bloco usa entradas= para fornecer 5 números: 5, 1, 4, 2 e 8.

n = int(input())
lista = []
for i in range(n):
    lista.append(int(input()))
print("antes", lista)
passadas = 0
for i in range(n - 1):
    trocou = False
    for j in range(n - 1 - i):
        if lista[j] > lista[j + 1]:
            lista[j], lista[j + 1] = lista[j + 1], lista[j]
            trocou = True
    passadas += 1
    if not trocou:
        break
print("depois", lista)
print("passadas", passadas)
print("menor", lista[0], "maior", lista[-1])
print("fim")

O simulador repete na saída os valores digitados, um por linha, e depois vêm antes [5, 1, 4, 2, 8], depois [1, 2, 4, 5, 8], passadas 3, menor 1 maior 8 e fim.

Repare que, depois de ordenada, o menor valor está sempre na primeira posição e o maior na última, e por isso lista[0] e lista[-1] bastam. A contagem das passadas só soma depois de terminar o laço de dentro, e o break sai quando uma passada não troca nada, o que explica as 3 passadas: duas com trocas e uma de confirmação.

Para treinar, tente: ordenar do maior ao menor; trocar o bubble pelo selection e comparar o número de trocas; contar as comparações e mostrar o total; e ordenar uma lista de textos lida do teclado, uma palavra por vez.

Perguntas frequentes

Por que aprender bubble sort se existe o sorted()? Porque o algoritmo treina laços, índices e troca de valores, e porque entender o custo de ordenar ajuda a decidir quando e como ordenar. Para o código de verdade, o sorted() e o sort() são a escolha.

Qual dos dois é melhor? Depende. O bubble com parada antecipada ganha em listas quase ordenadas. O selection ganha quando trocar é caro, porque faz poucas trocas. Nenhum dos dois serve para listas grandes.

O bubble sort ordena a lista original? A função que escrevemos, sim: ela troca elementos na própria lista. Para preservar a original, ordene uma cópia, feita com lista[:].

Por que a comparação é > e não >=? Com >=, valores iguais seriam trocados sem necessidade, e o algoritmo faria trabalho à toa. Com >, valores iguais ficam onde estão.

O selection sort sempre faz o mesmo número de comparações? Sim: n * (n - 1) / 2, qualquer que seja a ordem inicial da lista, como mostraram as contagens. O que muda é o número de trocas.

Quanto tempo leva ordenar 100 elementos? Cerca de 4950 comparações, o que no computador é instantâneo. O ponto é como o trabalho cresce: com 1000 elementos, seriam cerca de 500 mil. É o assunto do artigo sobre complexidade.

Para continuar

Os desafios Lista ao Contrário, Maior da Lista e Média da Lista praticam o percurso e a escolha de elementos que os dois algoritmos usam. Para rever a base, vale passar pelos artigos sobre listas, busca linear e binária e tuplas, e pela trilha de lógica.

O próximo artigo apresenta o insertion sort, o terceiro algoritmo simples de ordenação, e mostra quando vale usar o sorted() no lugar de escrever o seu.