Ordenação por Bolha

5.1 Definição de Ordenação por Bolha

Ordenação por Bolha (Bubble Sort) é um algoritmo simples de ordenação que passa repetidamente por uma lista, comparando elementos adjacentes e trocando-os de lugar se estiverem na ordem errada. Esse processo continua até que a lista esteja completamente ordenada.

Princípio de Funcionamento:

1. O algoritmo percorre a lista e compara cada par de elementos adjacentes.
2. Se os elementos estiverem na ordem errada (o primeiro for maior que o segundo para ordenação crescente) — eles são trocados de lugar.
3. Esse processo se repete para todos os pares de elementos na lista.
4. Após cada passagem completa, o maior elemento "sobe" para o seu lugar (como uma bolha na superfície da água), e por isso ele não participa mais das próximas passagens.
5. O processo se repete até que a lista esteja ordenada.

Complexidade de tempo e espaço da ordenação por bolha

Complexidade de Tempo:

• No pior caso: O(n^2) — ocorre quando os elementos estão inicialmente na ordem reversa.
• No caso médio: O(n^2) — ocorre para uma disposição aleatória dos elementos.
• No melhor caso: O(n) — ocorre quando os elementos já estão ordenados (o algoritmo pode ser otimizado para esse caso, adicionando uma verificação se houve troca de elementos durante a passagem).

Complexidade de Espaço:

O(1) — já que o algoritmo usa uma quantidade constante de memória adicional (apenas algumas variáveis para armazenar valores temporários).

5.2 Implementação do Algoritmo

O algoritmo de "ordenação por bolha" é o mais simples e primitivo algoritmo de ordenação de uma lista/array de elementos. Ele simplesmente compara pares de elementos e troca-os de lugar, se necessário.

Versão 1:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1):
        if array[j] > array[j + 1]:
            array[j], array[j + 1] = array[j + 1], array[j]  # Troca de elementos

print("Array ordenado:", array)
# Saída: Array ordenado: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

O loop interno (destacado em verde) compara um elemento com seu vizinho à direita. E, se necessário, troca-os de lugar.

Versão 2:

Podemos imediatamente adicionar uma otimização ao nosso algoritmo: após a primeira passagem o elemento máximo estará no extremo direito, então ele já pode ser desconsiderado no próximo ciclo.

Após a segunda iteração, já haverá 2 elementos máximos à direita, então o loop interno pode ir até n - 1 - i, em vez de n - 1, onde i é o número de iterações passadas do loop externo.

A nova versão vai ficar assim:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1 - i):
        if array[j] > array[j + 1]:
            array[j], array[j + 1] = array[j + 1], array[j]  # Troca de elementos

print("Array ordenado:", array)
# Saída: Array ordenado: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

Versão 3:

Além disso, o array já pode estar quase ordenado. Portanto, podemos adicionar uma otimização assim: se o loop interno percorreu todos os elementos, mas não fez nenhuma troca, então a ordenação está concluída.

Nesta versão, é utilizada a variável swapped, que monitora se ocorreu alguma troca de elementos durante a última passagem. Se, após passar pelo array, nenhuma troca ocorreu, isso significa que o array já está ordenado, e prosseguir com mais iterações se torna inútil — elas não vão melhorar a ordenação. Assim, a variável swapped permite acelerar significativamente o funcionamento do algoritmo em arrays quase ordenados, encerrando sua execução antecipadamente.

Implementação da ordenação por bolha em Python:

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        swapped = False  # Otimização: verificação se ocorreu troca
        for j in range(0, n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]  # Troca de elementos
                swapped = True
        if not swapped:
            break  # Se não houve trocas, o array já está ordenado
    return array

# Exemplo de uso:
array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = bubble_sort(array)
print("Array ordenado:", sorted_array)
# Saída: Array ordenado: [11, 12, 22, 25, 34, 64, 90]