Implementieren des Quicksort-Algorithmus in C++

1. Implementieren Sie Quicksort für den std::vector-Container
2. Untersuchen Sie die Rekursionsebenen in der Quicksort-Implementierung

In diesem Artikel werden mehrere Methoden zum Implementieren des Quicksort-Algorithmus in C++ veranschaulicht.

Implementieren Sie Quicksort für den std::vector-Container

Quicksort ist einer der schnellsten universellen Sortieralgorithmen, die in modernen Codebasen verwendet werden. Es verwendet die Divide-and-Conquer-Technik ähnlich dem Merge-Sort-Algorithmus. Ersteres hängt jedoch von einer Operation ab, die allgemein als Partitionierung bezeichnet wird. Der Originalvektor wird auf das als pivot bekannte Element aufgeteilt, das kleinere Elemente davor und grössere danach abgrenzt. Beachten Sie, dass diese Vergleiche relativ zum Pivot-Wert sind, den der Benutzer auswählen sollte. Die Wahl des Pivot-Werts ist zufällig der kritische Faktor für die Leistung dieses Algorithmus, den wir später in diesem Artikel analysieren werden. An dieser Stelle nehmen wir an, dass das Pivot-Element das erste Element im ursprünglichen Vektor ist. Sobald wir die Methode für die Pivot-Auswahl haben, können wir den Vektor in zwei kleinere Vektoren unterteilen, die rekursiv sortiert werden. Beachten Sie, dass die Quicksort-Operation der Merge-Sortierung insofern ähnelt, als sie die Vektoren auch mehrmals partitioniert, bis sich ihre Startpositionen kreuzen.

Der folgende Beispielcode implementiert den Algorithmus mit einer rekursiven Funktion sort, die bei jedem Aufruf die Funktion partitionVec aufruft. Der Partitionierungsprozess kann in linearer Zeit erfolgen, indem Elemente im gleichen Vektorobjekt ausgetauscht werden. Letztere Operation wird mit der Funktion partitionVec realisiert, die in gewisser Weise auch als Sortierfunktion fungiert.

#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>
T partitionVec(vector<T> &vec, size_t start, size_t end) {
  T pivot = vec.at(start);
  auto lh = start + 1;
  auto rh = end;

  while (true) {
    while (lh < rh && vec.at(rh) >= pivot) rh--;
    while (lh < rh && vec.at(lh) < pivot) lh++;

    if (lh == rh) break;

    T tmp = vec.at(lh);
    vec.at(lh) = vec.at(rh);
    vec.at(rh) = tmp;
  }

  if (vec.at(lh) >= pivot) return start;
  vec.at(start) = vec.at(lh);
  vec.at(lh) = pivot;
  return lh;
}

template <typename T>
void sort(vector<T> &vec, size_t start, size_t end) {
  if (start >= end) return;

  auto boundary = partitionVec(vec, start, end);

  sort(vec, start, boundary);
  sort(vec, boundary + 1, end);
}

template <typename T>
void quickSort(vector<T> &vec) {
  sort(vec, 0, vec.size() - 1);
}

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

  printVector(vec1);
  quickSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Ausgabe:

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

Untersuchen Sie die Rekursionsebenen in der Quicksort-Implementierung

Quicksort hat die durchschnittliche Zeitkomplexität O(nlogn), die dem Merge-Sort-Algorithmus gleichkommt. Beachten Sie jedoch, dass der Quicksort-Algorithmus stark von der Pivot-Auswahlmethode abhängt. In diesem Fall haben wir die naive Version für die Auswahl des Pivot-Werts gewählt, der das erste Element im Vektor war. Dies kann in bestimmten Szenarien zu ziemlich schlechten Laufzeiten mit O(n²) führen. In der Praxis hat die Wahl des zufälligen Pivots eine hohe Wahrscheinlichkeit, die Leistung von O(nlogn) zu erzielen. Allerdings sollte man sich der Pivot-Auswahlmethode auf der Grundlage von Eingabedaten bewusst sein, wenn die maximale Leistung erforderlich ist.

Wir können den rekursiven Prozess im vorherigen Code-Schnipsel beobachten, indem wir das zusätzliche Funktionsargument verwenden, das jeden Aufruf der Funktion sort zählt. Im folgenden Beispiel wird ein ähnlicher Test an zwei Vektoren unterschiedlicher Größe ausgeführt und die entsprechenden Summen ausgegeben. Beachten Sie, dass die Summe der rekursiven Aufrufe die Vektorgröße mit der folgenden Funktion in Beziehung setzt - 2n - 1, wobei n die Anzahl der Elemente bezeichnet.

#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>
auto partitionVec(vector<T> &vec, size_t start, size_t end) {
  T pivot = vec.at(start);
  auto lh = start + 1;
  auto rh = end;

  while (true) {
    while (lh < rh && vec.at(rh) >= pivot) rh--;
    while (lh < rh && vec.at(lh) < pivot) lh++;

    if (lh == rh) break;

    T tmp = vec.at(lh);
    vec.at(lh) = vec.at(rh);
    vec.at(rh) = tmp;
  }

  if (vec.at(lh) >= pivot) return start;
  vec.at(start) = vec.at(lh);
  vec.at(lh) = pivot;
  return lh;
}

template <typename T>
void sort(vector<T> &vec, size_t start, size_t end, int &level) {
  if (start >= end) return;

  auto boundary = partitionVec(vec, start, end);

  sort(vec, start, boundary, ++level);
  sort(vec, boundary + 1, end, ++level);
}

template <typename T>
void quickSort(vector<T> &vec, int &level) {
  sort(vec, 0, vec.size() - 1, ++level);
}

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

  int recursion_level = 0;

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

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

  return EXIT_SUCCESS;
}

Ausgabe:

level: 199
level: 399