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
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.