Algoritmo de classificação de bolhas em C++

1. Implementar classificação por bolha para recipiente std::vector
2. Analise a complexidade da classificação por bolha com medições de tempo empíricas

Este artigo explicará vários métodos de como implementar o algoritmo de classificação de bolhas em C++.

Implementar classificação por bolha para recipiente std::vector

A classificação por bolha é um dos algoritmos de classificação mais simples. Ele itera através da lista de objetos comparando cada par adjacente e, se eles não forem ordenados, os elementos serão trocados. É classificado como um algoritmo de ordenação por comparação, pois a única leitura dos elementos é feita através da expressão de comparação. No código de exemplo a seguir, implementamos a classificação por bolha para funcionar em objetos vector genéricos. Uma única função chamada bubbleSort é suficiente para definir toda a rotina de classificação. A função é modelada e leva uma referência a um vector como o único argumento.

bubbleSort inclui dois loops for aninhados para iterar sobre os elementos vetor até que sejam classificados em ordem crescente. Observe que cada iteração do loop externo for armazena um elemento em um lugar correto. O último elemento é armazenado no final do vetor e passa a ser o maior elemento na parte do vetor que é percorrida no loop interno. Observe que utilizamos o algoritmo std::swap para simplificar a implementação e torná-la mais legível.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void bubbleSort(vector<T> &vec) {
  for (size_t i = 0; i < vec.size() - 1; ++i) {
    for (size_t j = 0; j < vec.size() - i - 1; ++j) {
      if (vec.at(j) > vec.at(j + 1)) std::swap(vec.at(j), vec.at(j + 1));
    }
  }
}

int main() {
  vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};

  printVector(vec1);
  bubbleSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Resultado:

43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;

Analise a complexidade da classificação por bolha com medições de tempo empíricas

A classificação por bolha pertence a uma classe quadrática de tempo de execução. Na verdade, o tempo médio e o desempenho de pior caso desse algoritmo são quadráticos - O(n²). Portanto, esse método se torna totalmente ineficiente para grandes conjuntos de dados de entrada. Não é usado praticamente por esse motivo. Por exemplo, se aumentarmos o comprimento do vetor de entrada em 10, o tempo de execução aumentará aproximadamente por um fator de 100. Observe, porém, que a classificação por bolha pode ser bastante eficiente para um caso especial quando os elementos no vetor de entrada estão fora de ordem em apenas um lugar (por exemplo, sequência 1032547698). O último caso tornaria a complexidade do algoritmo linear. O exemplo de código a seguir mede o tempo de execução para dois vetores diferentes usando a função gettimeofday e envia os resultados para o console.

#include <sys/time.h>

#include <algorithm>
#include <ctime>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void bubbleSort(vector<T> &vec) {
  for (size_t i = 0; i < vec.size() - 1; ++i) {
    for (size_t j = 0; j < vec.size() - i - 1; ++j) {
      if (vec.at(j) > vec.at(j + 1)) std::swap(vec.at(j), vec.at(j + 1));
    }
  }
}

float time_diff(struct timeval *start, struct timeval *end) {
  return (end->tv_sec - start->tv_sec) + 1e-6 * (end->tv_usec - start->tv_usec);
}

int main() {
  struct timeval start {};
  struct timeval end {};

  vector<int> vec3(100, 10);
  vector<int> vec4(1000, 10);

  gettimeofday(&start, nullptr);
  bubbleSort(vec3);
  gettimeofday(&end, nullptr);
  printf("bubbleSort %zu elements: %0.8f sec\n", vec3.size(),
         time_diff(&start, &end));

  gettimeofday(&start, nullptr);
  bubbleSort(vec4);
  gettimeofday(&end, nullptr);
  printf("bubbleSort %zu elements: %0.8f sec\n", vec4.size(),
         time_diff(&start, &end));

  return EXIT_SUCCESS;
}

Resultado:

bubbleSort 100 elements: 0.00002500 sec
bubbleSort 1000 elements: 0.00184900 sec