Algoritmos e Estruturas de Dados

Bubble Sort (ordenação por bolha)

Dado um array de n inteiros, nosso objetivo é classificá-los em ordem crescente. O Bubble Sort (ordenação por bolha) é um dos algoritmos mais populares e simples para resolver esse problema (lembre-se de que ele não é rápido – a maior parte dos algoritmos utilizados em produção emprega outras técnicas para ordenar listas de números).
Video preview
Com o algoritmo de Bubble Sort, fazemos várias passagens pelo array e trocamos quaisquer elementos vizinhos que não estejam em ordem. Assim, se , trocamos os dois para garantir que o array fique em ordem crescente.
De modo mais específico, pegamos o array inicial a (imagine que a seja [4, 1, -1, 0, 2, 8]) e olhamos para os dois primeiros elementos. Se não estiverem em ordem, trocamos seus lugares (neste caso, [1, 4, -1, 0, 2, 8]). Em seguida, passamos para o par seguinte. Se também estiverem fora de ordem, trocamos seus lugares (agora [1, -1, 4, 0, 2, 8]). Repetimos esse processo até chegar ao final do array (no nosso exemplo: [1, -1, 4, 0, 2, 8] → [1, -1, 0, 4, 2, 8] → [1, -1, 0, 2, 4, 8] → nenhuma mudança → concluído).
Depois disso, o loop recomeça desde o início. Observamos o primeiro par do array e comparamos. Se não estiver em ordem, trocamos. Então passamos para o par seguinte, depois para o outro, e assim por diante, até chegar ao fim do array. Em nosso exemplo, isso resulta em: [1, -1, 0, 2, 4, 8] → [-1, 1, 0, 2, 4, 8] → [-1, 0, 1, 2, 4, 8] → nenhuma mudança.
Esse processo se repete até que todo o array esteja completamente ordenado:
a = [...]
while True:                                 # executa até que o array esteja ordenado
    is_sorted = True                        # se algo mudar, definimos isto como False
    for i in range(len(a) - 1):             # percorre de 0 ... n-2
        if a[i] > a[i + 1]:                 # se algo não estiver em ordem
            is_sorted = False               # => o array não estava ordenado
            a[i], a[i + 1] = a[i + 1], a[i] # troca a[i] e a[i + 1]
    
    if is_sorted:                           # para o processo se a estiver ordenado
        break
print(a)
Podemos fazer uma otimização para evitar etapas desnecessárias:
  • Sabemos que depois de cada iteração, os elementos maiores vão se acumulando no final do array. Então, após k passagens, os k maiores elementos do array já estarão ordenados no final. Por isso, podemos evitar passar por eles no loop interno:
a = [...]
for u in range(len(a) - 1, 0, -1):          # u = limite superior para o loop interno
    is_sorted = True                        # se algo mudar, definimos isto como False
    for i in range(u):                      # percorre de 0 ... u-1
        if a[i] > a[i + 1]:                 # se algo não estiver em ordem
            is_sorted = False               # => o array não estava ordenado
            a[i], a[i + 1] = a[i + 1], a[i] # troca a[i] e a[i + 1]
    
    if is_sorted:                           # para o processo se a estiver ordenado
        break
print(a)
O pior cenário para o Bubble Sort é aquele em que os números estão em ordem exatamente inversa (descendente) em vez de ascendente. Nesse caso, o algoritmo executa operações, o que é muito se comparado a algoritmos mais rápidos, que veremos adiante no curso.
Vamos simular o algoritmo em alguns arrays:
[4, 1, -1, 0, 2, 8]
  1. u = 5
    1. i = 0 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]
    2. i = 1 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8]
    3. i = 2 ⇒ swap ⇒ [1, -1, 0, 4, 2, 8]
    4. i = 3 ⇒ swap ⇒ [1, -1, 0, 2, 4, 8]
    5. i = 4 ⇒ do nothing
  1. i = 0 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]
    1. i = 0 ⇒ swap ⇒ [-1, 1, 0, 2, 4, 8]
    2. i = 1 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
    3. i = 2 ⇒ do nothing
    4. i = 3 ⇒ do nothing
  1. i = 1 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8]
    1. i = 0 ⇒ do nothing
    2. i = 1 ⇒ do nothing
    3. i = 2 ⇒ do nothing
    4. is_sorted is True ⇒ break
  1. i = 2 ⇒ swap ⇒ [1, -1, 0, 4, 2, 8]
[10, 5, 1, -1, -2, -7]
  1. u = 5
    1. i = 0 ⇒ swap ⇒ [5, 10, 1, -1, -2, -7]
    2. i = 1 ⇒ swap ⇒ [5, 1, 10, -1, -2, -7]
    3. i = 2 ⇒ swap ⇒ [5, 1, -1, 10, -2, -7]
    4. i = 3 ⇒ swap ⇒ [5, 1, -1, -2, 10, -7]
    5. i = 4 ⇒ swap ⇒ [5, 1, -1, -2, -7, 10]
  1. i = 0 ⇒ swap ⇒ [5, 10, 1, -1, -2, -7]
    1. i = 0 ⇒ swap ⇒ [1, 5, -1, -2, -7, 10]
    2. i = 1 ⇒ swap ⇒ [1, -1, 5, -2, -7, 10]
    3. i = 2 ⇒ swap ⇒ [1, -1, -2, 5, -7, 10]
    4. i = 3 ⇒ swap ⇒ [1, -1, -2, -7, 5, 10]
  1. i = 1 ⇒ swap ⇒ [5, 1, 10, -1, -2, -7]
    1. i = 0 ⇒ swap ⇒ [-1, 1, -2, -7, 5, 10]
    2. i = 1 ⇒ swap ⇒ [-1, -2, 1, -7, 5, 10]
    3. i = 2 ⇒ swap ⇒ [-1, -2, -7, 1, 5, 10]
  1. i = 2 ⇒ swap ⇒ [5, 1, -1, 10, -2, -7]
    1. i = 0 ⇒ swap ⇒ [-2, -1, -7, 1, 5, 10]
    2. i = 1 ⇒ swap ⇒ [-2, -7, -1, 1, 5, 10]
  1. i = 3 ⇒ swap ⇒ [5, 1, -1, -2, 10, -7]
    1. i = 0 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 4 ⇒ swap ⇒ [5, 1, -1, -2, -7, 10]
[1, 2, 3, 4, 5]
  1. u = 5
    1. i = 0 ⇒ do nothing
    2. i = 1 ⇒ do nothing
    3. i = 2 ⇒ do nothing
    4. i = 3 ⇒ do nothing
    5. i = 4 ⇒ do nothing
    6. is_sorted is True ⇒ break
  1. i = 0 ⇒ do nothing
Extracurricular (vídeo interessante)
Há um ótimo vídeo no YouTube feito por Lines That Connect que explora mais a fundo o Bubble Sort Algorithm e explica a intuição por trás da curva que se forma quando o algoritmo é executado.
Video preview
Vídeo de Lines That Connect – The Bubble Sort Curve.

Challenge

n pessoas estão participando de uma competição. Pede-se que sejam organizadas em ordem crescente de altura. A cada passo, é permitido solicitar que dois participantes vizinhos troquem de lugar. O tempo é curto, portanto é do seu interesse fazer isso de forma eficiente.
Você decidiu escrever um programa que imprima os índices dos participantes que devem trocar de posição. A indexação começa em 0.

Entrada

A primeira linha da entrada contém um único inteiro n (1 ≤ n ≤ 1000).
A linha seguinte contém n inteiros separados por espaço ( ≤ ≤ ), que são as alturas dos participantes.

Saída

O programa deve imprimir os pares de índices dos participantes que precisam trocar de posição. Cada par deve ser impresso em uma linha separada. Em caso de múltiplas respostas ótimas, qualquer uma delas é aceitável.

Exemplos

Entrada
Saída
5 1 4 8 2 -1
2 3 3 4 1 2 2 3 1 2 0 1

Explicação

  1. 2 ↔ 3 ⇒ 1 4 2 8 -1
  1. 3 ↔ 4 ⇒ 1 4 2 -1 8
  1. 1 ↔ 2 ⇒ 1 2 4 -1 8
  1. 2 ↔ 3 ⇒ 1 2 -1 4 8
  1. 1 ↔ 2 ⇒ 1 -1 2 4 8
  1. 0 ↔ 1 ⇒ -1 1 2 4 8
 

Constraints

Time limit: 1.98 seconds

Memory limit: 512 MB

Output limit: 10 MB

To check your solution you need to sign in
Sign in to continue