Bubble sort — Passo a passo

Entendendo o infame algoritmo de ordenação.

fonte: https://bit.ly/2CrqzLu

Se você estuda/estudou computação, provavelmente já ouviu falar do Bubble Sort. Tirando o fato de que ele é conhecidamente ineficiente, sua implementação é relativamente fácil e entendê-lo pode ser uma porta de entrada para o universo dos algoritmos de ordenação.

De onde vem o nome Bubble Sort?

De uma suposta analogia do processo de ordenamento com um “bolhas emergindo em um tanque de água”.

O que vamos ordenar?

Uma pequena lista de inteiros : [7, 3, 6, 2, 0].

Como vamos ordenar?

Cada elemento será comparado com os adjacentes, de maneira que a cada “passada” o maior elemento será deslocado para o fim da lista. Exemplificando fica mais fácil:

Primeira iteração:

Estado inicial antes da primeira iteração: [3, 7, 6, 2, 0]
7 > 3? Sim, realiza a troca:
[3, 7, 6, 2, 0]
7 > 6? Sim, realiza a troca:
[3, 6, 7, 2, 0]
7 > 2? Sim, realiza a troca:
[3, 6, 2, 7, 0]
7 > 0? Sim, realiza a troca:
[3, 6, 2, 0, 7]
Estado final após a primeira iteração: [3, 6, 2, 0, 7]

Observe que o maior número foi para o fim, assim como um bolha emerge do fundo para a superfície de um tanque de água!

Segunda iteração:

Estado inicial antes da segunda iteração: [3, 6, 2, 0, 7] 
3 > 6? Não, vá para o próximo:
[3, 6, 2, 0, 7]
6 > 2? Sim, realiza a troca:
[3, 2, 6, 0, 7]
6 > 0? Sim, realiza a troca:
[3, 2, 0, 6, 7]
6 > 7? Não, como não existe próximo, acaba aqui.
[3, 2, 0, 6, 7]
Estado final após a segunda iteração: [3, 2, 0, 6, 7]

Observe que o segundo maior número foi para o penúltimo lugar, logo antes do maior.

Terceira iteração:

Estado inicial antes da terceira iteração: [3, 2, 0, 6, 7]
3 > 2? Sim, realiza a troca:[7, 3, 6, 2, 0]
[2, 3, 0, 6, 7]
3 > 0? Sim, realiza a troca:
[2, 0, 3, 6, 7]
3 > 6? Não, mantém o estado atual e vai para o próximo:
[2, 0, 3, 6, 7]
3 > 6? Não, como não existe próximo, acaba aqui.
[2, 0, 3, 6, 7]
Estado final após a terceira iteração: [2, 0, 3, 6, 7]

Novamente, observe que o terceiro maior número se tornou o antepenúltimo

Quarta iteração:

Estado inicial antes da quarta iteração: [2, 0, 3, 6, 7]
2 > 0 ? Sim, realiza a troca:
[0, 2, 3, 6, 7]
2 > 3? Não, mantém o estado atual e vai para o próximo:
[0, 2, 3, 6, 7]
2 > 6? Não, mantém o estado atual e vai para o próximo:
[0, 2, 3, 6, 7]
2 > 7? Não, como não existe próximo, acaba aqui:
[0, 2, 3, 6, 7]
Estado final após a quarta iteração: [2, 0, 3, 6, 7]

Nossa lista finalmente está ordenada! Observe que, justamente pelo fato dos maiores números “borbulharem” para o fim, a última iteração só realizou uma troca, as demais nem precisariam ser feitas.

Pois bem, vamos agora implementar o algoritmo em Python ❤

Primeira implementação

Propositalmente não otimizada:

numbers = [7, 3, 6, 2, 0]
size = len(numbers)
for i in range(size -1): 
    for j in range (size -1):
        if numbers[j] > numbers[j + 1]:
            numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]

Descrição do raciocínio:

Para cada item na lista: (primeiro for)
    Compare com todos os itens: (segundo for)
        Se o item atual for maior que o seguinte: (if)
            Troque eles de posição (atual,seguinte = seguinte,atual)

Bem simples, não? Já é uma implementação funcional do algoritmo Bubble Sort.

Segunda implementação

Evitando comparações desnecessárias.

se você observar bem, a cada iteração um número é “empurrado” para o fim da lista. No nosso caso foi mais ou menos assim:

[. . . . 7]
[. . . 6 7]
[. . 3 6 7]
[. 2 3 6 7]
[0 2 3 6 7]

Sendo assim, concorda comigo que a cada iteração nós temos um índice a menos para se preocupar? Em outras palavras, a cada iteração, um índice é definitivamente ordenado.

Vamos otimizar nossa implementação inicial:

numbers = [7, 3, 6, 2, 0]
size = len(numbers)
for i in range(size -1): 
    for j in range (size -i -1):
        if numbers[j] > numbers[j + 1]:
            numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]

Observe que agora nós subtraímos o valor de i no segundo laço for. O motivo é:

1 — Na primeira iteração o número 7 é ordenado e posicionado no fim da lista:

[. . . . 7]

Nessa iteração, i vale 0, então verificamos todos os índices no segundo laço.

2 — Na segunda iteração, podemos considerar que o último índice já se encontra ordenado, certo? Sendo assim, precisamos realmente ir até o último índice? Não! é aí que entra o nosso -i no segundo laço:

...
    for j in range (size -i -1):
...

Observe que agora i vale 1, e nós só iremos até o penúltimo índice (já que o último já se encontra ordenado). O algoritmo continua assim até que na última iteração, só os dois últimos números sejam comparados.

Terceira implementação

Para a terceira (e última) implementação, precisaremos de uma lista diferente para reproduzir a possível otimização:

[1, 3, 2, 6, 7, 8]

Observe que só existe uma troca a ser feita: 3 pelo 2. Sendo assim, faz sentido avaliar todas as possibilidades? Ou será que poderíamos fazer algo do tipo:

Trocou nenhum número de lugar nesta iteração? Não.
    Encerra o processo de ordenação

Ou seja, Nós paramos a ordenação assim que identificamos que nenhuma troca foi feita, já que, se nenhuma troca foi feita, a lista já se encontra ordenada!

Em termos de implementação, ficaria assim:

numbers = [7, 3, 6, 2, 0]
size = len(numbers)
for i in range(size -1):
    swapped = False 
    for j in range (size -i -1):
        if numbers[j] > numbers[j + 1]:
            numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
            swapped = True
    if not swapped:
        break

Conclusão

Mesmo não sendo um algoritmo “performático”, o Bubble Sort ainda serve como introdução ao tema. Além disso, vimos que mesmo uma solução considerada “não tão boa” pode ser repensada e melhorada.

EXTRA: Ainda não entendeu? veja meu Github ;)

https://github.com/rafaeltardivo/sort-algorithms

Deixei exemplos das três implementações por lá. Espero que ajude!

Até mais!