Implémenter l'algorithme de tri rapide en C++

1. Implémenter Quicksort pour le conteneur std::vector
2. Enquêter sur les niveaux de récursivité dans la mise en œuvre du tri rapide

Cet article présentera plusieurs méthodes sur la façon d’implémenter l’algorithme de tri rapide en C++.

Implémenter Quicksort pour le conteneur std::vector

Quicksort est l’un des algorithmes de tri polyvalents les plus rapides utilisés dans les bases de code contemporaines. Il utilise la technique diviser pour régner similaire à l’algorithme de tri par fusion. Cependant, le premier dépend d’une opération communément appelée partitionnement. Le vecteur d’origine est découpé sur l’élément dit pivot, qui délimite les éléments plus petits avant lui et les plus grands après. Notez que ces comparaisons sont relatives à la valeur pivot, que l’utilisateur doit choisir. Le choix de la valeur pivot se trouve être le facteur critique pour la performance de cet algorithme, que nous analyserons plus loin dans l’article. À ce stade, supposons que l’élément pivot est le premier élément du vecteur d’origine. Une fois que nous avons la méthode de sélection par pivot, nous pouvons partitionner le vecteur en deux vecteurs plus petits qui seront triés récursivement sur place. Notez que l’opération de tri rapide est similaire au tri par fusion en ce sens qu’elle partitionne également les vecteurs plusieurs fois jusqu’à ce que leurs positions de départ se croisent.

L’exemple de code suivant implémente l’algorithme avec une fonction sort récursive qui appelle la fonction partitionVec à chaque fois qu’elle est invoquée. Le processus de partitionnement peut être effectué en temps linéaire en échangeant des éléments dans le même objet vectoriel. Cette dernière opération est mise en œuvre à l’aide de la fonction partitionVec, qui fait également fonction de tri d’une certaine manière.

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

Production:

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

Enquêter sur les niveaux de récursivité dans la mise en œuvre du tri rapide

Quicksort a la complexité temporelle moyenne O(nlogn), qui est comparable à l’algorithme de tri par fusion. Notez, cependant, que l’algorithme de tri rapide dépend fortement de la méthode de sélection du pivot. Dans ce cas, nous avons choisi la version naïve pour choisir la valeur pivot, qui était le premier élément du vecteur. Cela peut donner des temps d’exécution assez mauvais avec O(n²) dans certains scénarios. En pratique, le choix du pivot aléatoire a une forte probabilité d’obtenir la performance O(nlogn). Cependant, il faut être conscient de la méthode de sélection du pivot basée sur les données d’entrée si la performance maximale est requise.

Nous pouvons observer le processus récursif dans l’extrait de code précédent en utilisant l’argument de fonction supplémentaire qui compte chaque invocation de la fonction sort. L’exemple suivant exécute un test similaire sur deux vecteurs de tailles différentes et imprime les sommes correspondantes. Notez que la somme des appels récursifs relie la taille du vecteur à la fonction suivante - 2n - 1, où n désigne le nombre d’éléments.

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

Production:

level: 199
level: 399