0Pricing
C++ Academy · Leçon

Tri et partitionnement : sort, stable_partition

Trier et partitionner des conteneurs avec std::sort et std::stable_partition

Tri et partitionnement : sort, stable_partition est une leçon C++ Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C++ Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C++ Academy comprend 4 leçons au total.

std::sort

L’algorithme de tri polyvalent. O(N log N) en moyenne. Sur place. Sa stabilité n’est pas garantie.

#include <algorithm>
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
std::sort(v.begin(), v.end());
// v is sorted ascending

Comparateur personnalisé

Transmettez un comparateur (fonction lambda ou foncteur) pour trier selon d’autres critères.

std::sort(v.begin(), v.end(),
    [](int a, int b) { return a > b; });   // descending

Tri de types personnalisés

Fournissez un comparateur qui compare des membres précis, ou définissez operator< pour le type.

struct Person { std::string name; int age; };
std::vector<Person> people;
std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) { return a.age < b.age; });

std::stable_sort

Comme sort, mais conserve l’ordre relatif des éléments égaux. Légèrement plus lent, avec généralement une mémoire supplémentaire en O(N log2 N).

std::partial_sort

Place les k plus petits éléments en tête, dans l’ordre. Les éléments restants sont dans un ordre non spécifié. Plus rapide qu’un tri complet lorsque seuls les k premiers éléments vous intéressent.

std::vector<int> v = {5, 2, 8, 1, 9, 3};
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// first 3 elements are the smallest, sorted

std::nth_element

Partitionne la plage afin que l’élément à la position nth soit celui qu’il occuperait dans une plage entièrement triée. Tout ce qui précède est ≤ à l’élément nth ; tout ce qui suit est ≥ à celui-ci. O(N) en moyenne.

std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] is the 3rd smallest element

std::is_sorted

Vérifie si une plage est déjà triée.

if (std::is_sorted(v.begin(), v.end())) {
    std::cout << "already sorted";
}

std::partition

Réordonne une plage afin que les éléments satisfaisant un prédicat apparaissent en premier. Renvoie l’itérateur vers le premier élément qui ne le satisfait pas. Non stable.

std::vector<int> v = {1, 2, 3, 4, 5};
auto pivot = std::partition(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });
// even numbers come first, then odd

std::stable_partition

Comme partition, mais conserve l’ordre relatif au sein de chaque groupe.

Tri selon plusieurs clés

Utilisez un comparateur qui compare la clé principale, puis la clé secondaire si la première est égale.

std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) {
        if (a.age != b.age) return a.age < b.age;
        return a.name < b.name;
    });

Recherche binaire dans des plages triées

Une fois la plage triée, utilisez std::lower_bound, std::upper_bound et std::binary_search pour effectuer des recherches en O(log N).

Vérification rapide

Quel algorithme conserve l’ordre relatif des éléments égaux après le tri ?

Récapitulatif

Utilisez std::sort pour un tri général, std::stable_sort lorsque l’ordre des éléments égaux compte, std::partial_sort pour les k premiers éléments, std::nth_element pour sélectionner et std::partition/std::stable_partition pour regrouper.

Questions Fréquemment Posées

La leçon « Tri et partitionnement : sort, stable_partition » est-elle gratuite ?

Oui — le texte complet de « Tri et partitionnement : sort, stable_partition » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C++ Academy, passe à CoddyKit PRO. Le cours C++ Academy comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Tri et partitionnement : sort, stable_partition » ?

Trier et partitionner des conteneurs avec std::sort et std::stable_partition Tu pratiques C++ Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer C++ Academy ?

Aucune expérience préalable n'est requise. C++ Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.

Combien de temps prend la leçon « Tri et partitionnement : sort, stable_partition » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon C++ Academy ?

Oui. Chaque leçon C++ Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Algorithmes non modificateurs : find, count, all_of
  2. Algorithmes modificateurs : transform, copy_if, replace
  3. Tri et partitionnement : sort, stable_partition
  4. Algorithmes numériques : accumulate, reduce, transform_reduce
← Retour à C++ Academy