Bubble-Sort-Algorithmus in C++

1. Implementieren von Bubble-Sort für den Container std::vector
2. Analyse der Bubble-Sort-Komplexität mit empirischen Timing-Messungen

In diesem Artikel werden verschiedene Methoden zum Implementieren des Bubble-Sort-Algorithmus in C++ erläutert.

Implementieren von Bubble-Sort für den Container std::vector

Bubble-Sort ist einer der einfachsten Sortieralgorithmen. Es durchläuft die Liste von Objekten und vergleicht jedes benachbarte Paar, und wenn sie nicht geordnet sind, werden die Elemente vertauscht. Es wird als Vergleichssortierungsalgorithmus klassifiziert, da das einzige Lesen der Elemente mithilfe des Vergleichsausdrucks erfolgt. Im folgenden Beispielcode implementieren wir Bubble-Sort, um mit generischen Vektor-Objekten zu arbeiten. Eine einzige Funktion namens bubbleSort reicht aus, um die gesamte Sortierroutine zu definieren. Die Funktion ist templatisiert und nimmt als einziges Argument eine Referenz auf einen Vektor.

bubbleSort enthält zwei verschachtelte for-Schleifen, um über die Vektor-Elemente zu iterieren, bis sie in aufsteigender Reihenfolge sortiert sind. Beachten Sie, dass jede Iteration der äußeren for-Schleife ein Element an der richtigen Stelle speichert. Das letztere Element wird am Ende des Vektors gespeichert und ist zufällig das größte Element in dem Teil des Vektors, der in der inneren Schleife durchlaufen wird. Beachten Sie, dass wir den std::swap-Algorithmus verwendet haben, um die Implementierung zu vereinfachen und lesbarer zu machen.

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

Ausgabe:

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

Analyse der Bubble-Sort-Komplexität mit empirischen Timing-Messungen

Bubblesort gehört zu einer quadratischen Laufzeitklasse. Tatsächlich sind die durchschnittliche Zeit und die Worst-Case-Leistung dieses Algorithmus beide quadratisch – O(n²). Somit wird dieses Verfahren für große Eingabedatensätze völlig ineffizient. Aus diesem Grund wird es praktisch nicht verwendet. Wenn wir beispielsweise die Länge des Eingabevektors um 10 erhöhen, wächst die Laufzeit ungefähr um den Faktor 100. Beachten Sie jedoch, dass die Blasensortierung für einen speziellen Fall sehr effizient sein kann, wenn Elemente im Eingabevektor nur an einer Stelle nicht in der Reihenfolge sind (z. B. Sequenz 1032547698). Der letztere Fall würde die Komplexität des Algorithmus linear machen. Das folgende Codebeispiel misst die Laufzeit für zwei verschiedene Vektoren mit der Funktion gettimeofday und gibt die Ergebnisse an die Konsole aus.

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

Ausgabe:

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