CKTIS / C++
std::partial_sort — zoradený začiatok rozsahu
std::partial_sort vyberie k najmenších prvkov a umiestni ich do zoradeného začiatku rozsahu. Mení vstupné údaje, pričom poradie ostatných prvkov nie je špecifikované.
Verzia: 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 deklarované v <algorithm> vytvorí zoradených prvých k prvkov bez zoradenia celého rozsahu. Pre k = middle - first umiestni do [first, middle) prvky, ktoré by sa po úplnom zoradení nachádzali na začiatku. Predvolené poradie je vzostupné; preťaženie s comp použije zadané usporiadanie. Vracia void.
Algoritmus preskupuje prvky v pôvodnom rozsahu. Poradie v [middle, last) nie je špecifikované: nepredpokladajte, že táto časť zostane nezmenená alebo bude zoradená. Stabilita nie je zaručená, takže prvky ekvivalentné podľa porovnávania nemusia zachovať svoje vzájomné poradie.
Vyžadujú sa iterátory s náhodným prístupom a platné rozsahy [first, middle) a [middle, last). Prvky musia podporovať výmenu, konštrukciu presunom a priradenie presunom. Pred vytvorením first + k zabezpečte, aby platilo 0 <= k <= last - first. Komparátor musí definovať striktné slabé usporiadanie; nepoužívajte <= namiesto <.
Pre N = last - first a k > 1 je počet porovnaní približne N * log(k). Tento algoritmus použite, keď potrebujete zoradenú najlepšiu podmnožinu údajov. Pri middle == last sa zoradí celý rozsah. Príklad vypisuje iba tri vybrané prvky, takže jeho výstup nezávisí od nešpecifikovaného poradia zvyšku.
Príklady
#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';
}
Výsledok
1 2 3
Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.