A classificação por bolha é um algoritmo simples usado para classificar um determinado conjunto de n elementos fornecidos na forma de uma matriz com n número de elementos. A classificação por bolha compara todos os elementos um por um e os classifica com base em seus valores.
Se a matriz fornecida tiver que ser classificada em ordem crescente, a classificação por bolha começará comparando o primeiro elemento da matriz com o segundo elemento, se o primeiro elemento for maior que o segundo elemento, ele trocará os dois elementos e, em seguida, irá comparar o segundo e o terceiro elemento e assim por diante.
Se tivermos o total n elementos, então precisamos repetir esse processo n-1 vezes.
É conhecido como classificação por bolha, porque, a cada iteração completa, o maior elemento em uma determinada matriz borbulha em direção ao último lugar ou ao índice mais alto, assim como uma bolha d’água sobe até a superfície da água.
A classificação ocorre passando por todos os elementos um por um e comparando-os com o elemento adjacente e trocando-os se necessário.
NOTA: Se você não está familiarizado com a classificação na estrutura de dados, você deve fi primeiro aprenda o que é classificação para saber sobre os fundamentos da classificação.
Implementando o algoritmo de classificação por bolha
A seguir estão as etapas envolvidas na classificação por bolha (para classificar uma determinada matriz em ordem crescente):
- Começando com o primeiro elemento (índice = 0), compare o elemento atual com o próximo elemento da matriz.
- Se o elemento atual for maior que o próximo elemento da matriz, troque-os.
- Se o elemento atual for menor que o próximo elemento, vá para o próximo elemento. Repita a etapa 1.
Vamos considerar uma matriz com valores {5, 1, 6, 2, 4, 3}
Abaixo, temos um representação pictórica de como a classificação por bolhas irá classificar a matriz fornecida.
Assim, como podemos ver na representação acima, após o primeira iteração, 6 é colocado no último índice, que é a posição correta para ele.
Da mesma forma, após a segunda iteração, 5 estará no penúltimo índice e assim por diante.
É hora de escrever o código para classificação por bolha:
Embora a lógica acima classifique uma matriz não classificada, ainda assim o algoritmo acima não é eficiente porque, de acordo com a lógica acima, o for continuará em execução por 6 iterações, mesmo se a matriz for classificada após a segunda iteração.
Portanto, podemos otimizar claramente nosso algoritmo.
Algoritmo de classificação por bolha otimizado
Para otimizar nosso bubb No algoritmo de classificação, podemos introduzir um flag para monitorar se os elementos estão sendo trocados dentro do loop for interno.
Portanto, no loop for interno, verificamos se a troca de elementos está ocorrendo ou não, todas as vezes.
Se para uma iteração particular, nenhuma troca ocorreu lugar, significa que a matriz foi classificada e podemos pular para fora do loop for, em vez de executar todas as iterações.
Vamos considerar uma matriz com valores {11, 17, 18, 26, 23}
Abaixo, temos uma representação pictórica de como a classificação de bolha otimizada classificará a matriz fornecida.
Como podemos ver, na primeira iteração, ocorreu a troca, portanto atualizamos nosso valor de flag para 1, como resultado, a execução entra no loop for novamente. Mas na segunda iteração, nenhuma troca ocorrerá, portanto, o valor de flag permanecerá 0 e a execução sairá do loop.
No código acima, na função bubbleSort, se para um ciclo completo único de j iteração (loop for interno), nenhuma troca ocorre, então flag permanecerá 0 e então sairemos dos for loops, porque a matriz já foi classificada.
Análise de complexidade do Bubble Sort
No Bubble Sort, n-1 as comparações serão feitas na primeira passagem, n-2 na 2ª passagem, n-3 na 3ª passagem e assim por diante. Portanto, o número total de comparações será,
(n-1) + (n-2) + (n-3) + ….. + 3 + 2 + 1Sum = n (n- 1) /2i.e O (n2)
Portanto, a complexidade de tempo do Bubble Sort é O (n2).
A principal vantagem do Bubble Sort é a simplicidade do algoritmo.
A complexidade do espaço para Bubble Sort é O (1), porque apenas um único espaço de memória adicional é necessário, ou seja, para a variável temp.
Além disso, o melhor caso de complexidade de tempo será O (n), quando a lista já está classificada.
A seguir estão a complexidade de tempo e espaço para o algoritmo de classificação de bolha.
Agora que aprendemos o algoritmo de classificação por bolha, você pode verificar esses algoritmos de classificação e suas aplicações também:
- Classificação por inserção
- Classificação por seleção
- Classificação rápida
- classificação por mesclagem
- classificação por heap
- classificação por contagem
