Implémenter l'algorithme de tri par insertion en C++

Cet article montrera comment implémenter un algorithme de tri par insertion en C++.

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

Dans ce guide, nous allons vous montrer comment implémenter le tri par insertion en tant que fonction distincte qui prend une référence à l’objet std::vector et modifie le contenu en place. Le tri par insertion parcourt chaque élément du vecteur. Il s’assure que tous les éléments avant la position actuelle sont triés en comparant l’élément actuel avec les précédents dans l’ordre inverse.

Généralement, l’ordre de comparaison n’a pas beaucoup d’importance dans les performances de l’algorithme, mais nous supposons l’ordre inverse et implémentons le code en conséquence. Nous supposerons également que nous trions les éléments par ordre croissant. Pourtant, dans les cas réels, l’algorithme de tri générique devrait être capable de prendre une fonction de comparaison personnalisée comme argument. Notez que l’opération de comparaison force souvent l’élément à être décalé vers la droite si l’élément courant est inférieur au précédent. Cette dernière opération est implémentée à l’aide d’une autre boucle for imbriquée, qui invoque la fonction std::swap sur les éléments qui sont dans le mauvais ordre.

L’extrait de code suivant inclut la fonction insertionSort où la boucle for externe est responsable de la totalité du parcours du tableau. Nous initialisons l’itérateur sur le deuxième élément du vecteur car les étapes suivantes incluent la comparaison avec les précédentes - la boucle interne itère de l’élément actuel au premier pour les comparer. Si la fonction de comparaison évalue true, la paire est permutée. Notez que l’expression else force la boucle interne à se rompre lorsqu’au moins un élément précédent s’avère être inférieur à l’élément actuel.

#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 insertionSort(vector<T> &vec) {
  for (auto it = vec.begin() + 1; it != vec.end(); ++it) {
    auto key = it;

    for (auto i = it - 1; i >= vec.begin(); --i) {
      if (*i > *key) {
        std::swap(*i, *key);
        key--;
      } else {
        break;
      }
    }
  }
}

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

  printVector(vec1);
  insertionSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Production:

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

Alternativement, nous pouvons réimplémenter la fonction insertionSort en utilisant des constructions de boucle while si cette dernière est préférée comme une forme plus lisible pour l’utilisateur. Deux algorithmes suivent une logique d’implémentation similaire, et tous deux utilisent la fonction std::swap pour décaler des éléments. Le tri par insertion est un algorithme assez inefficace sur de grands ensembles de données, et sa performance moyenne est O(n²).

Le tri par insertion est similaire à un autre algorithme quadratique appelé tri par sélection ; ils parcourent tous les deux le vecteur. Après les n itérations, les premiers n éléments sont triés. Cependant, le tri par sélection évalue les éléments en avant à partir de la position actuelle contrairement au tri par insertion.

#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 insertionSort2(vector<T> &vec) {
  auto iter = vec.begin() + 1;
  while (iter != vec.end()) {
    auto key = iter;
    auto it = iter - 1;

    while (it >= vec.begin() && *it > *key) {
      std::swap(*it, *key);
      key--;
      it--;
    }
    iter++;
  }
}

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

  printVector(vec1);
  insertionSort2(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Production:

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

Le tri par insertion peut être plus efficace en pratique par rapport aux autres algorithmes O(n²) car il n’a pas toujours besoin de comparer l’élément courant avec tous les précédents. Pendant ce temps, le tri par sélection doit toujours rechercher dans chaque élément du sous-tableau non trié pour trouver le plus petit (ou le plus grand) élément. Notez que nous pouvons utiliser à la fois l’implémentation de la fonction insertionSort sur le vecteur de std::string car cette dernière classe implémente les surcharges de l’opérateur de comparaison. L’exemple suivant montre son utilisation de base avec le vecteur de chaîne et imprime la liste triée de mots.

#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 insertionSort(vector<T> &vec) {
  auto iter = vec.begin() + 1;
  while (iter != vec.end()) {
    auto key = iter;
    auto it = iter - 1;

    while (it >= vec.begin() && *it > *key) {
      std::swap(*it, *key);
      key--;
      it--;
    }
    iter++;
  }
}

int main() {
  vector<string> vec2 = {"highway", "song",  "work",
                         "borland", "death", "woman"};

  printVector(vec2);
  insertionSort(vec2);
  printVector(vec2);

  return EXIT_SUCCESS;
}

Production:

highway;
song;
work;
borland;
death;
woman;
borland;
death;
highway;
song;
woman;
work;