KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C++

std::partial_sort — een gesorteerd begin van een bereik

std::partial_sort selecteert de k kleinste elementen en plaatst ze in een gesorteerd begin van het bereik. De invoer wordt gewijzigd; de volgorde van de overige elementen is niet gespecificeerd.

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

Syntax

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

std::partial_sort, gedeclareerd in <algorithm>, levert de eerste k elementen gesorteerd op zonder het hele bereik te sorteren. Voor k = middle - first plaatst het in [first, middle) de elementen die bij een volledige sortering vooraan zouden staan. De standaardvolgorde is oplopend; de overload met comp gebruikt de opgegeven volgorde. De functie retourneert void.

Het algoritme herschikt elementen in het oorspronkelijke bereik. De volgorde in [middle, last) is niet gespecificeerd: ga er niet van uit dat dit achterste deel ongewijzigd blijft of gesorteerd raakt. Stabiliteit is niet gegarandeerd, dus elementen die volgens de vergelijking equivalent zijn, hoeven hun onderlinge volgorde niet te behouden.

Iteratoren met willekeurige toegang en geldige bereiken [first, middle) en [middle, last) zijn vereist. Elementen moeten verwisselbaar zijn en move-constructie en move-toewijzing ondersteunen. Controleer vóór het vormen van first + k dat 0 <= k <= last - first. De comparator moet een strikte zwakke ordening definiëren; gebruik geen <= in plaats van <.

Voor N = last - first en k > 1 bedraagt het aantal vergelijkingen ongeveer N * log(k). Gebruik dit algoritme wanneer je een gesorteerde beste deelverzameling van de gegevens nodig hebt. Bij middle == last wordt het hele bereik gesorteerd. Het voorbeeld toont alleen de drie geselecteerde elementen, dus de uitvoer hangt niet af van de niet-gespecificeerde volgorde van het achterste deel.

Voorbeelden

#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';
}

Resultaat

1 2 3

De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.

Bronnen