WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

std::partial_sort — ein sortierter Anfang eines Bereichs

std::partial_sort wählt die k kleinsten Elemente aus und ordnet sie am Anfang des Bereichs. Der Algorithmus verändert die Eingabedaten; die Reihenfolge der übrigen Elemente ist nicht festgelegt.

Version: 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 aus <algorithm> erzeugt die ersten k Elemente in sortierter Reihenfolge, ohne den gesamten Bereich zu sortieren. Für k = middle - first platziert es in [first, middle) die Elemente, die bei einer vollständigen Sortierung am Anfang stehen würden. Standardmäßig wird aufsteigend sortiert; die Überladung mit comp verwendet die angegebene Ordnung. Die Funktion gibt void zurück.

Der Algorithmus ordnet die Elemente im ursprünglichen Bereich um. Die Reihenfolge in [middle, last) ist nicht festgelegt: Gehe nicht davon aus, dass dieser Rest unverändert bleibt oder sortiert wird. Stabilität ist nicht garantiert; Elemente, die gemäß dem Vergleich gleichwertig sind, müssen ihre relative Reihenfolge nicht beibehalten.

Erforderlich sind Iteratoren mit wahlfreiem Zugriff sowie gültige Bereiche [first, middle) und [middle, last). Die Elemente müssen vertauschbar sowie per Move konstruierbar und zuweisbar sein. Stelle vor der Bildung von first + k sicher, dass 0 <= k <= last - first gilt. Der Komparator muss eine strikte schwache Ordnung definieren; verwende nicht <= anstelle von <.

Für N = last - first und k > 1 beträgt die Anzahl der Vergleiche ungefähr N * log(k). Verwende den Algorithmus, wenn du eine sortierte beste Teilmenge der Daten benötigst. Bei middle == last wird der gesamte Bereich sortiert. Das Beispiel gibt nur die drei ausgewählten Elemente aus; seine Ausgabe hängt daher nicht von der unbestimmten Reihenfolge des Rests ab.

Beispiele

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

Ergebnis

1 2 3

Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.

Quellen