std::partial_sort

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.

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

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

[edit] Parameters

[edit] Complexity

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

[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++.

template<typename RandomIt>
constexpr //< since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last)
{
 typedef typename std::iterator_traits <RandomIt>::value_type VT;
 std::partial_sort(first, middle, last, std::less <VT>());
}

namespace impl
{
 template<typename RandomIt, typename Compare>
 constexpr //< since C++20
 void sift_down(RandomIt first, RandomIt last, const Compare& comp)
 {
 // sift down element at "first"
 const auto length = static_cast<std::size_t >(last - first);
 std::size_t current = 0;
 std::size_t next = 2;
 while (next < length)
 {
 if (comp(*(first + next), *(first + (next - 1))))
 --next;
 if (!comp(*(first + current), *(first + next)))
 return;
 std::iter_swap (first + current, first + next);
 current = next;
 next = 2 * current + 2;
 }
 --next;
 if (next < length && comp(*(first + current), *(first + next)))
 std::iter_swap (first + current, first + next);
 }
 
 template<typename RandomIt, typename Compare>
 constexpr //< since C++20
 void heap_select(RandomIt first, RandomIt middle, RandomIt last, const Compare& comp)
 {
 std::make_heap (first, middle, comp);
 for (auto i = middle; i != last; ++i)
 {
 if (comp(*i, *first))
 {
 std::iter_swap (first, i);
 sift_down(first, middle, comp);
 }
 }
 }
} // namespace impl
 
template<typename RandomIt, typename Compare>
constexpr //< since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp)
{
 impl::heap_select(first, middle, last, comp);
 std::sort_heap (first, middle, comp);
}

[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 <algorithm>
#include <array>
#include <functional>
#include <iostream>
 
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);
}

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