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.