База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C++

std::partial_sort — сортиран начален сегмент на диапазон

std::partial_sort избира k-те най-малки елемента и ги поставя в сортиран начален сегмент на диапазона. Алгоритъмът променя входните данни, а редът на останалите елементи не е указан.

Версия: C++23; repository compiler flag, production runtime not attested

Синтаксис

#include <algorithm>
std::partial_sort(first, middle, last);
std::partial_sort(first, middle, last, comp);

std::partial_sort, деклариран в <algorithm>, подрежда първите k елемента, без да сортира целия диапазон. За k = middle - first поставя в [first, middle) елементите, които биха били в началото след пълно сортиране. По подразбиране редът е възходящ; претоварването с comp използва зададения ред. Функцията връща void.

Алгоритъмът пренарежда елементите в първоначалния диапазон. Редът в [middle, last) не е указан: не приемайте, че този краен сегмент остава непроменен или става сортиран. Стабилността не е гарантирана, затова елементите, еквивалентни според сравнението, не е задължително да запазят относителния си ред.

Изискват се итератори с произволен достъп и валидни диапазони [first, middle) и [middle, last). Елементите трябва да поддържат разместване, конструиране чрез преместване и присвояване чрез преместване. Преди да образувате first + k, уверете се, че 0 <= k <= last - first. Компараторът трябва да дефинира строго слабо подреждане; не използвайте <= вместо <.

За N = last - first и k > 1 броят на сравненията е приблизително N * log(k). Използвайте този алгоритъм, когато ви е нужна сортирана най-добра подгрупа от данните. При middle == last се сортира целият диапазон. Примерът отпечатва само трите избрани елемента, така че резултатът му не зависи от неуказания ред на останалата част.

Примери

#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';
}

Резултат

1 2 3

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници