Comment trier dans la bibliothèque de modèles standard (STL) de C++

Utilisez la fonction sort() de la bibliothèque standard C++, issue de <algorithm>, pour ordonner un tableau ou un vecteur en place. Par défaut, elle trie la plage semi-ouverte de first jusqu’à, mais sans inclure, last par ordre croissant. Transmettez un comparateur pour choisir un autre ordre.

Utiliser la fonction sort() pour trier un tableau ou un vecteur en C++

std::sort accepte les itérateurs à accès aléatoire, donc il fonctionne avec les tableaux et les vecteurs. Il ne peut pas réordonner std::set ou std::map en place car ces conteneurs ne fournissent pas d’itérateurs à accès aléatoire. Ce programme complet trie à la fois un tableau et un vecteur :

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    int values[] = {8, 3, 6, 1, 5};
    std::vector<int> scores{14, 7, 22, 9};

    std::sort(std::begin(values), std::end(values));
    std::sort(scores.begin(), scores.end());

    for (int value : values) std::cout << value << ' ';
    std::cout << '\n';
    for (int score : scores) std::cout << score << ' ';
    std::cout << '\n';
    return 0;
}

std::begin et std::end fournissent la plage du tableau, tandis que le vecteur utilise ses itérateurs begin() et end(). Ce programme est fourni comme un exemple non exécuté ; sa sortie est omise jusqu’à ce qu’elle soit observée dans l’environnement d’exécution configuré. Les deux appels modifient les éléments d’origine, donc le code ultérieur les voit dans le nouvel ordre. Pour ne trier qu’une partie d’un conteneur, transmettez des itérateurs délimitant cette portion.

Trier un tableau ou un vecteur par ordre décroissant en C++

Transmettez std::greater<> comme troisième argument pour ordonner les valeurs de la plus grande à la plus petite. Incluez <functional> pour le comparateur. Par exemple, std::sort(values.begin(), values.end(), std::greater<>{}); trie un vecteur par ordre décroissant. Le comparateur modifie la règle d’ordre sans changer la plage triée.

Utiliser partial_sort() pour trier une partie d’un tableau ou d’un vecteur

Utilisez partial_sort(first, middle, last) lorsque seul un préfixe doit être ordonné. Il place les middle - first plus petits éléments dans l’ordre trié avant middle. Les éléments de middle à last n’ont aucun ordre particulier garanti. Par exemple, std::partial_sort(values.begin(), values.begin() + 3, values.end()); sélectionne les trois plus petites valeurs pour les trois premières positions.

Utiliser un comparateur personnalisé avec sort() en C++

Un comparateur vous permet d’ordonner des valeurs selon une clé telle que la longueur de la chaîne. Par exemple, std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) { return a.size() < b.size(); }); place les chaînes les plus courtes en premier. Un comparateur doit définir un ordre faible strict : il doit être cohérent et ne doit pas considérer qu’un élément se précède lui-même. Les chaînes de longueurs égales sont équivalentes dans cette comparaison, donc leur ordre relatif n’est pas spécifié. Incluez <string> avec <algorithm> lorsque vous utilisez cet exemple.

Vérifier si une plage est triée avec is_sorted()

std::is_sorted(first, last) renvoie true lorsque la plage de first jusqu’à, mais sans inclure, last est ordonnée selon la comparaison par défaut, et false sinon. Il vérifie la plage sans réorganiser ses éléments. Fournissez le même comparateur que celui utilisé pour un ordre personnalisé lorsque vous vérifiez cet ordre, comme dans std::is_sorted(words.begin(), words.end(), compare).

Complexité temporelle des algorithmes de tri

Pour std::sort, la norme spécifie O(N log N) comparaisons dans le pire des cas, où N est le nombre d’éléments dans la plage. Cela décrit comment le travail croît avec la longueur de la plage ; cela ne promet pas une implémentation de tri particulière. std::partial_sort utilise approximativement N log K comparaisons lors de la sélection et de l’ordre de K éléments parmi N, tandis que std::is_sorted effectue au plus N - 1 comparaisons. Ces limites aident à distinguer le tri complet d’une plage, le tri d’un préfixe seulement, ou la vérification d’un ordre existant.