Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies.


Politique de confidentialité
Introduction et syntaxe de base
Pointeurs et fonctions
Programmation OO
Structures de données
La bibliothèque standard (STL)

Tri et méthodes associées en C++ - Bibliothèque STL

 

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>.

Les éléments de la séquence cible doivent être permutables, constructibles par déplacement et assignables par déplacement.

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
                

Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.