Tris

Tris

L’ensemble des opérations de tri et des opérations associées possèdent deux versions. La première compare les éléments à l’aide de l’opérateur surchargé <, et la seconde utilise un objet de comparaison externe. Cela implique que toutes les séquences soient triées en ordre croissant. Il est possible de trier une séquence en ordre inverse à l’aide d’un prédicat externe.
La STL fournit un ensemble de fonctions de tri qui ordonnent les séquences d’éléments selon divers critères. Ces opérations sont traitées dans les sections qui suivent.

sort et stable_sort

Les algorithmes de tri sont déclarés comme suit dans l’en-tête <algorithm> :

template <class RandomAccessIterator> 
void sort(RandomAccessIterator premier, RandomAccessIterator dernier); 

template <class RandomAccessIterator, class Compare> 
void sort(RandomAccessIterator premier, RandomAccessIterator dernier, 
    Compare c); 

template <class RandomAccessIterator> 
void stable_sort(RandomAccessIterator premier, RandomAccessIterator dernier); 

template <class RandomAccessIterator, class Compare> 
void stable_sort(RandomAccessIterator premier, RandomAccessIterator dernier, 
    Compare c);

Les algorithmes sort et stable_sort s’utilisent de la même manière et permettent de trier complètement la séquence qui leur est spécifiée à l’aide des deux itérateurs premier et dernier. Ces deux algorithmes effectuent un tri par ordre croissant en utilisant l’opérateur d’infériorité du type des éléments de la séquence à trier. Cependant, il est également possible d’utiliser un autre critère, en spécifiant un foncteur binaire en troisième argument. Ce foncteur doit être capable de comparer deux éléments de la séquence à trier et d’indiquer si le premier est ou non le plus petit au sens de la relation d’ordre qu’il utilise.

Code 9.14 : algorithme de tri

#include <iostream> 
#include <algorithm> 

using namespace std; 

int main() 
{ 
   int tab[10] = {2, 3, 7, 5, 4, 1, 8, 0, 9, 6}; 
   cout << "On trie le tableau {2, 3, 7, 5, 4, 1, 8, 0, 9, 6} :" << endl; 
   sort(tab, tab+10); 
   //On affiche le résultat : 
   int i; 
   for (i=0; i<10; i++) 
      cout << tab[i] << " "; 
   cout << endl; 
}

L’algorithme stable_sort() trie également les éléments d’une séquence. Lorsque deux éléments – ou davantage – sont égaux, leur ordre relatif est préservé.

partial_sort et partial_sort_copy

Dans certaines situations, il n’est pas nécessaire d’effectuer un tri total des éléments. En effet, le tri des premiers éléments d’une séquence seulement ou bien seule la détermination du n-ième élément d’un ensemble peuvent être désirés.
À cet effet, la bibliothèque standard fournit les algorithmes suivants :

template <class RandomAccessIterator> 
void partial_sort(RandomAccessIterator premier, 
    RandomAccessIterator pivot, RandomAccessIterator dernier); 

template <class InputIterator, class RandomAccessIterator> 
RandomAccessIterator partial_sort_copy( 
    InputIterator premier, InputIterator dernier, 
    RandomAccessIterator debut_resultat, RandomAccessIterator fin_resultat); 

template <class RandomAccessIterator, class Compare> 
void partial_sort( 
    RandomAccessIterator premier, RandomAccessIterator fin_tri, 
    RandomAccessIterator dernier, Compare c); 

template <class InputIterator, class RandomAccessIterator, 
    class Compare> 
RandomAccessIterator partial_sort_copy( 
    InputIterator premier, InputIterator dernier, 
    RandomAccessIterator debut_resultat, RandomAccessIterator fin_resultat, 
    Compare c); 

template <class RandomAccessIterator> 
void nth_element(RandomAccessIterator premier, RandomAccessIterator position, 
    RandomAccessIterator dernier); 

template <class RandomAccessIterator, class Compare> 
void nth_element(RandomAccessIterator premier, RandomAccessIterator position, 
    RandomAccessIterator dernier,  Compare c);

L’algorithme partial_sort permet de n’effectuer qu’un tri partiel d’une séquence. Cet algorithme existe en deux versions. La première version prend en argument l’itérateur de début de la séquence, l’itérateur de la position du dernier élément de la séquence qui sera triée à la fin de l’exécution de l’algorithme, et l’itérateur de fin de la séquence.

La seconde version, nommée partial_sort_copy, permet de copier le résultat du tri partiel à un autre emplacement que celui de la séquence initiale. Cette version de l’algorithme de tri partiel prend alors deux paires d’itérateurs en argument, la première spécifiant la séquence sur laquelle l’algorithme doit travailler et la seconde l’emplacement destination dans lequel le résultat doit être stocké.

Enfin, comme pour tous les autres algorithmes, il est possible de spécifier un autre opérateur de comparaison que l’opérateur d’infériorité par défaut en fournissant un foncteur binaire en dernier argument.

Code 9.15 : algorithme de tri partiel

#include <iostream> 
#include <algorithm> 

using namespace std; 

int main() 
{ 
   int tab[10] = {2, 3, 7, 5, 4, 1, 8, 0, 9, 6}; 
   cout << "Le tableau {2, 3, 7, 5, 4, 1, 8, 0, 9, 6} devient :" << endl; 
   // Trie les 5 premiers éléments du tableau : 
   partial_sort(tab, tab+5, tab+10); 
   //On affiche le résultat : 
   int i; 
   for (i=0; i<10; i++) 
      cout << tab[i] << " "; 
   cout << endl; 
}

nth_element

L’algorithme nth_element permet quant à lui de calculer la valeur d’un élément de rang donné dans le conteneur si celui-ci était complètement trié. Cet algorithme prend en argument l’itérateur de début de la séquence à traiter, un itérateur sur l’emplacement de l’élément qui sera placé à sa position à la fin de l’opération de tri partiel et l’itérateur de fin de la séquence. Il est également possible, comme pour les autres algorithmes, de spécifier un foncteur à utiliser pour tester l’infériorité des éléments de la séquence.
À l’issue de l’appel, le n-ième élément de la séquence sera le même élément que celui qui se trouverait à cette position si la séquence était complètement triée selon la relation d’ordre induite par l’opérateur d’infériorité ou par le foncteur fourni en argument.

Code 9.16 : algorithme de positionnement du n-ième élément

#include <iostream> 
#include <algorithm> 

using namespace std; 

int main() 
{ 
   int tab[10] = {2, 3, 9, 6, 7, 5, 4, 0, 1, 8}; 
   cout << "Tableau initial : {2, 3, 9, 6, 7, 5, 4, 0, 1, 8}" << endl; 
   // Trie tous les éléments un à un : 
   int i; 
   for (i=0; i<10; i++) 
   { 
      nth_element(tab, tab+i, tab+10); 
      cout << "L’élément " << i << 
         " a pour valeur " << tab[i] << endl; 
   } 
}

min_element et max_element

Enfin, et bien que ces algorithmes ne fassent pas à proprement parler des opérations de tri, la bibliothèque standard fournit deux algorithmes permettant d’obtenir le plus petit et le plus grand des éléments d’une séquence. Ces algorithmes sont déclarés de la manière suivante dans l’en-tête <algorithm> :

template <class ForwardIterator> 
ForwardIterator min_element(ForwardIterator premier, ForwardIterator dernier); 

template <class ForwardIterator, class Compare> 
ForwardIterator min_element(ForwardIterator premier, ForwardIterator dernier, 
    Compare c); 

template <class ForwardIterator> 
ForwardIterator max_element(ForwardIterator premier, ForwardIterator dernier); 

template <class ForwardIterator, class Compare> 
ForwardIterator max_element(ForwardIterator premier, ForwardIterator dernier, 
    Compare c);

Ces deux algorithmes prennent en argument deux itérateurs permettant de définir la séquence des éléments dont le minimum et le maximum doivent être déterminés. Ils retournent un itérateur référençant respectivement le plus petit et le plus grand des éléments de cette séquence.

Code 9.17 : algorithmes de détermination du maximum et du minimum

#include <iostream> 
#include <algorithm> 

using namespace std; 

int main() 
{ 
   int tab[10] = {5, 2, 4, 6, 3, 7, 9, 1, 0, 8}; 
   cout << "Dans le tableau : {5, 2, 4, 6, 3, 7, 9, 1, 0, 8}" << endl; 
   //On affiche le minimum et le maximum : 
   cout << "Le minimum est: "; 
   cout << *min_element(tab, tab+10) << endl; 
   cout << "Le maximum est: "; 
   cout << *max_element(tab, tab+10) << endl; 
}

Le texte original de cette fiche pratique est extrait de
«Tout sur le C++» (Christine EBERHARDT, Collection
CommentCaMarche.net, Dunod, 2009)