Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / C++

std::partial_sort — un préfixe trié d’une plage

std::partial_sort sélectionne les k plus petits éléments et les place dans un préfixe trié de la plage. L’algorithme modifie les données d’entrée, tandis que l’ordre des autres éléments n’est pas spécifié.

Version : C++23; repository compiler flag, production runtime not attested

Syntaxe

#include <algorithm>
std::partial_sort(first, middle, last);
std::partial_sort(first, middle, last, comp);

std::partial_sort, déclaré dans <algorithm>, produit les k premiers éléments triés sans trier toute la plage. Pour k = middle - first, il place dans [first, middle) les éléments qui apparaîtraient au début après un tri complet. L’ordre par défaut est croissant ; la surcharge avec comp utilise l’ordre fourni. La fonction renvoie void.

L’algorithme réorganise les éléments de la plage d’origine. L’ordre dans [middle, last) n’est pas spécifié : ne supposez pas que ce suffixe reste inchangé ou devient trié. La stabilité n’est pas garantie ; les éléments équivalents selon le comparateur ne conservent donc pas nécessairement leur ordre relatif.

Des itérateurs à accès aléatoire et des plages valides [first, middle) et [middle, last) sont requis. Les éléments doivent pouvoir être échangés, construits par déplacement et assignés par déplacement. Avant de former first + k, vérifiez que 0 <= k <= last - first. Le comparateur doit définir un ordre strict faible ; n’utilisez pas <= à la place de <.

Pour N = last - first et k > 1, le nombre de comparaisons est approximativement N * log(k). Utilisez cet algorithme lorsque vous avez besoin d’un sous-ensemble des meilleurs éléments, trié. Avec middle == last, toute la plage est triée. L’exemple n’affiche que les trois éléments sélectionnés ; sa sortie ne dépend donc pas de l’ordre non spécifié du suffixe.

Exemples

#include <algorithm>
#include <array>
#include <iostream>

int main() {
    std::array<int, 6> values{8, 3, 7, 1, 5, 2};
    constexpr int k = 3;
    std::partial_sort(values.begin(), values.begin() + k, values.end());

    for (int i = 0; i < k; ++i) {
        if (i != 0) std::cout << ' ';
        std::cout << values[i];
    }
    std::cout << '\n';
}

Résultat

1 2 3

Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.

Sources