Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::partial_sort — posortowany początek zakresu

std::partial_sort wybiera najmniejsze k elementów i umieszcza je w posortowanym początku zakresu. Modyfikuje dane wejściowe, a kolejność pozostałych elementów jest nieokreślona.

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

Składnia

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

std::partial_sort z nagłówka <algorithm> służy do uzyskania posortowanych pierwszych k elementów bez sortowania całego zakresu. Dla k = middle - first umieszcza w [first, middle) elementy, które znalazłyby się na początku po pełnym sortowaniu. Domyślnie porządkuje rosnąco; przeciążenie z comp stosuje wskazany porządek. Zwraca void.

Algorytm przestawia elementy w oryginalnym zakresie. Kolejność w [middle, last) jest nieokreślona: nie zakładaj, że ten fragment pozostanie niezmieniony lub będzie posortowany. Nie ma gwarancji stabilności, czyli zachowania względnej kolejności elementów równoważnych według porównania.

Wymagane są iteratory dostępu swobodnego oraz poprawne zakresy [first, middle) i [middle, last). Elementy muszą obsługiwać zamianę, konstruowanie przez przeniesienie i przypisanie przez przeniesienie. Przed utworzeniem first + k zapewnij 0 <= k <= last - first. Komparator musi definiować ścisły słaby porządek; nie używaj <= zamiast <.

Dla N = last - first i k > 1 liczba porównań wynosi w przybliżeniu N * log(k). Użyj tego algorytmu, gdy potrzebujesz posortowanej najlepszej części danych. Przy middle == last posortowany zostaje cały zakres. Przykład wypisuje tylko trzy wybrane elementy, więc jego wynik nie zależy od nieokreślonej kolejności reszty.

Przykłady

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

Wynik

1 2 3

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła