Algorithme de tri à bulles en C++

1. Implémenter le tri à bulles pour le conteneur std::vector
2. Analysez la complexité du tri des bulles avec des mesures de temps empiriques

Cet article explique plusieurs méthodes d’implémentation de l’algorithme de tri à bulles en C++.

Implémenter le tri à bulles pour le conteneur std::vector

Le tri à bulles est l’un des algorithmes de tri les plus simples. Il parcourt la liste des objets en comparant chaque paire adjacente, et s’ils ne sont pas ordonnés, les éléments sont permutés. Il est classé comme un algorithme de tri par comparaison, car la seule lecture des éléments est effectuée à l’aide de l’expression de comparaison. Dans l’exemple de code suivant, nous implémentons le tri à bulles pour travailler sur des objets vector génériques. Une seule fonction nommée bubbleSort est suffisante pour définir toute la routine de tri. La fonction est modélisée et prend une référence à un vector comme seul argument.

bubbleSort inclut deux boucles for imbriquées pour parcourir les éléments vector jusqu’à ce qu’ils soient triés par ordre croissant. Notez que chaque itération de la boucle for externe stocke un élément au bon endroit. Ce dernier élément est stocké à la fin du vecteur, et il se trouve qu’il s’agit du plus grand élément de la partie du vecteur qui est traversée dans la boucle interne. Notez que nous avons utilisé l’algorithme std::swap pour simplifier l’implémentation et la rendre plus lisible.

#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 bubbleSort(vector<T> &vec) {
  for (size_t i = 0; i < vec.size() - 1; ++i) {
    for (size_t j = 0; j < vec.size() - i - 1; ++j) {
      if (vec.at(j) > vec.at(j + 1)) std::swap(vec.at(j), vec.at(j + 1));
    }
  }
}

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

  printVector(vec1);
  bubbleSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Production:

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

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

Le tri à bulles appartient à une classe de durée d’exécution quadratique. En fait, le temps moyen et les performances dans le pire des cas de cet algorithme sont tous deux quadratiques - O(n²). Ainsi, cette méthode devient totalement inefficace pour les grands ensembles de données d’entrée. Il n’est pas utilisé pratiquement pour cette raison. Par exemple, si nous augmentons la longueur du vecteur d’entrée de 10, le temps d’exécution augmentera approximativement d’un facteur de 100. Notez, cependant, que le tri à bulles peut être assez efficace pour un cas particulier lorsque les éléments du vecteur d’entrée sont dans le désordre d’un seul endroit (par exemple, séquence 1032547698). Ce dernier cas rendrait la complexité de l’algorithme linéaire. L’exemple de code suivant mesure le temps d’exécution de deux vecteurs différents à l’aide de la fonction gettimeofday et affiche les résultats dans la console.

#include <sys/time.h>

#include <algorithm>
#include <ctime>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void bubbleSort(vector<T> &vec) {
  for (size_t i = 0; i < vec.size() - 1; ++i) {
    for (size_t j = 0; j < vec.size() - i - 1; ++j) {
      if (vec.at(j) > vec.at(j + 1)) std::swap(vec.at(j), vec.at(j + 1));
    }
  }
}

float time_diff(struct timeval *start, struct timeval *end) {
  return (end->tv_sec - start->tv_sec) + 1e-6 * (end->tv_usec - start->tv_usec);
}

int main() {
  struct timeval start {};
  struct timeval end {};

  vector<int> vec3(100, 10);
  vector<int> vec4(1000, 10);

  gettimeofday(&start, nullptr);
  bubbleSort(vec3);
  gettimeofday(&end, nullptr);
  printf("bubbleSort %zu elements: %0.8f sec\n", vec3.size(),
         time_diff(&start, &end));

  gettimeofday(&start, nullptr);
  bubbleSort(vec4);
  gettimeofday(&end, nullptr);
  printf("bubbleSort %zu elements: %0.8f sec\n", vec4.size(),
         time_diff(&start, &end));

  return EXIT_SUCCESS;
}

Production:

bubbleSort 100 elements: 0.00002500 sec
bubbleSort 1000 elements: 0.00184900 sec