Classificação por bolha é considerado um dos algoritmos de classificação mais simples que funciona trocando repetidamente os elementos adjacentes se eles estiverem na ordem errada. Com um algoritmo de classificação por bolha, você poderá ver que o maior elemento (assumindo que estamos classificando do menor para o maior) “borbulhará” no topo da lista ou matriz.

Exemplo:
Suponha que queremos classificar uma lista ou array de elementos em ordem crescente (do menor para o maior): List = (3,1,2)

Visto que nenhuma troca ocorreu, isso nos diz que o array é já classificado em ordem crescente!

Melhor caso

Agora, vamos tentar o mesmo algoritmo novamente, mas desta vez usando o melhor cenário, que é quando os elementos já estão classificados na ordem ( ascendente) gostaríamos.

Uma vez que nenhuma troca ocorreu, terminamos, e o algoritmo fez apenas 2 comparações e o número de elementos na matriz chamaremos de n = 3. Portanto, podemos ver que para n elementos este algoritmo no melhor caso terá apenas n-1 comparações, n-1 = O (n)

O procedimento ou algoritmo que usamos está abaixo:

Este algoritmo usa um sinalizador para saber se os elementos foram trocados ou não , que permite que o melhor caso do algoritmo de classificação por bolha seja O (n) em vez de O (n²) como outra implementação de classificação por bolha.

O algoritmo acima
Pior caso = O (n²)
Melhor caso = O (n)

Vamos dar uma olhada em uma implementação diferente do algoritmo de classificação de bolha:

BUBBLESORT(A)
1 for i = 1 to A.length - 1
2 for j = A.length downto i + 1
3 if A < A
4 exchange A with A

O algoritmo acima
Pior caso = O (n²)
Melhor caso = O (n²)

Pior caso

Vamos classificar uma matriz ou lista = (3,2,1) este seria o pior caso em que a lista está na ordem completamente oposta à que desejamos (em ordem crescente) usando o algoritmo acima.

Primeira passagem:
(3,2,1) – > Compare os elementos 3 & 2
(2,3 , 1) – > Troca 3 & 2 desde 2 < 3
( 2,3,1) – > Compare os elementos 3 & 1
(2,1,3) – > Troca 1 & 3 desde 1 < 3

Segunda passagem:
(2,1,3) – > Compare os elementos 2 & 1
(1,2,3) – > Troca 2 & 1 desde 1 < 2
(1,2,3) – > Compare os elementos 2 & 3
(1,2,3) – > Nenhuma TROCA necessária desde 2 < 3

Agora terminamos o loop através de ambos os loops, então a matriz deve ser classificada em ordem crescente.

Observe que fizemos 4 comparações no segundo exemplo acima, e o número de elementos na matriz que chamaremos de ‘n’ = 3, então o número de comparações feitas é (n-1) ², e (n-1) ² = O (n²)

Também um ótimo livro para prepará-lo para entrevistas de codificação / programação é chamado de quebrar a entrevista de codificação. Isso o ajudará a se familiarizar com algoritmos de classificação e resolução de problemas, portanto, certifique-se de dar uma olhada!

Obrigado por ler este artigo, espero que seja útil para todos vocês! Continue aprendendo e, se quiser mais vídeos de análise de algoritmo, visite e inscreva-se em meus canais do YouTube (randerson112358 & compsci112358)

Confira o seguinte mais conteúdo / vídeos sobre análise e programação de algoritmos:

Canal do YouTube:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:

Site:

Tutoriais em vídeo sobre relação de recorrência:

Tutorial em vídeo sobre análise de algoritmo:

Twitter: