Bubble sort (ordenação por bolha)

Podcast

Desvendando o Bubble Sort0:00 / 9:10

0:001:00 restante

1x

A Ordenação por Bolha, ou Bubble Sort, é um dos algoritmos de ordenação mais fundamentais e intuitivos, perfeito para quem está começando a aprender sobre estruturas de dados e algoritmos. Seu nome peculiar vem da forma como os elementos maiores, como bolhas, "sobem" lentamente para o final da lista, enquanto os menores "afundam" para o início. Este guia completo explora o que é a Ordenação por Bolha, como ela funciona, suas vantagens e desvantagens, e sua aplicação.

O que é e Como Funciona a Ordenação por Bolha (Bubble Sort)?

A Ordenação por Bolha é um algoritmo que percorre repetidamente uma lista, comparando pares de elementos adjacentes e trocando-os de posição se estiverem na ordem errada. Este processo se repete até que nenhuma troca seja necessária em uma passagem completa, indicando que a lista está totalmente ordenada.

Princípio Básico da Ordenação por Bolha

O coração do algoritmo Bubble Sort é a comparação e a troca de elementos vizinhos. Ele garante que, a cada passagem pela lista, o maior elemento não ordenado "borbulhe" para sua posição final correta. A Ordenação por Bolha continua seu trabalho até que não haja mais elementos para trocar, significando que a lista alcançou a ordem desejada.

O processo detalhado inclui as seguintes etapas:

1. Comparação: Inicia-se pelo primeiro par de elementos (índice 0 e 1) da lista.
2. Troca: Se o primeiro elemento for maior que o segundo, eles são trocados. Caso contrário, permanecem como estão.
3. Avanço: O algoritmo move-se para o próximo par (índice 1 e 2) e repete a comparação e, se necessário, a troca.
4. Propagação: Este ciclo continua até o final da lista. Ao término da primeira passagem, o maior elemento estará garantidamente na última posição.
5. Repetição: As passagens são repetidas, mas em cada nova passagem, o número de comparações diminui, pois os últimos elementos já estão ordenados.
6. Condição de Parada: O algoritmo finaliza quando uma passagem completa ocorre sem que nenhuma troca seja realizada, confirmando que a lista está completamente ordenada.

Exemplo Prático de Ordenação por Bolha

Vamos visualizar o processo com a lista [5, 1, 4, 2, 8], ordenando-a em ordem crescente:

Lista inicial: [5, 1, 4, 2, 8]

Primeira Passagem:

• 5 e 1: 5 > 1, troca. Lista: [1, 5, 4, 2, 8]
• 5 e 4: 5 > 4, troca. Lista: [1, 4, 5, 2, 8]
• 5 e 2: 5 > 2, troca. Lista: [1, 4, 2, 5, 8]
• 5 e 8: 5 < 8, não troca. Lista: [1, 4, 2, 5, 8] Ao final desta passagem, o 8 está em sua posição correta.

Segunda Passagem: (considerando [1, 4, 2, 5])

• 1 e 4: 1 < 4, não troca. Lista: [1, 4, 2, 5, 8]
• 4 e 2: 4 > 2, troca. Lista: [1, 2, 4, 5, 8]
• 4 e 5: 4 < 5, não troca. Lista: [1, 2, 4, 5, 8] Agora, o 5 está no lugar certo.

Terceira Passagem: (considerando [1, 2, 4])

• 1 e 2: 1 < 2, não troca. Lista: [1, 2, 4, 5, 8]
• 2 e 4: 2 < 4, não troca. Lista: [1, 2, 4, 5, 8] O 4 está posicionado corretamente.

Quarta Passagem: (considerando [1, 2])

• 1 e 2: 1 < 2, não troca. Lista: [1, 2, 4, 5, 8]

Nenhuma troca ocorreu nesta última passagem, o que significa que a lista está completamente ordenada. Lista final ordenada: [1, 2, 4, 5, 8]

Complexidade e Otimização da Ordenação por Bolha

Entender a complexidade de tempo é crucial para avaliar a eficiência de qualquer algoritmo. Para a Ordenação por Bolha, esta medida pode variar significativamente dependendo do estado inicial da lista.

Complexidade de Tempo da Ordenação por Bolha

A complexidade de tempo descreve como o tempo de execução de um algoritmo escala com o tamanho da entrada (n). Para o Bubble Sort, temos:

• Pior Caso (O(n²)): Acontece quando a lista está em ordem inversa. O algoritmo realiza o número máximo de comparações e trocas, resultando em um crescimento quadrático do tempo de execução. Para n elementos, há aproximadamente n * (n-1) / 2 comparações.
• Caso Médio (O(n²)): Na maioria das situações, mesmo que a lista não esteja completamente invertida, a complexidade permanece quadrática. O número de comparações e trocas ainda é substancial.
• Melhor Caso (O(n)): Ocorre quando a lista já está ordenada. Com uma otimização, o algoritmo faz apenas uma passagem para verificar que não há trocas, resultando em complexidade linear. Sem otimização, ainda seria O(n²).

Devido à sua complexidade O(n²), a Ordenação por Bolha é geralmente ineficiente para grandes conjuntos de dados. Algoritmos como Merge Sort ou Quick Sort, com complexidade O(n log n), são preferíveis para essas situações.

Otimização Comum para Bubble Sort

A otimização mais empregada para a Ordenação por Bolha utiliza uma flag booleana. Essa flag indica se ocorreu alguma troca durante uma passagem. Se uma passagem terminar sem nenhuma troca, significa que a lista já está ordenada, permitindo que o algoritmo pare mais cedo. Esta melhoria transforma o melhor caso de O(n²) para O(n), mas não altera a complexidade nos casos médio ou pior.

Vantagens e Desvantagens do Algoritmo Bubble Sort

Como todo algoritmo, o Bubble Sort possui seus prós e contras, que devem ser considerados ao decidir quando (e se) usá-lo.

Vantagens:

• Simplicidade: É um dos algoritmos de ordenação mais fáceis de entender e implementar, ideal para fins didáticos.
• Estabilidade: Preserva a ordem relativa de elementos com valores iguais. Isso é importante em certas aplicações.
• Uso de memória: É um algoritmo in-place, requerendo uma quantidade mínima de espaço de memória adicional (O(1)).

Desvantagens:

• Ineficiência: Sua complexidade de tempo O(n²) o torna impraticável para grandes volumes de dados.
• Lento: Para listas extensas, o número excessivo de comparações e trocas resulta em um tempo de execução muito longo.

Pseudocódigo e Implementação em Python da Ordenação por Bolha

Para solidificar o entendimento, veja o pseudocódigo e uma implementação prática em Python.

Pseudocódigo com Otimização

função bubbleSort(lista):
 n = tamanho(lista)
 para i de 0 até n-1:
 troca_ocorreu = falso
 para j de 0 até n-1-i:
 se lista[j] > lista[j+1]:
 trocar(lista[j], lista[j+1])
 troca_ocorreu = verdadeiro
 se troca_ocorreu for falso:
 parar
 retornar lista

Implementação em Python

def bubble_sort(lista):
 n = len(lista)
 for i in range(n):
 # Flag para otimização: se nenhuma troca ocorrer nesta passagem, a lista está ordenada
 troca_ocorreu = False
 # A última i elementos já estão no lugar correto, então não precisamos compará-los
 for j in range(0, n - i - 1):
 # Compara elementos adjacentes
 if lista[j] > lista[j+1]:
 # Troca os elementos se estiverem na ordem errada
 lista[j], lista[j+1] = lista[j+1], lista[j]
 troca_ocorreu = True
 # Se nenhuma troca ocorreu em uma passagem, a lista está ordenada
 if not troca_ocorreu:
 break

 return lista

# Exemplos de uso da Ordenação por Bolha:
minha_lista = [5, 1, 4, 2, 8]
lista_ordenada = bubble_sort(minha_lista)
print(f"Lista original: [5, 1, 4, 2, 8]")
print(f"Lista ordenada: {lista_ordenada}") # Saída: [1, 2, 4, 5, 8]

minha_lista_quase_ordenada = [1, 2, 4, 5, 3]
lista_ordenada_quase = bubble_sort(minha_lista_quase_ordenada)
print(f"Lista quase ordenada: [1, 2, 4, 5, 3]")
print(f"Lista ordenada: {lista_ordenada_quase}") # Saída: [1, 2, 3, 4, 5]

minha_lista_ordenada = [1, 2, 3, 4, 5]
lista_ordenada_ja = bubble_sort(minha_lista_ordenada)
print(f"Lista já ordenada: [1, 2, 3, 4, 5]")
print(f"Lista ordenada: {lista_ordenada_ja}") # Saída: [1, 2, 3, 4, 5]

O que Observar em uma Simulação de Bubble Sort

Interagir com uma simulação da Ordenação por Bolha é uma excelente forma de aprofundar seu entendimento. Ao observar o algoritmo em ação, preste atenção aos seguintes pontos:

1. Movimento dos Elementos: Note como os elementos maiores realmente "borbulham" para o final, e os menores "afundam" para o início.
2. Número de Comparações: Observe como o número de comparações diminui em cada passagem, à medida que mais elementos são ordenados.
3. Frequência de Trocas: Perceba a relação entre o nível de desordem da lista e o número de trocas realizadas.
4. Efeito da Otimização: Experimente com listas já ou quase ordenadas para ver como a flag de otimização pode acelerar o processo no melhor caso.
5. Desempenho em Cenários Distintos: Teste com listas de tamanhos e níveis de desordem variados para visualizar a diferença entre os casos de melhor, pior e médio desempenho.

Perguntas Frequentes sobre Ordenação por Bolha

Qual a principal desvantagem da ordenação por bolha?

A principal desvantagem da Ordenação por Bolha é sua baixa eficiência para grandes conjuntos de dados, devido à sua complexidade de tempo quadrática (O(n²)) no pior e médio caso. Isso significa que o tempo de execução aumenta drasticamente com o tamanho da lista, tornando-o impraticável para aplicações com muitos elementos.

Em quais situações o Bubble Sort pode ser útil?

Embora não seja eficiente para grandes conjuntos de dados, o Bubble Sort é extremamente útil para fins didáticos, pois é um dos algoritmos de ordenação mais simples de entender e implementar. Também pode ser aceitável para listas muito pequenas onde a simplicidade supera a necessidade de velocidade extrema, ou quando a lista já está quase ordenada (beneficiando-se da otimização de O(n)).

Como a otimização impacta a complexidade do Bubble Sort?

A otimização mais comum do Bubble Sort, que usa uma flag para verificar se houve trocas em uma passagem, melhora a complexidade do melhor caso de O(n²) para O(n). Isso acontece quando a lista já está ordenada, pois o algoritmo pode parar após uma única passagem sem trocas. No entanto, essa otimização não altera a complexidade no pior ou caso médio, que permanece O(n²).

A ordenação por bolha é um algoritmo estável?

Sim, a Ordenação por Bolha é um algoritmo de ordenação estável. Isso significa que, se houver elementos com valores iguais na lista, a sua ordem relativa original é mantida após a ordenação. Por exemplo, se dois '5's aparecem na lista, o primeiro '5' original permanecerá antes do segundo '5' original na lista ordenada.

O que significa dizer que Bubble Sort é um algoritmo in-place?

Ser um algoritmo in-place significa que o Bubble Sort executa a ordenação diretamente na estrutura de dados de entrada, sem a necessidade de alocar uma quantidade significativa de espaço de memória adicional. Ele requer apenas um espaço constante (O(1)) para variáveis auxiliares durante as trocas de elementos, o que é uma vantagem em termos de uso de memória.