Algoritmo de clasificación de burbujas en C++

Jinku Hu 12 octubre 2023
  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
Algoritmo de clasificación de burbujas en C++

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(n2). 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
Autor: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn Facebook

Artículo relacionado - C++ Algorithm