TUTORIAL · Algorithm
Tipo de bolha
Este tutorial apresenta o algoritmo de classificação por bolha.
Nesta página
A classificação por bolha é um algoritmo de classificação simples. Funciona por comparação repetida de elementos adjacentes e trocando-os se estiverem na ordem errada. As comparações repetidas borbulham o menor / maior elemento no final da matriz e, portanto, esse algoritmo é denominado bubble sort. Embora ineficiente, ainda representa a base para algoritmos de classificação.
Algoritmo de classificação de bolhas
Vamos supor que temos um array não classificado A[] contendo n elementos.
-
Comece a partir do par dos dois primeiros elementos (
A[0]eA[1]), compare seus valores e troque-os se não estiverem na ordem correta. Faça o mesmo para o próximo par (A[1]eA[2]) e mova da mesma forma para o resto da matriz. O menor / maior elemento está na última posição após esta etapa. -
Repita as etapas acima
(n-2)vezes para as iterações restantes. Reduza o tamanho do array em um a cada vez, pois o último elemento já está classificado. O menor / maior elemento nesta iteração se move para a posição mais à direita.
A etapa 1 no algoritmo acima também é chamada de aprovação. Para classificar uma matriz de tamanho n, são necessários passes n-1.
Exemplo de algoritmo de classificação de bolhas
Suponha que temos o array: (5,3,4,2,1). Vamos classificá-lo usando o algoritmo de classificação de bolhas.
- Primeira passagem:
| (5 3 4 2 1) | → | (3 5 4 2 1) | (3 < 5 trocados) |
| (3 5 4 2 1) | → | (3 4 5 2 1) | (4 < 5 trocados) |
| (3 4 5 2 1) | → | (3 4 2 5 1) | (2 < 5 trocados) |
| (3 4 2 5 1) | → | (3 4 2 1 5) | (1 < 5 trocados) |
- Segundo Passe:
| (3 4 2 1 5) | → | (3 4 2 1 5) | |
| (3 4 2 1 5) | → | (3 2 4 1 5) | (2 < 4 trocados) |
| (3 2 4 1 5) | → | (3 2 1 4 5) | (1 < 4 trocados) |
- Terceiro Passe:
| (3 2 1 4 5) | → | (2 3 1 4 5) | (2 < 3 trocados) |
| (2 3 1 4 5) | → | (2 1 3 4 5) | (1 < 3 trocados) |
- Quarto Passe:
| (2 1 3 4 5) | → | (1 2 3 4 5) | (1 < 2 trocados) |
Obtemos a matriz classificada após a quarta passagem - (1 2 3 4 5)
Implementação do algoritmo de classificação de bolhas
#include <iostream>
using namespace std;
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
int n = 5;
int arr[5] = {5, 3, 4, 2, 1};
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
bubble_sort(arr, n); // Sort elements in ascending order
cout << "Output array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
Complexidade do algoritmo de classificação por bolha
Complexidade de tempo
- Caso Médio
Em média, as comparações n-i são feitas na i-ésima passagem do tipo de bolha. Portanto, se houver n passes, a complexidade de tempo média pode ser dada por
(n-1) + (n-2) + (n-3) ..... + 1 = n*(n-1)/2
Logo, a complexidade do tempo é da ordem de O(n2).
- Pior caso
O pior caso ocorre quando a matriz é classificada inversamente e o número máximo de comparações e trocas deve ser executado.
O pior caso de complexidade de tempo é O(n2).
- Melhor caso
O melhor caso ocorre quando a matriz já está classificada e, então, apenas N comparações são necessárias.
O melhor caso de complexidade de tempo é O(n).
Complexidade do Espaço
A Complexidade de Espaço para este algoritmo é O(n) porque nenhuma memória extra além de uma variável temporária é necessária.
