Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

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.

Zdroje