Docs C++ exécutables : Tri

Q: Comment trier un vecteur en C++ ?

Incluez et appelez sort(v.begin(), v.end()). Cela trie les éléments sur place en ordre croissant à l'aide de operator<. Pour trier un tableau, passez arr et arr + n (ou begin(arr) / end(arr)).

Q: Comment trier en ordre décroissant en C++ ?

Passez un comparateur qui renvoie a > b : sort(v.begin(), v.end(), [](int a, int b){ return a > b; });. Vous pouvez aussi utiliser le sort(v.begin(), v.end(), greater ()); intégré, issu de .

Q: Pourquoi mon comparateur fait-il planter std::sort en C++ ?

Votre comparateur doit définir un ordre faible strict : il doit renvoyer false lorsque les deux arguments sont égaux. Utiliser = (qui renvoient true pour des éléments égaux) enfreint cette règle et constitue un comportement indéfini : std::sort peut lire hors limites et planter. Comparez toujours avec .

Le tri n'est qu'un algorithme parmi d'autres

À la page précédente, vous avez vu que la bibliothèque standard fournit des algorithmes prêts à l'emploi qui fonctionnent sur n'importe quelle plage via les itérateurs. Le tri est celui auquel vous ferez appel le plus souvent, et il a sa propre page car il comporte quelques pièges : ordres personnalisés, stabilité et une règle qui, si vous l'enfreignez, vous donne un comportement indéfini plutôt qu'une mauvaise réponse.

La bête de somme, c'est std::sort de <algorithm>. Vous lui donnez le début et la fin d'une plage, et il réorganise les éléments sur place en ordre croissant :

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

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end());   // croissant, sur place

    for (int n : nums) cout << n << " ";  // 1 2 3 5 8 9
    cout << "\n";
    return 0;
}

Aucune copie n'est faite : le vecteur lui-même est réordonné. En interne, std::sort est généralement un introsort (un quicksort qui bascule sur un heapsort), ce qui vous donne du O(n log n) en moyenne. C'est presque toujours plus rapide et bien moins sujet aux erreurs que d'écrire votre propre tri.

Il fonctionne aussi sur les tableaux C ordinaires : vous décrivez simplement la plage avec des pointeurs :

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

int main() {
    int arr[] = {40, 10, 30, 20};
    int n = 4;

    sort(arr, arr + n);               // ou sort(begin(arr), end(arr));

    for (int x : arr) cout << x << " ";  // 10 20 30 40
    return 0;
}

Ordre personnalisé avec un comparateur

Par défaut, std::sort ordonne les éléments avec operator<. Pour trier autrement, passez un troisième argument : un comparateur qui prend deux éléments et renvoie true si le premier doit venir avant le second.

Une lambda s'y prête naturellement. L'ordre décroissant, c'est simplement a > b :

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

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;   // "a avant b" quand a est plus grand -> décroissant
    });

    for (int n : nums) cout << n << " ";  // 9 8 5 3 2 1
    cout << "\n";
    return 0;
}

Pour le cas courant d'un simple ordre décroissant sur des types intégrés, la bibliothèque fournit même un comparateur prêt à l'emploi, greater<T>() de <functional> :

#include <functional>
sort(nums.begin(), nums.end(), greater<int>());  // identique à a > b

Le comparateur est aussi le moyen de trier selon autre chose que la valeur elle-même ; par exemple, trier des chaînes par longueur plutôt qu'alphabétiquement :

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

int main() {
    vector<string> words = {"pear", "fig", "banana", "kiwi"};

    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.size() < b.size();   // les mots les plus courts d'abord
    });

    for (const string& w : words) cout << w << " ";  // fig kiwi pear banana
    cout << "\n";
    return 0;
}

Recevez les paramètres du comparateur par const& pour tout ce qui dépasse quelques octets (comme string) : copier chaque élément à chaque comparaison est du pur gaspillage.

Trier des structs par un champ

Dans les programmes réels, vous triez généralement des collections de structs selon l'un de leurs champs. Le comparateur accède simplement au champ qui vous intéresse. Ici, nous trions des personnes par âge, du plus jeune au plus âgé :

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

struct Person {
    string name;
    int age;
};

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age;
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    return 0;
}

Remarquez que Linus et Dennis ont tous deux 25 ans. Ici, ils sont ressortis dans leur ordre relatif d'origine, mais std::sort ne le garantit pas. Si l'ordre relatif des éléments égaux importe, utilisez std::stable_sort, qui le préserve (au prix d'une légère baisse de performance) :

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

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    stable_sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) { return a.age < b.age; });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    // Linus reste avant Dennis - leur ordre d'entrée est préservé
    return 0;
}

Pour départager délibérément les ex æquo - par exemple trier par âge, puis alphabétiquement par nom - comparez la clé secondaire uniquement lorsque les clés primaires sont égales. std::tie rend cela élégant :

#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
using namespace std;

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return tie(a.age, a.name) < tie(b.age, b.name);  // âge, puis nom
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";  // Dennis et Linus 25, ordre alphabétique
    return 0;
}

Le piège de l'ordre faible strict

C'est l'erreur la plus dangereuse du tri en C++, car elle ne vous donne pas une mauvaise réponse : elle vous donne un comportement indéfini, ce qui signifie souvent un plantage ou une lecture hors limites.

std::sort exige que votre comparateur définisse un ordre faible strict. La règle pratique : comp(x, x) doit valoir false pour tout élément x. Autrement dit, un élément n'est jamais « avant » lui-même. C'est exactement ce que vous donnent < et >, et exactement ce que cassent <= et >= :

// BUG : renvoie true quand a == b, ce qui viole l'ordre faible strict.
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;   // comportement indéfini - peut planter sur certaines entrées
});

Avec <=, le comparateur affirme que 5 vient avant un autre 5, ce qui est contradictoire. std::sort peut alors faire avancer un pointeur au-delà de la fin de la plage. Les petites entrées semblent parfois fonctionner, ce qui rend ce bug terrifiant : il peut passer vos tests et planter en production. Le correctif est tout simplement < :

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

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

    sort(v.begin(), v.end(), [](int a, int b) {
        return a < b;   // correct : false quand égaux
    });

    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

Un deuxième piège classique : le tri invalide tout ce qui pointe dans la plage. Les itérateurs, pointeurs et indices que vous aviez sauvegardés avant le tri ne désignent plus le même élément logique ensuite, car les éléments ont bougé. Recalculez toute position dont vous avez besoin après le tri, jamais avant.

Trier une partie d'une plage

Parfois, vous n'avez pas besoin de tout trier : vous voulez seulement les premiers éléments. Trier le vecteur entier pour lire les trois premiers est du gaspillage. std::partial_sort n'arrange que les éléments demandés et laisse le reste dans un ordre non spécifié, ce qui est moins coûteux :

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

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};

    // Place les 3 plus petits, en ordre, au début. Le reste n'est pas spécifié.
    partial_sort(v.begin(), v.begin() + 3, v.end());

    for (int i = 0; i < 3; i++) cout << v[i] << " ";  // 1 2 3
    cout << "\n";
    return 0;
}

Et si vous n'avez besoin que du seul élément qui se trouverait à une position donnée - comme la médiane - std::nth_element en fait encore moins : il place le bon élément à cet indice, avec tout ce qui est plus petit avant et tout ce qui est plus grand après, le tout en O(n) en moyenne.

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

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    size_t mid = v.size() / 2;

    nth_element(v.begin(), v.begin() + mid, v.end());

    cout << "median is " << v[mid] << "\n";  // 5
    return 0;
}

Faites appel à ceux-ci quand « entièrement trié » dépasse ce dont le problème a réellement besoin : ils font gagner un temps réel sur de grandes données.

Suivant : les templates

Avez-vous remarqué que le même std::sort a géré int, string et votre propre struct Person, et que greater<int>() pouvait tout aussi bien être greater<string>() ? Cette généralité n'a rien de magique : ce sont les templates, le mécanisme qui permet à un même morceau de code de fonctionner pour n'importe quel type que l'appelant y branche. À la page suivante, nous verrons comment écrire vos propres fonctions et classes templates, afin que votre code puisse être aussi indépendant du type que les algorithmes que vous utilisez.

Questions fréquentes

Comment trier un vecteur en C++ ?

Incluez <algorithm> et appelez sort(v.begin(), v.end()). Cela trie les éléments sur place en ordre croissant à l'aide de operator<. Pour trier un tableau, passez arr et arr + n (ou begin(arr) / end(arr)).

Comment trier en ordre décroissant en C++ ?

Passez un comparateur qui renvoie a > b : sort(v.begin(), v.end(), [](int a, int b){ return a > b; });. Vous pouvez aussi utiliser le sort(v.begin(), v.end(), greater<int>()); intégré, issu de <functional>.

Pourquoi mon comparateur fait-il planter std::sort en C++ ?

Votre comparateur doit définir un ordre faible strict : il doit renvoyer false lorsque les deux arguments sont égaux. Utiliser <= ou >= (qui renvoient true pour des éléments égaux) enfreint cette règle et constitue un comportement indéfini : std::sort peut lire hors limites et planter. Comparez toujours avec < ou >.

Concepts liés