Tipo de bolha

1. Algoritmo de classificação de bolhas
2. Exemplo de algoritmo de classificação de bolhas
3. Implementação do algoritmo de classificação de bolhas
4. Complexidade do algoritmo de classificação por bolha

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.

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:

• Segundo Passe:

• Terceiro Passe:

• Quarto Passe:

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(n²).

• 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(n²).

• 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.