Algorithmes de tri dans la STL
Définition
Le tri est l'un des algorithmes les plus élémentaires appliqués aux données. Il signifie organiser les données d'une manière particulière, qui peut être croissante ou décroissante.
Opérateurs de comparaison
Chaque algorithme de tri a deux versions :
- Une qui utilise operator< par défaut
- Une qui prend un objet fonction appelé opérateur de comparaison (fonction binaire retournant un booléen)
Un opérateur de comparaison retourne true si le premier argument est inférieur au second, false sinon.
Propriété importante
Les opérateurs de comparaison doivent être transitifs. Cela signifie que pour tous les éléments a, b et c :
si fct_comp(a, b) et fct_comp(b, c), alors fct_comp(a, c).
Si a est ordonné avant b et b avant c, alors a doit être ordonné avant c.
Prérequis
Les éléments de la séquence cible doivent être permutables, constructibles par déplacement et assignables par déplacement.
Tous les algorithmes expliqués dans ce cours se trouvent dans l'en-tête <algorithm>.
1. Algorithme sort
Description
L'algorithme sort trie les éléments d'une séquence dans l'ordre croissant (par défaut) ou selon un opérateur de comparaison fourni.
Caractéristiques
- Complexité : O(N log N) en moyenne
- Stabilité : Non stable (les éléments équivalents peuvent perdre leur ordre relatif)
- En place : Oui
Syntaxe
void sort([ep], it_debut, it_fin);
void sort([ep], it_debut, it_fin, [fct_comp]);Arguments
- ep (optionnel) : politique d'exécution (std::execution::seq par défaut)
- it_debut, it_fin : une paire de RandomAccessIterators représentant la séquence cible
- fct_comp (optionnel) : opérateur de comparaison binaire
Exemple 1 : Utilisation de sort
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void afficher(int a) {
cout << a << " ";
}
bool ordre_descendant(int i, int j) {
return i > j; // retourne true si i > j (ordre décroissant)
}
int main() {
// Exemple sur un tableau
int t1[5] = {1, 5, 8, 4, 2};
sort(t1, t1 + 5);
cout << "Tableau trié : ";
for_each(t1, t1 + 5, afficher);
cout << '\n';
// Exemple sur un vecteur
vector<int> v1;
v1.push_back(9);
v1.push_back(4);
v1.push_back(1);
v1.push_back(5);
v1.push_back(7);
sort(v1.begin(), v1.end());
cout << "Vecteur trié : ";
for_each(v1.begin(), v1.end(), afficher);
cout << '\n';
// Tri avec fonction de comparaison personnalisée (ordre décroissant)
int t2[] = {4, 3, 13, 5, 6, 8, 4, 2, 17};
sort(t2, t2 + 9, ordre_descendant);
cout << "Tableau trié décroissant : ";
for_each(t2, t2 + 9, afficher);
cout << '\n';
return 0;
}Résultat
Tableau trié : 1 2 4 5 8 Vecteur trié : 1 4 5 7 9 Tableau trié décroissant : 17 13 8 6 5 4 4 3 2
2. Algorithme stable_sort
Description
L'algorithme stable_sort trie les éléments comme sort, mais préserve l'ordre relatif des éléments avec des valeurs équivalentes (les éléments égaux conservent leur ordre d'origine).
Syntaxe
void stable_sort([ep], it_debut, it_fin);
void stable_sort([ep], it_debut, it_fin, [fct_comp]);Exemple 2 : Utilisation de stable_sort
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void afficher(int a) {
cout << a << " ";
}
bool ordre_descendant(int i, int j) {
return i > j;
}
int main() {
vector<int> v1;
v1.push_back(9);
v1.push_back(4);
v1.push_back(1);
v1.push_back(5);
v1.push_back(7);
// Tri normal (ordre croissant)
stable_sort(v1.begin(), v1.end());
cout << "Vecteur trié (stable) : ";
for_each(v1.begin(), v1.end(), afficher);
cout << '\n';
// Tri décroissant avec stable_sort
stable_sort(v1.begin(), v1.end(), ordre_descendant);
cout << "Vecteur trié décroissant (stable) : ";
for_each(v1.begin(), v1.end(), afficher);
cout << '\n';
return 0;
}Résultat
Vecteur trié (stable) : 1 4 5 7 9 Vecteur trié décroissant (stable) : 9 7 5 4 1
3. Algorithme partial_sort
Description
L'algorithme partial_sort réorganise les éléments de la plage [it_debut, it_fin) de telle sorte que les éléments avant it_milieu soient les plus petits éléments de toute la séquence et soient triés par ordre croissant, tandis que les autres éléments sont laissés sans ordre spécifique.
Un tri partiel vous permet de trouver les premiers éléments d'une séquence triée sans avoir à trier la séquence entière. Par exemple, si vous avez la séquence D C B A, vous pouvez effectuer un tri partiel des deux premiers éléments et obtenir le résultat A B D C. Les deux premiers éléments sont les mêmes que si vous aviez trié la séquence entière, mais les autres éléments ne le sont pas.
Syntaxe
void partial_sort([ep], it_debut, it_milieu, it_fin, [fct_comp]);Exemple 3 : Utilisation de partial_sort
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void afficher(int a) {
cout << a << " ";
}
bool ordre_descendant(int i, int j) {
return i > j;
}
int main() {
vector<int> v1;
v1.push_back(9);
v1.push_back(4);
v1.push_back(1);
v1.push_back(5);
v1.push_back(7);
v1.push_back(3);
v1.push_back(14);
v1.push_back(10);
cout << "Vecteur original : ";
for_each(v1.begin(), v1.end(), afficher);
cout << '\n';
vector<int>::iterator i = v1.begin();
// Trier partiellement les 4 premiers éléments
partial_sort(v1.begin(), i + 4, v1.end());
cout << "Après partial_sort des 4 premiers : ";
for_each(v1.begin(), v1.end(), afficher);
cout << '\n';
// Trier partiellement les 4 premiers en ordre décroissant
partial_sort(v1.begin(), i + 4, v1.end(), ordre_descendant);
cout << "Après partial_sort décroissant des 4 premiers : ";
for_each(v1.begin(), v1.end(), afficher);
cout << '\n';
return 0;
}Résultat
Vecteur original : 9 4 1 5 7 3 14 10 Après partial_sort des 4 premiers : 1 3 4 5 9 7 14 10 Après partial_sort décroissant des 4 premiers : 14 10 9 7 1 3 4 5
Explication :
- Premier partial_sort : les 4 premiers éléments sont les plus petits de toute la séquence (1,3,4,5) et sont triés.
- Les éléments restants (9,7,14,10) ne sont pas triés.
- Deuxième partial_sort (décroissant) : les 4 premiers sont les plus grands (14,10,9,7) et sont triés.
4. Algorithmes is_sorted et is_sorted_until
Description
L'algorithme is_sorted détermine si une séquence est triée.
L'algorithme is_sorted_until renvoie un itérateur pointant sur le premier élément non trié.
Syntaxe
bool is_sorted([ep], it_debut, it_fin, [fct_comp]);
ForwardIterator is_sorted_until([ep], it_debut, it_fin, [fct_comp]);Exemple 4 : Vérification du tri
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void afficher(int a) {
cout << a << " ";
}
int main() {
vector<int> v1;
v1.push_back(9);
v1.push_back(4);
v1.push_back(1);
v1.push_back(5);
v1.push_back(7);
// Test avant tri
cout << "Avant sort :\n";
if (is_sorted(v1.begin(), v1.end()))
cout << "Le vecteur est trié\n";
else
cout << "Le vecteur n'est pas trié\n";
// Tri
sort(v1.begin(), v1.end());
// Test après tri
cout << "Après sort :\n";
if (is_sorted(v1.begin(), v1.end()))
cout << "Le vecteur est trié\n";
else
cout << "Le vecteur n'est pas trié\n";
cout << '\n';
// Exemple avec is_sorted_until
int a[] = {1, 3, 4, 5, 8, 7, 9, 10};
int* p = is_sorted_until(a, a + 8);
cout << "Il y a " << (p - a) << " éléments triés dans la liste\n";
cout << "Le premier élément non trié est " << *p << '\n';
return 0;
}Résultat
Avant sort : Le vecteur n'est pas trié Après sort : Le vecteur est trié Il y a 5 éléments triés dans la liste Le premier élément non trié est 7
Explication pour is_sorted_until :
- La séquence {1,3,4,5,8,7,9,10} est triée jusqu'à l'indice 4 inclus (valeurs 1,3,4,5,8).
- À l'indice 5, on trouve 7 qui est inférieur à 8, donc la séquence n'est plus triée.
is_sorted_untilretourne un itérateur vers cet élément (7).
5. Algorithme nth_element
Description
L'algorithme nth_element place un élément particulier d'une séquence dans sa position triée correcte.
Cet algorithme de tri partiel modifie la séquence cible de la manière suivante :
- L'élément à la position pointée par it_nieme se trouve à cette position comme si toute la séquence était triée.
- Tous les éléments de it_debut à it_nieme-1 seront inférieurs à it_nieme.
- Tous les éléments après it_nieme seront supérieurs à it_nieme.
- Les autres éléments sont laissés sans ordre spécifique.
Si it_nieme == it_fin, la fonction n'effectue aucune opération.
Syntaxe
void nth_element([ep], it_debut, it_nieme, it_fin, [fct_comp]);Exemple 5 : Utilisation de nth_element
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void afficher(int a) {
cout << a << " ";
}
int main() {
vector<int> v1;
v1.push_back(6);
v1.push_back(1);
v1.push_back(5);
v1.push_back(4);
v1.push_back(7);
v1.push_back(8);
v1.push_back(14);
v1.push_back(10);
cout << "Vecteur original : ";
for_each(v1.begin(), v1.end(), afficher);
cout << '\n';
// Place le 4ème élément (index 3) à sa position triée correcte
nth_element(v1.begin(), v1.begin() + 3, v1.end());
cout << "Après nth_element (4ème élément) : ";
for_each(v1.begin(), v1.end(), afficher);
cout << '\n';
return 0;
}Résultat
Vecteur original : 6 1 5 4 7 8 14 10 Après nth_element (4ème élément) : 1 4 5 6 7 8 14 10
Explication :
- Le vecteur original est {6,1,5,4,7,8,14,10}
- Si on trie complètement, on obtiendrait {1,4,5,6,7,8,10,14}
- Le 4ème élément (index 3) serait 6
- Après
nth_element, l'élément à l'index 3 est bien 6 - Tous les éléments avant l'index 3 (1,4,5) sont inférieurs à 6
- Tous les éléments après (7,8,14,10) sont supérieurs à 6, mais non triés
Récapitulatif des algorithmes de tri
| Algorithme | Description | Stable | Complexité |
|---|---|---|---|
| sort | Trie toute la séquence | Non | O(N log N) |
| stable_sort | Trie toute la séquence en préservant l'ordre des équivalents | Oui | O(N log N) |
| partial_sort | Trie les premiers éléments (les plus petits) | Non | O(N log M) avec M = distance(it_debut, it_milieu) |
| nth_element | Place un élément à sa position triée correcte | Non | O(N) |
| is_sorted | Vérifie si la séquence est triée | - | O(N) |
| is_sorted_until | Trouve le premier élément non trié | - | O(N) |
Exercice pratique
Choisir le bon algorithme de tri
Pour chaque situation, indiquez quel algorithme de tri serait le plus approprié :
- Vous avez une liste de 10 millions d'entiers et vous voulez les trier complètement.
- Vous voulez trouver les 100 plus petits éléments d'une liste de 1 million d'éléments, sans avoir besoin de trier le reste.
- Vous voulez vérifier rapidement si une liste est déjà triée avant d'effectuer d'autres opérations.
- Vous avez une liste avec des éléments en double et vous voulez conserver l'ordre relatif des éléments égaux.
- Vous voulez connaître la médiane d'une liste (l'élément du milieu).
Solution
- 10 millions d'entiers à trier complètement : sort (le plus rapide pour un tri complet)
- Trouver les 100 plus petits éléments : partial_sort (tri uniquement les 100 premiers, plus efficace qu'un tri complet)
- Vérifier si une liste est triée : is_sorted (simple test O(N))
- Conserver l'ordre relatif des éléments égaux : stable_sort (seul algorithme stable parmi ceux-ci)
- Trouver la médiane : nth_element (place l'élément du milieu à sa position triée sans trier tout le reste)
Points clés à retenir
- Les algorithmes de tri sont dans l'en-tête <algorithm>.
- sort : tri complet, rapide mais non stable.
- stable_sort : tri complet en préservant l'ordre des éléments équivalents.
- partial_sort : tri partiel des premiers éléments (les plus petits).
- nth_element : place un élément à sa position triée (utile pour médianes, quartiles).
- is_sorted : vérifie si une séquence est triée.
- is_sorted_until : trouve le premier élément non trié.
- On peut fournir une fonction de comparaison personnalisée pour changer l'ordre de tri.
- La fonction de comparaison doit être transitive et définir un ordre strict faible.
- Choisissez l'algorithme en fonction de vos besoins : tri complet, tri partiel, stabilité, etc.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.