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

1. Implémenter le tri par fusion pour le conteneur std::vector en C++
2. Analysez la complexité du tri par fusion avec des mesures de temps empiriques

Cet article présentera comment implémenter un algorithme de tri par fusion en C++.

Implémenter le tri par fusion pour le conteneur std::vector en C++

Le tri par fusion utilise la stratégie diviser pour régner pour atteindre l’efficacité, et il peut être utilisé comme algorithme de tri général pour les grandes listes. L’idée derrière l’algorithme est de diviser le vecteur d’entrée en plusieurs vecteurs plus petits, puis de trier chacun de ces vecteurs. Une fois les vecteurs plus petits terminés, nous pouvons les fusionner en une seule liste, ce qui s’avère être une opération relativement plus simple. Notez que l’exemple de code suivant implémente cette méthode en utilisant la récursivité car elle est parfaitement adaptée à cette solution. Un processus récursif est utilisé pour diviser le vecteur d’origine plusieurs fois jusqu’à ce que nous obtenions les vecteurs à deux éléments, où la fonction de comparaison sera appelée. Lorsque chaque paire est triée, elles sont fusionnées en vecteurs à quatre éléments et ainsi de suite jusqu’au retour du niveau final de récursivité.

La fonction mergeSort est la partie centrale du processus récursif. Il prend la référence vectorielle comme seul argument et vérifie si la taille est inférieure à un. Si c’est le cas, le vecteur est qualifié de trié et la fonction est renvoyée. Lorsque le vecteur contient deux éléments ou plus, il est divisé en deux objets vectoriels distincts et la fonction mergeSort est appelée sur chacun d’eux. Notez que cette dernière partie force le tri à commencer sur les plus petits sous-vecteurs. Une fois que la récursivité atteint ce niveau, les deux fonctions mergeSort reviennent et le code suivant démarre l’exécution. Dans un premier temps, le vecteur vec est effacé, puis la fonction merge est appelée. La fonction merge est implémentée avec un processus itératif qui peut être exploré avec une observation attentive. En général, cette dernière étape joint les plus petits vecteurs triés en un seul objet vectoriel.

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

Production:

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

Alternativement, on pourrait réécrire le code précédent en utilisant l’algorithme STL std::merge qui pourrait simplifier le code pour la lecture. Notez que la fonction std::merge remplace notre implémentation merge et que la fusion vectorielle peut être effectuée avec une seule instruction dans le corps de la fonction mergeSort. Lorsque le niveau final de récursivité renvoie deux vecteurs dans le premier appel de mergeSort, la dernière invocation de std::merge stockera le contenu trié dans l’objet vec d’origine qui peut être observé à partir de la fonction main.

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

Analysez la complexité du tri par fusion avec des mesures de temps empiriques

Le tri par fusion offre un temps d’exécution dans le pire des cas O(nlogn), qui se trouve être l’un des meilleurs parmi les algorithmes de tri à usage général contemporains. Il a la complexité de l’espace linéaire dans le pire des cas qui est plus que ce que propose l’algorithme de tri rapide. Cette dernière a tendance à être relativement plus rapide en pratique lorsque la mise en œuvre utilise des méthodes efficaces pour choisir la variable pivot.

Même si la méthode récursive peut être assez difficile à comprendre, on peut toujours utiliser un débogueur pour plonger dans les détails de chaque étape. Au niveau supérieur, cependant, nous pouvons utiliser l’exemple de code suivant pour compter les appels de fonctions récursives entre différentes tailles de vecteur. Notez que la somme des appels récursifs tend à être la fonction - 2n - 2 où n correspond au nombre d’éléments dans le vecteur.

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

Production:

recursion level: 198
recursion level: 398