CKTIS / C++
std::partial_sort — sortirani početak raspona
std::partial_sort odabire k najmanjih elemenata i smješta ih u sortirani početak raspona. Mijenja ulazne podatke, dok redoslijed preostalih elemenata nije specificiran.
Verzija: C++23; repository compiler flag, production runtime not attested
Sintaksa
#include <algorithm>
std::partial_sort(first, middle, last);
std::partial_sort(first, middle, last, comp);std::partial_sort, deklariran u <algorithm>, stvara sortiranih prvih k elemenata bez sortiranja cijelog raspona. Za k = middle - first smješta u [first, middle) elemente koji bi se nakon potpunog sortiranja našli na početku. Zadani je redoslijed uzlazni; preopterećenje s comp upotrebljava zadani poredak. Vraća void.
Algoritam premješta elemente unutar izvornog raspona. Redoslijed u [middle, last) nije specificiran: nemoj pretpostaviti da taj dio ostaje nepromijenjen ili postaje sortiran. Stabilnost nije zajamčena, pa elementi ekvivalentni prema usporedbi ne moraju zadržati svoj međusobni redoslijed.
Potrebni su iteratori s nasumičnim pristupom i valjani rasponi [first, middle) i [middle, last). Elementi moraju podržavati zamjenu, konstrukciju premještanjem i dodjelu premještanjem. Prije stvaranja first + k provjeri da vrijedi 0 <= k <= last - first. Komparator mora definirati strogi slabi poredak; nemoj upotrebljavati <= umjesto <.
Za N = last - first i k > 1 broj usporedbi iznosi približno N * log(k). Ovaj algoritam upotrijebi kada ti treba sortirana najbolja podskupina podataka. Uz middle == last sortira se cijeli raspon. Primjer ispisuje samo tri odabrana elementa, pa njegov ispis ne ovisi o nespecificiranom redoslijedu ostatka.
Primjeri
#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';
}
Rezultat
1 2 3
Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.