Tri et méthodes associées en C++ - Bibliothèque STL
Le tri est l'un des algorithmes les plus élémentaires appliqués aux données. Cela signifie organiser les données d'une manière particulière, qui peut être croissante ou décroissante.
Chaque algorithme de tri a deux versions : une qui prend un objet fonction appelé opérateur de comparaison et une qui utilise operator<. Un opérateur de comparaison est un objet fonction qui peut être invoqué avec deux objets à comparer. Elle renvoie true si le premier argument est inférieur au second argument ; sinon, il renvoie faux.
Les opérateurs de comparaison doivent être transitifs. Cela signifie que pour tous les éléments a, b et c, l'opérateur de comparaison fct_comp doit conserver la relation suivante : si fct_comp(a, b) et fct_comp(b, c), alors fct_comp(a, c). Cela devrait avoir un sens : si a est ordonné avant b et b est ordonné avant c, alors a doit être ordonné avant c.
Tous les algorithmes expliqués dans ce cours se trouvent dans l'en-tête <algorithm>.
Fonction sort
Syntaxe
void sort([ep],it_debut, it_fin);
void sort([ep],it_debut, it_fin, [fct_comp]);
Arguments
- Une politique d'exécution facultative std::execution, ep (par défaut : std::execution ::seq)
- Une paire de RandomAccessIterators, it_debut et id_fin, représentant la séquence cible
- Un opérateur de comparaison facultatif, fct_comp. Il s'agit d'une fonction binaire qui accepte deux éléments de la séquence comme arguments et renvoie une valeur booléenne. La valeur renvoyée indique si l'élément passé en premier argument est considéré comme devant le second dans l'ordre spécifique strict et faible qu'il définit.
Les éléments sont comparés en utilisant operator< pour la première version, et fct_comp pour la seconde.
Les éléments équivalents ne sont pas garantis de conserver leur ordre relatif d'origine, ce qui signifie que cet algorithme est instable mais en place.
Exemple 1
#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 1 si i>j sinon 0
}
int main()
{
// Exemple sur un tableau
int t1[5] = {1,5,8,4,2};
sort(t1 , t1+5);
for_each(t1 , t1+5, afficher); // afficher le tableau
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());
for_each(v1.begin(),v1.end(), afficher); // afficher le vecteur
cout<<'\n';
/* Nous allons maintenant utiliser une fonction de comparaison définie par l'utilisateur
sur le tableau t2
*/
int t2[] = { 4,3,13,5,6,8,4,2,17 };
// Trier le tableau t2 dans l'ordre décroissant
sort(t2,t2+9,ordre_descendant);
for_each(t2,t2+9, afficher); // afficher le tableau
return 0;
}
Résultat
1 2 4 5 8
1 4 5 7 9
17 13 8 6 5 4 4 3 2
Fonction stable_sort
Trie les éléments de la plage [id_debut,it_fin] dans l'ordre croissant, comme sort , mais stable_sort 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
#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 1 si i>j sinon 0
}
int main()
{
// 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());
for_each(v1.begin(),v1.end(), afficher); // afficher le vecteur
cout<<'\n';
// Trier dans l'ordre décroissant
sort(v1.begin(),v1.end(),ordre_descendant);
for_each(v1.begin(),v1.end(), afficher); // afficher le tableau
return 0;
}
Résultat
1 4 5 7 9 9 7 5 4 1
Fonction 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.
En cas de modification, l'algorithme trie les premiers (it_milieu - it_debut) éléments de la séquence cible de façon à ce que tous les éléments de it_debut à it_milieu soient inférieurs au reste des éléments.
E, cas de copie, l'algorithme place les premiers éléments triés min(distance(it_debut, , it_fin), distance(itD_debut, itD_fin)) dans la séquence de destination, et il renvoie un itérateur pointant vers la fin de la séquence de destination.
Syntaxe
void partial_sort([ep], it_debut, it_milieu, it_fin, [fct_comp]);
RandomAccessIterator partial_sort_copy([ep], it_debut, ip_fin, itD_debut, itD_fin_end, [fct_comp]);
Arguments
- Une politique d'exécution std::execution facultative, ep (par défaut : std::execution ::seq)
- Si modification, un trio de RandomAccessIterators, it_debut, it_milieu, et it_fin, représentant la séquence cible
- Si on copie, une paire it_debut et ip_fin représentant la séquence cible et une paire itD_debut et itD_fin représentant la séquence de destination
- Un opérateur de comparaison facultatif, fct_comp
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.
Exemple 3
#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 1 si i>j sinon 0
}
int main()
{
// 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);
v1.push_back(3);
v1.push_back(14);
v1.push_back(10);
for_each(v1.begin(),v1.end(), afficher);
cout<<'\n';
vector<int>::iterator i=v1.begin();
partial_sort(v1.begin(),i+4,v1.end());
for_each(v1.begin(),v1.end(), afficher); // afficher le vecteur
cout<<'\n';
// Trier dans l'ordre décroissant
partial_sort(v1.begin(),i+4,v1.end(),ordre_descendant);
for_each(v1.begin(),v1.end(), afficher); // afficher le tableau
return 0;
}
Résultat
9 4 1 5 7 3 14 10
1 3 4 5 9 7 14 10
14 10 9 7 1 3 4 5
Fonction is_sorted
La fonction is_sorted détermine si une séquence est triée. L'algorithme renvoie true si la séquence cible est triée selon operator< ou fct_comp, s 'il est donné.
La fonction is_sorted_until renvoie un itérateur pointant sur le premier élément non trié ou it_fin si la séquence cible est triée.
Syntaxe
bool is_sorted([ep], it_debut, it_fin, [fct_comp]);
ForwardIterator is_sorted_until([ep], it_debut, it_fin, [fct_comp]);
Arguments
- Une politique d'exécution std::execution facultative, ep (par défaut : std::execution ::seq)
- Une paire de RandomAccessIterators, it_debut et it_fin, représentant la séquence cible
- Un opérateur de comparaison facultatif, fct_comp.
Exemple 4
#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 1 si i>j sinon 0
}
int main()
{
// 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);
cout<< " avant sort "<<'\n';
if(is_sorted(v1.begin(),v1.end())){
cout<< "Le vecteur est trie" << '\n';
}
else{
cout<< "Le vecteur n'est pas trie" << '\n';
}
cout<< " apres sort "<<'\n';
sort(v1.begin(),v1.end());
if(is_sorted(v1.begin(),v1.end())){
cout<< "Le vecteur est trie" << '\n';
}
else{
cout<< "Le vecteur n'est pas trie" << '\n';
}
cout<<'\n';
// exemple avec la fonction is_sorted_until
int a[] = {1,3,4,5,8,7,9,10};
int* p;
p=is_sorted_until(a,a+8);
cout<<"Il y a "<<(p - a) << " éléments triés dans la liste "
<<"et le premier élément non trié est " << *p;
return 0;
}
Résultat
avant sort
Le vecteur n'est pas trie
apres sort
Le vecteur est trie
Il y a 5 éléments triés dans la liste et le premier élément non trié est 7
Fonction nth_element
La fonction 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. Si it_nieme == it_fin, la fonction n'effectue aucune opération.
Les autres éléments sont laissés sans ordre spécifique, sauf qu'aucun des éléments qui précèdent it_nieme n'est supérieur à lui, et aucun des éléments qui le suivent n'est inférieur.
Syntaxe
bool nth_element([ep],it_debut, it_nieme, it_fin, [fct_comp]);
Arguments
- Une politique d'exécution std::execution facultative, ep (par défaut : std::execution ::seq)
- Un trio de RandomAccessIterators, it_debut, it_nieme, et it_fin représentant la séquence cible
- Un opérateur de comparaison facultatif, fct_comp.
Exemple 5
#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 1 si i>j sinon 0
}
int main()
{
// Exemple sur un vecteur
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);
for_each(v1.begin(),v1.end(), afficher);
cout<<'\n';
nth_element (v1.begin(), v1.begin()+3, v1.end());
for_each(v1.begin(),v1.end(), afficher);
return 0;
}
Résultat
6 1 5 4 7 8 14 10
1 4 5 6 7 8 14 10
