Implementieren des Merge-Sort-Algorithmus in C++

1. Implementieren von Merge Sort für den Container std::vector in C++
2. Analysieren Sie die Sortierkomplexität mit empirischen Timing-Messungen

In diesem Artikel wird vorgestellt, wie ein Zusammenführungssortieralgorithmus in C++ implementiert wird.

Implementieren von Merge Sort für den Container std::vector in C++

Merge-Sort verwendet die Divide-and-Conquer-Strategie, um Effizienz zu erreichen, und kann als universeller Sortieralgorithmus für große Listen verwendet werden. Die Idee hinter dem Algorithmus besteht darin, den Eingabevektor in mehrere kleinere Vektoren aufzuteilen und dann jeden dieser Vektoren zu sortieren. Sobald die kleineren Vektoren fertig sind, können wir sie zu einer einzigen Liste zusammenführen, was eine relativ einfachere Operation ist. Beachten Sie, dass im folgenden Codebeispiel diese Methode mithilfe der Rekursion implementiert wird, da sie für diese Lösung optimal geeignet ist. Ein rekursiver Prozess wird verwendet, um den Originalvektor mehrmals zu dividieren, bis wir die Zweielementvektoren erhalten, in denen die Vergleichsfunktion aufgerufen wird. Wenn jedes Paar sortiert ist, werden sie zu Vektoren mit vier Elementen usw. zusammengeführt, bis die letzte Rekursionsebene zurückgegeben wird.

Die Funktion mergeSort ist das Herzstück des rekursiven Prozesses. Es verwendet die Vektorreferenz als einziges Argument und prüft, ob die Größe kleiner als eins ist. Wenn dies der Fall ist, gilt der Vektor als sortiert und die Funktion kehrt zurück. Wenn der Vektor zwei oder mehr Elemente enthält, wird er in zwei separate Vektorobjekte aufgeteilt und die Funktion mergeSort wird für jedes von ihnen aufgerufen. Beachten Sie, dass der letzte Teil erzwingt, dass die Sortierung bei den kleinsten Untervektoren beginnt. Sobald die Rekursion ein solches Niveau erreicht, kehren beide mergeSort-Funktionen zurück und der folgende Code beginnt mit der Ausführung. Zuerst wird der Vektor vec gelöscht und dann die Funktion merge aufgerufen. Die Funktion merge wird mit einem iterativen Prozess implementiert, der bei genauer Beobachtung erkundet werden kann. Im Allgemeinen verbindet der letztere Schritt die kleinsten sortierten Vektoren zu einem Vektorobjekt.

#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 merge(vector<T> &vec, vector<T> &v1, vector<T> &v2) {
  auto siz1 = v1.size();
  auto siz2 = v2.size();
  size_t p1 = 0;
  size_t p2 = 0;

  while (p1 < siz1 && p2 < siz2) {
    if (v1.at(p1) < v2.at(p2))
      vec.push_back(v1.at(p1++));
    else
      vec.push_back(v2.at(p2++));
  }

  while (p1 < siz1) vec.push_back(v1.at(p1++));
  while (p2 < siz2) vec.push_back(v2.at(p2++));
}

template <typename T>
void mergeSort(vector<T> &vec) {
  if (vec.size() <= 1) return;

  auto iter = vec.begin() + vec.size() / 2;
  vector<T> v1(vec.begin(), iter);
  vector<T> v2(iter, vec.end());

  mergeSort(v1);
  mergeSort(v2);

  vec.clear();
  merge(vec, v1, v2);
}

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

  printVector(vec1);
  mergeSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Ausgabe:

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

Alternativ könnte man den vorherigen Code mit dem STL-Algorithmus std::merge umschreiben, der das Lesen des Codes vereinfachen könnte. Beachten Sie, dass die Funktion std::merge unsere merge-Implementierung ersetzt und das Zusammenführen von Vektoren mit einer einzigen Anweisung im Funktionsrumpf mergeSort erreicht werden kann. Wenn die letzte Rekursionsebene beim ersten Aufruf von mergeSort zwei Vektoren zurückgibt, speichert der letzte Aufruf von std::merge den sortierten Inhalt im ursprünglichen vec-Objekt, das von der main-Funktion aus beobachtet werden kann.

#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 mergeSort2(vector<T> &vec) {
  if (vec.size() <= 1) return;

  auto iter = vec.begin() + vec.size() / 2;
  vector<T> v1(vec.begin(), iter);
  vector<T> v2(iter, vec.end());

  mergeSort2(v1);
  mergeSort2(v2);

  vec.clear();
  std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(),
             std::back_inserter(vec));
}

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

  printVector(vec1);
  mergeSort2(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Analysieren Sie die Sortierkomplexität mit empirischen Timing-Messungen

Merge-Sort bietet O(nlogn) Worst-Case-Laufzeit, was zufällig einer der besten unter den heutigen universellen Sortieralgorithmen ist. Es hat die lineare Raumkomplexität in einem Worst-Case-Szenario, die mehr ist, als der schnelle Sortieralgorithmus bietet. Letzteres ist in der Praxis tendenziell relativ schneller, wenn die Implementierung effiziente Methoden zur Auswahl der Pivot-Variablen verwendet.

Auch wenn die rekursive Methode ziemlich schwierig zu verstehen sein kann, kann man immer einen Debugger verwenden, um in die Details jedes Schritts einzutauchen. Auf der höheren Ebene können wir jedoch das folgende Codebeispiel verwenden, um die rekursiven Funktionsaufrufe zwischen verschiedenen Vektorgrößen zu zählen. Beachten Sie, dass die Summe der rekursiven Aufrufe dazu neigt, die Funktion - 2n - 2 zu sein, wobei n der Anzahl der Elemente im Vektor entspricht.

#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 mergeSort2(vector<T> &vec, int &level) {
  if (vec.size() <= 1) return;

  auto iter = vec.begin() + vec.size() / 2;
  vector<T> v1(vec.begin(), iter);
  vector<T> v2(iter, vec.end());

  mergeSort2(v1, ++level);
  mergeSort2(v2, ++level);

  vec.clear();
  std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(),
             std::back_inserter(vec));
}

int main() {
  vector<int> vec3(100, 10);
  vector<int> vec4(200, 10);

  int recursion_level = 0;

  mergeSort2(vec3, recursion_level);
  cout << "recursion level: " << recursion_level << endl;

  recursion_level = 0;
  mergeSort2(vec4, recursion_level);
  cout << "recursion level: " << recursion_level << endl;

  return EXIT_SUCCESS;
}

Ausgabe:

recursion level: 198
recursion level: 398