Tri dans la bibliothèque de modèles standard C++(STL)

1. Utilisez la fonction sort() pour trier les conteneurs Array ou STL en C++
2. Trier le tableau par ordre décroissant en C++
3. Utilisez la fonction partial_sort() pour trier une partie d’un tableau ou d’un vecteur
4. Tri défini par l’utilisateur ou personnalisé à l’aide de la fonction sort() en C++
5. Utiliser la méthode is_sorted() en C++
6. Complexité temporelle des algorithmes de tri

Dans ce didacticiel, nous allons découvrir une fonction C++ largement utilisée appelée sort(). Nous verrons également d’autres fonctions liées au tri.

Pour trier les données en C++, nous écrivons notre algorithme et l’appliquons aux données, ou nous pouvons utiliser la fonction intégrée sort() présente dans C++ STL. La fonction sort() est définie dans le fichier d’en-tête algorithm.

Cette fonction utilise l’algorithme IntroSort, un algorithme de tri hybride qui utilise trois algorithmes de tri, Quicksort, Heapsort et Insertion sort, pour minimiser le temps d’exécution.

Cette fonction trie les éléments de la plage donnée.

Syntaxe:

sort(start iterator, end iterator, compare_function)

Cela trie les éléments dans la plage définie par l’itérateur de début et l’itérateur de fin dans l'ordre croissant par défaut (c’est la fonction de comparaison par défaut).

Utilisez la fonction sort() pour trier les conteneurs Array ou STL en C++

Le tri est l’une des opérations fondamentales qui est effectuée sur les données. Nous organisons les données de manière croissante, décroissante ou définie par l’utilisateur (tri personnalisé).

Nous pouvons trier un tableau ou des conteneurs STL comme un vecteur, un ensemble, une carte, etc., en C++ en utilisant la fonction sort().

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
  int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};

  // array size
  int n = sizeof(arr) / sizeof(arr[0]);

  vector<int> v{35, 67, 11, -9, 7, -22};  // vector

  cout << "The array  after sorting is : \n";

  sort(arr, arr + n);
  sort(v.begin(), v.end());  // sorting vector

  for (int i = 0; i < n; ++i) cout << arr[i] << " ";

  cout << endl;

  cout << "The vector after sorting is : \n";
  for (int i = 0; i < v.size(); ++i) cout << v[i] << " ";
}

Production:

The array  after sorting is :
0 1 2 3 4 5 6 7 8 9
The vector after sorting is :
-22 -9 7 11 35 67

Les éléments sont classés par ordre croissant par défaut.

Trier le tableau par ordre décroissant en C++

Pour trier les tableaux ou les conteneurs présents dans C++ STL par ordre décroissant, nous devons passer un troisième paramètre appelé greater<type>() dans la fonction sort(). Cette fonction effectue une comparaison afin que les éléments à la fin soient triés par ordre décroissant.

Le Type fait référence au type de tableau ou de conteneur que nous utilisons, type int, float ou string.

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
  int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};

  // array size
  int n = sizeof(arr) / sizeof(arr[0]);

  vector<int> v{35, 67, 11, -9, 7, -22};  // vector

  cout << "The array  after sorting is : \n";

  sort(arr, arr + n, greater<int>());
  sort(v.begin(), v.end(), greater<int>());  // sorting vector

  for (int i = 0; i < n; ++i) cout << arr[i] << " ";

  cout << endl;

  cout << "The vector after sorting is : \n";
  for (int i = 0; i < v.size(); ++i) cout << v[i] << " ";
}

Production:

The array  after sorting is :
9 8 7 6 5 4 3 2 1 0
The vector after sorting is :
67 35 11 7 -9 -22

Utilisez la fonction partial_sort() pour trier une partie d’un tableau ou d’un vecteur

Nous pouvons utiliser partial_sort() pour trier juste une partie d’un tableau. Cette méthode n’est rien d’autre qu’une variante de la méthode de tri originale.

Syntaxe:

partial_sort(first, middle, last)

Il réorganise les éléments de la plage (first, last) de sorte que les éléments avant le milieu soient triés par ordre croissant et que les éléments après le milieu soient laissés sans ordre spécifique.

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
  vector<int> vr{35, 67, 11, -9, 7, -22};  // vector

  cout << "The vector after partial sorting is : \n";

  partial_sort(vr.begin(), vr.begin() + 2, vr.end());

  for (int i = 0; i < vr.size(); ++i) cout << vr[i] << " ";
}

Production:

The vector after partial sorting is :
-22 -9 67 35 11 7

Nous pouvons observer que seuls les deux premiers éléments sont triés restants sont juste présents dans un ordre aléatoire.

Tri défini par l’utilisateur ou personnalisé à l’aide de la fonction sort() en C++

Tant que nous voulons trier les données dans l’ordre croissant ou décroissant, nous pouvons utiliser cette fonction, mais il y a des moments où nous voulons que les données soient triées d’une manière définie par l’utilisateur.

Ici, nous devons écrire notre fonction de tri personnalisée, que nous transmettrons comme troisième paramètre dans la fonction sort().

#include <algorithm>
#include <iostream>
using namespace std;

bool myfunction(string x, string y) { return x.size() < y.size(); }

int main() {
  string str[] = {"a", "abc", "ba", "abcd"};
  int n = 4;

  sort(str, str + n);  // normal sort function
  cout << "Array after sorting : \n";
  for (int i = 0; i < n; ++i) cout << str[i] << " ";

  cout << endl;

  sort(str, str + n, myfunction);
  cout << "Array after user defined sorting : \n";
  for (int i = 0; i < n; ++i) cout << str[i] << " ";
}

Production:

Array after sorting :
a abc abcd ba
Array after user defined sorting :
a ba abc abcd

La première méthode de tri trie par défaut le tableau de chaînes par ordre croissant lexicographique. La deuxième méthode de tri trie les chaînes en fonction de leur longueur, c’est-à-dire la condition que nous avons mentionnée dans notre fonction de comparaison personnalisée nommée myfunction.

Utiliser la méthode is_sorted() en C++

Si nous voulons vérifier si la plage de données donnée est triée ou non, nous pouvons utiliser cette méthode.

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
  vector<int> v{35, 67, 11, -9, 7, -22};  // vector

  cout << is_sorted(v.begin(), v.end());
}

Production:

0

Puisque le vecteur n’est pas trié, nous obtenons la sortie sous la forme 0, ce qui signifie false.

Complexité temporelle des algorithmes de tri

Le sort() a une complexité temporelle de O(NlogN), où N est le nombre d’éléments sur lesquels la fonction sort() est appliquée.