Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

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.

Izvori