Ordenação Bolha/bubble

  • Conceito
  • Gif
  • Código
  • Passo a passo
  • Vamos dançar!
  • Análise de complexidade [no futuro]
  • outros algoritmos

Conceito

O algoritmo de ordenação bolha (bubble sort) é um dos algoritmos de ordenação mais simples de ser desenvolvido e compreendido.
Ele compara pares adjacentes de valores e “flutua” o maior valor (ou menor se for descrescente) para a posição correta (última).
O laço interno garante que todos os valores serão comparados e o maior valor da vez será selecionado. Enquanto o laço externo garante que o laço interno se repetirá e selecionará o valor (primeiro maior, segundo maior, terceiro maior, etc…) conforme quantidade de vezes necessária.
Obs: Após ser colocado na posição correta, o valor não precisa mais ser comparado. Mas mesmo que as comparações sigam de forma redundante nas próximas “passadas” pelo laço interno, o algoritmo conseguirá ordenar o vetor da mesma forma, a diferença é que executará passos desnecessários.

Vantagens

– Algoritmo estável e simples.

Indicações

– Valores pré-ordenados.

– Pequena quantidade de valores.

Observe no GIF a seguir que os elementos maiores vão aos poucos “subindo” para o final do vetor (que poderia estar posicionado na vertical), como se fossem bolhas.

Gif

Código

def bubble_sort(valores):
   n = len(valores)-1
   for i in range(n,0,-1):
      for j in range(n):
         if valores[j] > valores[j + 1]:
            auxiliar = valores[j]
            valores[j] = valores[j + 1]
            valores[j + 1] = auxiliar
   return valores

Disponível em: https://github.com/wschratzenstaller/ordenacao/blob/954c93d18c406555dfd1f9af02d2e9688f1fe54c/bubble_sort.py

Passo a passo

0

1

2

3

4

5

def bubble_sort(valores):
-> n = len(valores)-1
   for i in range(n,0,-1):
      for j in range(n):
         if valores[j] > valores[j + 1]:
            auxiliar = valores[j]
            valores[j] = valores[j + 1]
            valores[j + 1] = auxiliar
   return valores

n = 5

def bubble_sort(valores):
   n = len(valores)-1
-> for i in range(n,0,-1):
      for j in range(n):
         if valores[j] > valores[j + 1]:
            auxiliar = valores[j]
            valores[j] = valores[j + 1]
            valores[j + 1] = auxiliar
   return valores

para cada posição no range de n(5 – cinco) a 0(zero), sempre descontando um a cada passo, faça:
n = 5
i = 5

def bubble_sort(valores):
   n = len(valores)-1
   for i in range(n,0,-1):
->    for j in range(n):
         if valores[j] > valores[j + 1]:
            auxiliar = valores[j]
            valores[j] = valores[j + 1]
            valores[j + 1] = auxiliar
   return valores

Cada vez que interagir no laço externo.
Para cada posição no range de n, faça:
n = 5
i = 5
j = 0

def bubble_sort(valores):
   n = len(valores)-1
   for i in range(n,0,-1):
      for j in range(n):
->       if valores[j] > valores[j + 1]:
            auxiliar = valores[j]
            valores[j] = valores[j + 1]
            valores[j + 1] = auxiliar
   return valores

n = 5
i = 5
j = 0

Verifica se valores[0] > = valores[1] // 9 > = 4 ? True

0

1

2

3

4

5

def bubble_sort(valores):
   n = len(valores)-1
   for i in range(n,0,-1):
      for j in range(n):
         if valores[j] > valores[j + 1]:
->          auxiliar = valores[j]
            valores[j] = valores[j + 1]
            valores[j + 1] = auxiliar
   return valores

n = 5
i = 5
j = 0
auxiliar = valores[0] // 9

0

1

2

3

4

5

def bubble_sort(valores):
   n = len(valores)-1
   for i in range(n,0,-1):
      for j in range(n):
         if valores[j] > valores[j + 1]:
            auxiliar = valores[j]
->          valores[j] = valores[j + 1]
            valores[j + 1] = auxiliar
   return valores

n = 5
i = 5
j = 0
auxiliar = 9
valores[0] = valores [1] // valores[0] = 4

0

1

2

3

4

5

def bubble_sort(valores):
   n = len(valores)-1
   for i in range(n,0,-1):
      for j in range(n):
         if valores[j] > valores[j + 1]:
            auxiliar = valores[j]
            valores[j] = valores[j + 1]
->          valores[j + 1] = auxiliar
   return valores

n = 5
i = 5
j = 0
auxiliar = 9
valores[0] = 4
valores[1] = auxiliar // valores[1] = 9

0

1

2

3

4

5

def bubble_sort(valores):
   n = len(valores)-1
   for i in range(n,0,-1):
->    for j in range(n):
         if valores[j] > valores[j + 1]:
            auxiliar = valores[j]
            valores[j] = valores[j + 1]
            valores[j + 1] = auxiliar
   return valores

n = 5
i = 5
j = 1
auxiliar = 9
valores[0] = 4
valores[1] = 9

def bubble_sort(valores):
   n = len(valores)-1
   for i in range(n,0,-1):
      for j in range(n):
->       if valores[j] > valores[j + 1]:
            auxiliar = valores[j]
            valores[j] = valores[j + 1]
            valores[j + 1] = auxiliar
   return valores

n = 5
i = 5
j = 1
auxiliar = 9
valores[0] = 4
valores[1] = 9

Verifica se valores[1] > = valores[2] // 9 > = 6 ? True

0

1

2

3

4

5

def bubble_sort(valores):
   n = len(valores)-1
   for i in range(n,0,-1):
      for j in range(n):
         if valores[j] > valores[j + 1]:
->          auxiliar = valores[j]
            valores[j] = valores[j + 1]
            valores[j + 1] = auxiliar
   return valores

n = 5
i = 5
j = 1
auxiliar = valores[1] // 9

0

1

2

3

4

5

def bubble_sort(valores):
   n = len(valores)-1
   for i in range(n,0,-1):
      for j in range(n):
         if valores[j] > valores[j + 1]:
            auxiliar = valores[j]
->          valores[j] = valores[j + 1]
            valores[j + 1] = auxiliar
   return valores

n = 5
i = 5
j = 1
auxiliar = 9
valores[1] = valores [2] // valores[1] = 6

0

1

2

3

4

5

def bubble_sort(valores):
   n = len(valores)-1
   for i in range(n,0,-1):
      for j in range(n):
         if valores[j] > valores[j + 1]:
            auxiliar = valores[j]
            valores[j] = valores[j + 1]
->          valores[j + 1] = auxiliar
   return valores

n = 5
i = 5
j = 1
auxiliar = 9
valores[1] = 6
valores[2] = auxiliar // valores[2] = 9

0

1

2

3

4

5

def bubble_sort(valores):
   n = len(valores)-1
   for i in range(n,0,-1):
->    for j in range(n):
         if valores[j] > valores[j + 1]:
            auxiliar = valores[j]
            valores[j] = valores[j + 1]
            valores[j + 1] = auxiliar
   return valores

n = 5
i = 5
j = 2
auxiliar = 9
valores[0] = 4
valores[1] = 9

def bubble_sort(valores):
   n = len(valores)-1
   for i in range(n,0,-1):
      for j in range(n):
->       if valores[j] > valores[j + 1]:
            auxiliar = valores[j]
            valores[j] = valores[j + 1]
            valores[j + 1] = auxiliar
   return valores

n = 5
i = 5
j = 2
auxiliar = 9
valores[0] = 4
valores[1] = 9
Verifica se valores[2] > = valores[3] // 9 > = 6 ? True

def bubble_sort(valores):
   n = len(valores)-1
   for i in range(n,0,-1):
      for j in range(n):
         if valores[j] > valores[j + 1]:
->          auxiliar = valores[j]
            valores[j] = valores[j + 1]
            valores[j + 1] = auxiliar
   return valores

n = 5
i = 5
j = 2
auxiliar = valores[2] // 9

0

1

2

3

4

5

def bubble_sort(valores):
   n = len(valores)-1
   for i in range(n,0,-1):
      for j in range(n):
         if valores[j] > valores[j + 1]:
            auxiliar = valores[j]
->          valores[j] = valores[j + 1]
            valores[j + 1] = auxiliar
   return valores

n = 5
i = 5
j = 2
auxiliar = 9
valores[0] = 4
valores[1] = 9
Verifica se valores[2] > = valores[3] // 9 > = 6 ? True

0

1

2

3

4

5

continua…

Vamos dançar!

Leave a Comment