Rearranges elements such that the range[first, middle) contains the sortedmiddle − 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 avalid range.

[edit]Parameters

[edit]Complexity

Given\(\scriptsize M\)M asmiddle- first,\(\scriptsize N\)N aslast- first:

[edit]Exceptions

The overloads with a template parameter namedExecutionPolicy report errors as follows:

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

[edit]Possible implementation

See also the implementations inlibstdc++ andlibc++.

template<typename RandomIt>constexpr//< since C++20void partial_sort(RandomIt first, RandomIt middle, RandomIt last){typedeftypenamestd::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++20void sift_down(RandomIt first, RandomIt last,const Compare& comp){// sift down element at “first”constauto 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++20void 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++20void 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 typicallyheap select to select the smallest elements, andheap sort to sort the selected elements in the heap in ascending order.

To select elements, a heap is used (seeheap). For example, foroperator< as comparison function,max-heap is used to selectmiddle − first smallest elements.

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

[edit]Intended use

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

[edit]Example

#include <algorithm>#include <array>#include <functional>#include <iostream> void print(constauto& s,int middle){for(int a: s)std::cout<< a<<' ';std::cout<<'\n';if(middle>0){while(middle-->0)std::cout<<"--";std::cout<<'^';}elseif(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

• In other languages

• Deutsch
• Español
• Français
• Italiano
• 日本語
• Português
• Русский
• 中文