home | help 
std::partial_sort(3)	       C++ Standard Libary	    std::partial_sort(3)

NAME
     std::partial_sort - std::partial_sort

Synopsis
	Defined in header <algorithm>
	template< class RandomIt >
	void  partial_sort( RandomIt first, RandomIt middle,	  (1) (constexpr
     since C++20)
	RandomIt last );
	template< class ExecutionPolicy, class RandomIt >

	void  partial_sort(  ExecutionPolicy&&	policy, 	     (2)  (since
     C++17)

			   RandomIt first, RandomIt middle,
	RandomIt last );
	template< class RandomIt, class Compare >

	void  partial_sort( RandomIt first, RandomIt middle,	  (3) (constexpr
     since C++20)
	RandomIt last,

			   Compare comp );
	template< class ExecutionPolicy, class RandomIt, class
	Compare >

	void  partial_sort(  ExecutionPolicy&&	policy, 	     (4)  (since
     C++17)
			   RandomIt first, RandomIt middle,
	RandomIt last,

			   Compare comp );

	Rearranges  elements  such  that  the range [first, middle) contains the
     sorted middle a
	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).
	3) 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

	std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>    is    true.
     (until
										  C++20)
	std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>      is
     true. (since
										  C++20)

	If any of the following conditions is satisfied, the behavior  is  unde-
     fined:

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

	  * The type of *first is not Swappable.	   (until C++11)
	  * RandomIt is not ValueSwappable.
	  * The type of *first is not MoveConstructible.   (since C++11)
	  * The type of *first is not MoveAssignable.

Parameters
	first, last - random access iterators defining the range
	middle	    - random access iterator defining the one-past-the-end iter-
     ator of the
		      range to be sorted
	policy	     - the execution policy to use. See execution policy for de-
     tails.
		      comparison function object (i.e. an object that  satisfies
     the
		      requirements  of	Compare) which returns true if the first
     argument is
		      less than (i.e. is ordered before) the second.

		      The signature of the comparison function should be equiva-
     lent to the
		      following:

		      bool cmp(const Type1& a, const Type2& b);
	comp	    -
		      While the signature does not  need  to  have  const&,  the
     function must
		      not  modify  the	objects passed to it and must be able to
     accept all
		      values of type (possibly const) Type1 and Type2 regardless
     of value
		      category (thus, Type1& is not allowed
		      , nor is Type1 unless for Type1 a move is equivalent to  a
     copy
		      (since C++11)).
		      The  types  Type1 and Type2 must be such that an object of
     type RandomIt
		      can be dereferenced and then implicitly converted to  both
     of them.

Type requirements
	-
	RandomIt must meet the requirements of LegacyRandomAccessIterator.
	-
	Compare must meet the requirements of Compare.

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

	1,2)  Approximately \(\scriptsize N \cdot \log(M)\)NA.log(M) comparisons
     using
	operator<
	(until C++20)
	std::less{}
	(since C++20).
	3,4) Approximately \(\scriptsize N \cdot \log(M)\)NA.log(M) applications
     of the
	comparator comp.

Exceptions
	The overloads with a template parameter named ExecutionPolicy report er-
     rors 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-de-
     fined.
	  * If the algorithm fails to allocate memory, std::bad_alloc is thrown.

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

					  partial_sort (1)
      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>());
      }
					  partial_sort (3)
      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 afirsta
	      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);
      }

Notes
Algorithm
	The algorithm used is typically heap select to select the smallest  ele-
     ments, 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 opera-
     tor< as
	comparison function, max-heap is used to select middle a first	smallest
     elements.

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

	  Intended use

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

Example
     // Run this code

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

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
	      ^----------

	Defect reports

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

	  DR	 Applied to	   Behavior as published	     Correct be-
     havior
	P0896R4 C++98	   [first, middle) and [middle, last)	the behavior  is
     undefined
			   were  not  required to be valid ranges if any of them
     is invalid

See also
			     partially sorts the given range making sure that it
     is
	nth_element	     partitioned by the given element
			     (function template)
	partial_sort_copy    copies and partially sorts a range of elements
			     (function template)
			     sorts a range of elements	while  preserving  order
     between equal
	stable_sort	     elements
			     (function template)
	sort		     sorts a range into ascending order
			     (function template)
	ranges::partial_sort sorts the first N elements of a range
	(C++20) 	     (niebloid)

http://cppreference.com 	   2024.06.10		    std::partial_sort(3)
home | help