Algoritmo de clasificación de burbujas en C++

1. Implementar Bubble Sort para el contenedor std::vector
2. Analice la complejidad de la clasificación de burbujas con medidas de tiempo empíricas

Este artículo explicará varios métodos de cómo implementar el algoritmo de clasificación de burbujas en C++.

Implementar Bubble Sort para el contenedor std::vector

La clasificación de burbujas es uno de los algoritmos de clasificación más simples. Repite la lista de objetos comparando cada par adyacente, y si no están ordenados, los elementos se intercambian. Se clasifica como un algoritmo de clasificación de comparación, ya que la única lectura de los elementos se realiza mediante la expresión de comparación. En el siguiente código de ejemplo, implementamos la clasificación de burbujas para trabajar en objetos vectoriales genéricos. Una sola función llamada bubbleSort es suficiente para definir toda la rutina de clasificación. La función tiene una plantilla y toma una referencia a un vector como único argumento.

bubbleSort incluye dos bucles for anidados para iterar sobre los elementos vector hasta que se clasifiquen en orden ascendente. Tenga en cuenta que cada iteración del bucle externo for almacena un elemento en el lugar correcto. El último elemento se almacena al final del vector y resulta ser el elemento más grande en la parte del vector que se atraviesa en el bucle interno. Observe que utilizamos el algoritmo std::swap para simplificar la implementación y hacerla más legible.

#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;
}

Producción :

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

Analice la complejidad de la clasificación de burbujas con medidas de tiempo empíricas

La clasificación de burbujas pertenece a una clase de tiempo de ejecución cuadrático. De hecho, el tiempo medio y el rendimiento en el peor de los casos de este algoritmo son cuadráticos - O(n²). Por lo tanto, este método se vuelve completamente ineficaz para grandes conjuntos de datos de entrada. No se usa prácticamente por esta misma razón. Por ejemplo, si aumentamos la longitud del vector de entrada en 10, el tiempo de ejecución aumentará aproximadamente en un factor de 100. Sin embargo, tenga en cuenta que la clasificación de burbujas puede ser bastante eficiente para un caso especial cuando los elementos del vector de entrada están desordenados en un solo lugar (por ejemplo, secuencia 1032547698). El último caso haría lineal la complejidad del algoritmo. El siguiente ejemplo de código mide el tiempo de ejecución de dos vectores diferentes utilizando la función gettimeofday y envía los resultados a la consola.

#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;
}

Producción :

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