Bubble Sort é um algoritmo de classificação simples que percorre repetidamente a lista, compara elementos adjacentes e os troca se estiverem na ordem errada. É denominado 'Bubble Sort' porque os elementos menores 'bolham' no topo da lista. Embora não seja o algoritmo de classificação mais eficiente, é fácil de entender e implementar, o que o torna um bom ponto de partida para aprender sobre algoritmos de classificação. Neste artigo, iremos nos aprofundar no conceito de Bubble Sort, fornecer uma implementação Python com saída e discutir a complexidade de tempo do algoritmo.
Compreendendo a classificação por bolha
A ideia básica por trás do Bubble Sort é percorrer a lista várias vezes, comparando elementos adjacentes e trocando-os se estiverem fora de ordem. O processo continua até que não sejam necessárias mais trocas, indicando que a lista está agora ordenada. O algoritmo recebe esse nome devido à forma como os elementos menores se movem gradualmente para o topo da lista, como bolhas subindo à superfície.
Vamos detalhar as etapas do algoritmo Bubble Sort:
- Iterar pela lista: comece do início da lista e compare cada par de elementos adjacentes.
- Compare e troque: se os elementos estiverem na ordem errada, troque-os. Isso garante que o elemento maior 'borbulhe' e o menor desça.
- Continue iterando: Repita o processo para cada par de elementos adjacentes até chegar ao final da lista.
- Repita até classificar: Continue iterando pela lista até que não sejam necessárias mais trocas. Neste ponto, a lista está ordenada.
Embora o Bubble Sort seja simples de entender, não é o algoritmo de classificação mais eficiente, especialmente para grandes conjuntos de dados. Sua complexidade de tempo é O(n^2) no pior caso, onde 'n' é o número de elementos na lista. Essa complexidade de tempo quadrática o torna menos adequado para grandes conjuntos de dados quando comparado a algoritmos de classificação mais avançados.
Implementação Python de classificação por bolha
Agora, vamos implementar o Bubble Sort em Python e observar seu comportamento com uma lista de exemplos:
def bubble_sort(arr): n = len(arr) # Traverse through all array elements for i in range(n): # Last i elements are already sorted, so we don't need to check them for j in range(0, n-i-1): # Swap if the element found is greater than the next element if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # Example usage if __name__ == '__main__': # Sample list to be sorted sample_list = [64, 34, 25, 12, 22, 11, 90] # Display the original list print('Original List:', sample_list) # Apply Bubble Sort bubble_sort(sample_list) # Display the sorted list print('Sorted List:', sample_list)
Nesta implementação, a função bubble_sort pega uma lista (arr) como parâmetro e a classifica no local. O loop aninhado compara elementos adjacentes e os troca se estiverem na ordem errada. O loop externo garante que o processo seja repetido até que toda a lista seja classificada.
Resultado e explicação
Vamos executar o código Python fornecido com a lista de exemplos e observar o resultado:
Original List: [64, 34, 25, 12, 22, 11, 90] Sorted List: [11, 12, 22, 25, 34, 64, 90]
Aqui, a lista original [64, 34, 25, 12, 22, 11, 90] é classificada com sucesso usando o algoritmo Bubble Sort, resultando na lista classificada [11, 12, 22, 25, 34, 64, 90].
O algoritmo percorre a lista várias vezes, comparando e trocando elementos até que toda a lista seja classificada. Em cada passagem, o maior elemento não classificado 'borbulha' para sua posição correta. Este processo continua até que não sejam necessárias mais trocas, indicando que a lista está totalmente ordenada.
Embora o Bubble Sort classifique a lista com êxito, é importante observar que sua complexidade de tempo o torna menos eficiente para grandes conjuntos de dados em comparação com outros algoritmos de classificação, como Merge Sort ou Quick Sort.
Complexidade temporal da classificação por bolha
Compreender a complexidade temporal de um algoritmo é crucial para avaliar sua eficiência, especialmente quando se trata de grandes conjuntos de dados. A complexidade de tempo do Bubble Sort é O(n^2) no pior caso, onde 'n' é o número de elementos na lista.
Vamos analisar a análise de complexidade de tempo:
- O loop externo é executado por 'n' iterações, onde 'n' é o número de elementos na lista.
- O loop interno também é executado por 'n' iterações no pior caso. No entanto, à medida que o algoritmo avança, o número de iterações no loop interno diminui, à medida que o maior elemento não classificado é colocado na posição correta em cada passagem.
- Na pior das hipóteses, o número de comparações e trocas é proporcional ao quadrado do número de elementos na lista, resultando na complexidade de tempo O(n^2). Isso torna o Bubble Sort ineficiente para grandes conjuntos de dados, e algoritmos de classificação mais avançados com melhores complexidades de tempo são frequentemente preferidos em aplicações do mundo real.
Conclusão
Neste artigo, exploramos o conceito de Bubble Sort, um algoritmo de classificação simples que compara e troca repetidamente elementos adjacentes até que toda a lista seja classificada. Fornecemos uma implementação Python do Bubble Sort, executamos com uma lista de exemplos e analisamos o resultado. Além disso, discutimos a complexidade de tempo do Bubble Sort, destacando sua complexidade de tempo de pior caso O(n^2) e suas implicações para a eficiência.