Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C++

std::partial_sort — urejen začetek območja

std::partial_sort izbere k najmanjših elementov in jih postavi v urejen začetek območja. Vhodne podatke spremeni, vrstni red preostalih elementov pa ni določen.

Različica: 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 v <algorithm>, ustvari urejenih prvih k elementov, ne da bi uredil celotno območje. Za k = middle - first v [first, middle) postavi elemente, ki bi bili po popolnem urejanju na začetku. Privzeti vrstni red je naraščajoč; preobremenitev z comp uporabi podani vrstni red. Vrne void.

Algoritem prerazporedi elemente v izvirnem območju. Vrstni red v [middle, last) ni določen: ne predpostavljaj, da ta del ostane nespremenjen ali se uredi. Stabilnost ni zagotovljena, zato elementi, ki so glede na primerjavo enakovredni, ne ohranijo nujno svojega medsebojnega vrstnega reda.

Potrebni so iteratorji z naključnim dostopom in veljavni območji [first, middle) ter [middle, last). Elementi morajo podpirati zamenjavo, konstrukcijo s premikom in prirejanje s premikom. Pred tvorjenjem first + k zagotovi, da velja 0 <= k <= last - first. Primerjalnik mora določati strogo šibko urejenost; ne uporabljaj <= namesto <.

Za N = last - first in k > 1 je število primerjav približno N * log(k). Ta algoritem uporabi, ko potrebuješ urejeno najboljšo podmnožico podatkov. Pri middle == last se uredi celotno območje. Primer izpiše samo tri izbrane elemente, zato njegov izpis ni odvisen od nedoločenega vrstnega reda preostalega dela.

Primeri

#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

Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.

Viri