Implémenter l'algorithme de tri de sélection en C++

Cet article explique comment implémenter l’algorithme de tri par sélection en C++.

Implémenter le tri de sélection pour le conteneur std::vector en C++

Parmi les algorithmes de tri simples, vous pouvez considérer le tri par sélection comme l’un des plus simples à mettre en œuvre ; bien qu’il ait la complexité O(n²), et le rend totalement inefficace sur les grands vecteurs.

Le tri par sélection peut être spécifié comme la routine suivante : Au début, nous trouvons la valeur minimale dans le vecteur et l’échangeons avec le premier élément. Ensuite, nous déplaçons le pointeur sur le deuxième élément et trouvons la valeur minimale du sous-vecteur restant à échanger avec le deuxième élément. Nous continuons les étapes précédentes pour le reste du vecteur tout en avançant le pointeur un élément à la fois.

Une autre explication du tri par sélection pourrait consister à diviser le vecteur d’entrée en deux partiesL : la première est un sous-vecteur trié et la seconde est le sous-vecteur restant d’éléments non triés (qui est dans l’ordre d’origine). Comme le sous-vecteur trié ne peut pas être supposé être présent dans le vecteur donné, nous devons choisir le premier élément comme diviseur entre les sous-vecteurs triés et non triés. Ainsi, lorsque nous commençons à échanger les valeurs minimales avec les éléments aux positions de départ. Le vecteur sera naturellement divisé en parties triées et non triées.

Dans l’exemple suivant, nous implémentons la fonction selectionSort qui prend la référence à l’objet std::vector et effectue une modification sur place des éléments. Nous avons utilisé l’algorithme std::min_element pour trouver la valeur minimale à chaque itération ; cela permet de mieux comprendre l’algorithme pour la première fois.

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

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

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void selectionSort(vector<T> &vec) {
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::swap(*it, *std::min_element(it, vec.end()));
  }
}

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

  printVector(vec1);
  selectionSort(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éécrire la fonction selectionSort avec la deuxième boucle for qui trouve la valeur minimale pour le sous-vecteur non trié restant de chaque itération. Cette version est adaptée à l’analyse de la complexité des algorithmes. Même si l’algorithme de tri par sélection a un temps d’exécution quadratique, il peut être étonnamment efficace sur des vecteurs plus petits par rapport aux algorithmes O(nlogn), comme le tri par fusion ou le tri par tas. Notez que nous utilisons toujours une fonction STL, std::swap, qui est une opération à temps constant dans ce cas, et il est utile que l’exemple de code soit concis.

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

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

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void selectionSort(vector<T> &vec) {
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    auto min = it;

    for (auto i = it + 1; i != vec.end(); ++i) {
      if (*i < *min) min = i;
    }

    std::swap(*it, *min);
  }
}

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

  printVector(vec1);
  selectionSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Production:

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