std::partial_sort - cppreference.com (original) (raw)

Rearranges elements such that the range [first, middle) contains the sorted middle − first smallest elements in the range [first, last).

The order of equal elements is not guaranteed to be preserved. The order of the remaining elements in the range [middle, last) is unspecified.

1. Elements are sorted with respect to operator<(until C++20)std::less{}(since C++20).

2. Elements are sorted with respect to comp.

2,4) Same as (1,3), but executed according to policy.

These overloads participate in overload resolution only if all following conditions are satisfied:

If any of the following conditions is satisfied, the behavior is undefined:

• [first, middle) or [middle, last) is not a valid range.

Contents

• 1 Parameters
• 2 Complexity
• 3 Exceptions
• 4 Possible implementation
• 5 Notes
  • 5.1 Algorithm
  • 5.2 Intended use
• 6 Example
• 7 Defect reports
• 8 See also

[edit] Parameters

[edit] Complexity

Given \(\scriptsize M\)M as middle - first, \(\scriptsize N\)N as last - first:

1,2) Approximately \(\scriptsize N \cdot \log(M)\)N·log(M) comparisons using operator<(until C++20)std::less{}(since C++20).

3,4) Approximately \(\scriptsize N \cdot \log(M)\)N·log(M) applications of the comparator comp.

[edit] Exceptions

The overloads with a template parameter named ExecutionPolicy report errors as follows:

• If execution of a function invoked as part of the algorithm throws an exception and ExecutionPolicy is one of the standard policies, std::terminate is called. For any other ExecutionPolicy, the behavior is implementation-defined.
• If the algorithm fails to allocate memory, std::bad_alloc is thrown.

[edit] Possible implementation

See also the implementations in libstdc++ and libc++.

[edit] Notes

[edit] Algorithm

The algorithm used is typically heap select to select the smallest elements, and heap sort to sort the selected elements in the heap in ascending order.

To select elements, a heap is used (see heap). For example, for operator< as comparison function, max-heap is used to select middle − first smallest elements.

Heap sort is used after selection to sort [first, middle) selected elements (see std::sort_heap).

[edit] Intended use

std::partial_sort algorithms are intended to be used for small constant numbers of [first, middle) selected elements.

[edit] Example

#include #include #include #include   void print(const auto& s, int middle) { for (int a : s) std::cout << a << ' '; std::cout << '\n'; if (middle > 0) { while (middle-- > 0) std::cout << "--"; std::cout << '^'; } else if (middle < 0) { for (auto i = s.size() + middle; --i; std::cout << " ") {}   for (std::cout << '^'; middle++ < 0; std::cout << "--") {} } std::cout << '\n'; };   int main() { std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3}; print(s, 0); std::partial_sort(s.begin(), s.begin() + 3, s.end()); print(s, 3); std::partial_sort(s.rbegin(), s.rbegin() + 4, s.rend()); print(s, -4); std::partial_sort(s.rbegin(), s.rbegin() + 5, s.rend(), std::greater{}); print(s, -5); }

Possible output:

5 7 4 2 8 6 1 9 0 3   0 1 2 7 8 6 5 9 4 3 ------^ 4 5 6 7 8 9 3 2 1 0 ^-------- 4 3 2 1 0 5 6 7 8 9 ^----------

[edit] Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

[edit] See also

| | partially sorts the given range making sure that it is partitioned by the given element (function template) [edit] | | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | | copies and partially sorts a range of elements (function template) [edit] | | | sorts a range of elements while preserving order between equal elements (function template) [edit] | | | sorts a range into ascending order (function template) [edit] | | | sorts the first N elements of a range(algorithm function object)[edit] |