Algoritmos de Ordenação: Bubble Sort

Os algoritmos de ordenação servem para colocar um conjunto de itens (geralmente numericamente ou lexicalmente) em uma ordem. A entrada é uma lista de itens e o retorno do algoritmo é a lista, de forma que deve seguir a ordenação estabelecida.

Vale lembrar também que a aplicação de algoritmos de ordenação são extremamente importantes para operações que incluem outros tipos de algoritmo tais como: busca binária e união de itens. Em outras palavras — existem algoritmos que possuem a premissa de que a lista esteja ordenada para assim aplicá-los.

Neste primeiro artigo será explicado sobre o bubble sort. A ideia daqui para frente é em cada artigo descrever as ideias, vantagens, desvantagens e um exemplo em código implementando cada tipo de algoritmo.

Vamos ao Bubble Sort

Este algoritmo é um dos mais simples levando em conta a implementação, apesar de não ter um bom desempenho se comparado a outros tipos de algoritmos de ordenação

A ideia é sempre iterar toda a lista de itens quantas vezes forem necessário até que os itens estejam na ordem correta.

Durante a iteração, o algoritmo deve comparar e ordenar pares de valores: O item que se está iterando e o seu vizinho à direita (não se preocupe se não entender, pois o processo e implementação do mesmo será detalhado a seguir).

Seu tempo de execução depende da ordem que a lista se encontra.

O melhor caso para o bubble sort é enviar uma lista com itens já ordenados na entrada, pois o algoritmo percorrerá a lista apenas uma vez, dado que após a primeira iteração os itens estarão já ordenados. Logo, seu tempo de execução no melhor caso é percorrer toda a lista uma vez, o que chamaremos de N.

Exemplificando: ao executar o bubble sort em uma lista já ordenada com cinco itens (Exemplo: 1, 2, 3, 4, 5), o algoritmo precisa irá iterar do primeiro ao quinto elemento, totalizando em cinco operações.

O pior caso é quando os menores elementos se encontram ao final da lista (na verdade, o pior é caso é uma lista em ordem decrescente). Serão necessárias muitas iterações na lista para “trazer” esses números menores para suas posições correspondentes na ordenação.

Exemplificando: no caso de ordenar uma lista decrescente com os valores [5, 4, 3, 2, 1] (de novo, não se preocupe, pois o funcionamento do algoritmo será explicado a seguir), teríamos vinte processos (ou mais precisamente, a diferença entre o número de elementos na lista ao quadrado e o tamanho da lista -> n² — n, neste caso 25–5 = 20):

Processo 1: [4, 5,3, 2, 1]

Processo 2: [4, 3, 5, 2, 1]

Processo 3: [4, 3, 2, 5, 1]

Processo 4: [4, 3, 2, 1, 5]

Processo 5: [3, 4, 2, 1, 5]

Processo 6: [3, 2, 4, 1, 5]

Processo 7: [3, 2, 1, 4, 5]

Processo 8: [3, 2, 1, 4, 5]

Processo 9: [2, 3, 1, 4, 5]

Processo 10: [2, 1, 3, 4, 5]

Processo 11: [2, 1, 3, 4, 5]

Processo 12: [2, 1, 3, 4, 5]

Processo 13: [1, 2, 3, 4, 5]

Processo 14: [1, 2, 3, 4, 5]

Processo 15: [1, 2, 3, 4, 5]

Processo 16: [1, 2, 3, 4, 5]

Processo 17: [1, 2, 3, 4, 5]

Processo 18: [1, 2, 3, 4, 5]

Processo 19: [1, 2, 3, 4, 5]

Processo 20: [1, 2, 3, 4, 5]

Funcionamento do algoritmo

Para o exemplo, será utilizada uma lista de itens com seis elementos ([5, 3, 1, 2, 4, 0]).

Lista Desordenada

Serão comparados respectivamente os valores do primeiro e o segundo item da lista.

Primeira iteração: O primeiro item(5) é maior que o segundo(3)?

Neste caso, sim: o primeiro item é maior que o segundo. Então para manter a ordem, devemos trocá-los de posição!

. Precisamos também dizer ao algoritmo que houveram alterações e portanto, mesmo que os itens fiquem ordenados nesta primeira iteração, a lista deverá ser percorrida novamente utilizando as mesmas regras de ordenação posteriormente.

Primeira iteração: Os valores do primeiro e segundo elementos da lista devem trocar de posição

Agora, deve-se comparar o segundo item da lista com o terceiro, seguindo a mesma lógica acima:

Primeira iteração: O valor do segundo item(5) é maior que o terceiro(1)?

Novamente, sim! Notificamos o algoritmo da mesma forma que houveram itens que não estavam ordenados na iteração. Logo, devemos trocar seus valores de posição

Primeira iteração: Os valores do segundo e terceiro elementos da lista devem trocar de posição

Seguimos com a mesma lógica. Para não ficar repetitivo, será apenas demonstrar o que ocorre com a lista até o final do processo explicado acima.

Primeira iteração: O valor do terceiro item(5) é maior que o quarto(2)?

Primeira iteração: Os valores do terceiro e quarto elementos da lista devem trocar de posição

Primeira iteração: O valor do quarto item(5) é maior que o quinto(4)?

Primeira iteração: Os valores do quarto e quinto elementos da lista devem trocar de posição

Primeira iteração: O valor do quinto item(5) é maior que o sexto(0)?

Primeira iteração: Os valores do quarto e quinto elementos da lista devem trocar de posição

Ao final da primeira iteração, a lista estará então dessa forma:

Itens após a primeira iteração

Como o algoritmo foi “notificado” para continuar iterando(novamente — isso sempre ocorre quando houver troca de valores na iteração atual), utilizaremos o mesmo processo descrito anteriormente.

Para não ficar repetitivo,n ão será explicado tão detalhadamente como na primeira iteração, pois a ideia é exatamente igual: se o valor do item à esquerda for maior que o seu vizinho à direita, os valores devem ser trocados de posição e o algoritmo notificado que ao término desta iteração, o processo deve ser realizado novamente.

Segunda iteração: O valor do primeiro item(3) é maior que o segundo(1)? (Sim!)

Segunda iteração: Os valores do primeiro e segundo elementos da lista devem trocar de posição

Segunda iteração: O valor do segundo item(3) é maior que o segundo(2)? (Sim!)

Segunda iteração: Os valores do segundo e terceiro elementos da lista devem trocar de posição

Segunda iteração: O valor do terceiro item(3) é maior que o quarto(4)? (Não, então os valores não precisam ser alterados!)

Segunda iteração: O valor do quarto item(4) é maior que o quinto(2)? (Sim!)

Segunda iteração: Os valores do quarto e quinto elementos da lista devem trocar de posição

Segunda iteração: O valor do quinto item(4) é maior que o sexto(5)? (Não, então os valores não precisam ser alterados!)

Ao final da primeira iteração, a lista estará então dessa forma:

Itens após a primeira iteração

Como o algoritmo foi “notificado” para continuar (pois houveram troca de valores na primeira iteração), utilizaremos o mesmo processo descrito anteriormente.

Terceira iteração: O valor do primeiro item(1) é maior que o segundo(2)? (Não, então os valores não precisam ser alterados!)

Terceira iteração: O valor do segundo item(2) é maior que o terceiro(4)? (Não, então os valores não precisam ser alterados!)

Terceira iteração: O valor do terceiro item(3) é maior que o quarto(0)? (Sim!)

Terceira iteração: Os valores do terceiro e quarto elementos da lista devem trocar de posição

Terceira iteração: O valor do quarto item(3) é maior que o quinto(4)? (Não, então os valores não precisam ser alterados!)

Terceira iteração: O valor do quinto item(4) é maior que o sexto(5)? (Não, então os valores não precisam ser alterados!)

Ao final da terceira iteração, a lista estará então dessa forma:

Como o algoritmo foi “notificado” para continuar (pois houveram troca de valores na terceira iteração), utilizaremos o mesmo processo descrito anteriormente.

Quarta iteração: O valor do primeiro item(1) é maior que o segundo(2)? (Não, então os valores não precisam ser alterados!)

Quarta iteração: O valor do segundo item(2) é maior que o terceiro(0)? (Sim!)

Quarta iteração: Os valores do segundo e terceiro elementos da lista devem trocar de posição

Quarta iteração: O valor do terceiro item(2) é maior que o quarto (3)? (Não, então os valores não precisam ser alterados!)

Quarta iteração: O valor do quarto item(3) é maior que o quinto(4)? (Não, então os valores não precisam ser alterados!)

Quarta iteração: O valor do quinto item(4) é maior que o sexto(5)? (Não, então os valores não precisam ser alterados!)

Ao final da quarta iteração, a lista estará então dessa forma:

Itens após a quarta iteração

Como o algoritmo foi “notificado” para continuar (pois houveram troca de valores na quarta iteração), utilizaremos o mesmo processo descrito anteriormente.

Quinta iteração: O valor do primeiro item(1) é maior que o segundo(0)? (Sim!)

Quinta iteração: Os valores do primeiro e segundo elementos da lista devem trocar de posição e o algoritmo deve seguir outra iteração ao terminar esta

Quinta iteração: O valor do segundo item(1) é maior que o terceiro (2)? (Não, então os valores não precisam ser alterados!)

Quinta iteração: O valor do terceiro item(2) é maior que o quarto (3)? (Não, então os valores não precisam ser alterados!)

Quinta iteração: O valor do quarto item(3) é maior que o quinto (4)? (Não, então os valores não precisam ser alterados!)

Quinta iteração: O valor do quinto item(4) é maior que o sexto (5)? (Não, então os valores não precisam ser alterados!)

Apesar da lista finalmente estar ordenada, houveram troca de valores entre posições e portanto, uma iteração adicional será necessária

Sexta iteração: O valor do primeiro item(0) é maior que o segundo (1)? (Não, então os valores não precisam ser alterados!)

Sexta iteração: O valor do segundo item(1) é maior que o segundo (2)? (Não, então os valores não precisam ser alterados!)

Sexta iteração: O valor do terceiro item(2) é maior que o quarto (3)? (Não, então os valores não precisam ser alterados!)

Sexta iteração: O valor do quarto item(3) é maior que o quinto (4)? (Não, então os valores não precisam ser alterados!)

Sexta iteração: O valor do quinto item(4) é maior que o sexto (5)? (Não, então os valores não precisam ser alterados!)

Note que desta vez, não houve quaisquer alterações ao percorrer a lista. O que isso significa?

A lista está finalmente ordenada! O algoritmo não precisa mais percorrer!

Lista ordenada após o algoritmo bubble sort

Implementação

Abaixo segue uma implementação em Python:

def bubble_sort(items):
 had_swap = True #Inicializa como True para passar ao menos uma vez no laço
while had_swap: #Enquanto na iteração houver troca de valores (swap)
  had_swap = False #Configura como falso inicialmente
  for i in range(len(items) - 1): 
   if items[i] > items[i + 1]: #Caso os elementos sendo comparados estejam desordenados
    swap(items, i) #Realiza a troca de valores nas posições
    had_swap = True #Como houveram troca de valores, deve-se continuar a iteração
return items
def swap(items, index):
 items[index], items[index + 1] = items[index + 1], items[index]
if __name__ == '__main__':
 print(bubble_sort([5, 4, 3, 2, 1]))

E com isso, encerramos nosso primeiro algoritmo de ordenação \o/!