partial_sort


function template
<algorithm>
template <class RandomAccessIterator>
  void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle,
                      RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
  void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle,
                      RandomAccessIterator last, Compare comp );

Partially Sort elements in range

Rearranges the elements in the range [first,last), in such a way that the subrange [first,middle) contains the smallest elements of the entire range sorted in ascending order, and the subrange [middle,end) contains the remaining elements without any specific order.

The elements are compared using operator< for the first version, and comp for the second.

Parameters

first, last
Random-Access iterators to the initial and final positions of the sequence to be used. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
Notice that in this function, these are not consecutive parameters, but the first and third ones.
middle
Random-Access iterator pointing to the element within the range [first,last) that is used as the upper boundary of the elements that are completely sorted.
comp
Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.


Return value

none

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
// partial_sort example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool myfunction (int i,int j) { return (i<j); }

int main () {
  int myints[] = {9,8,7,6,5,4,3,2,1};
  vector<int> myvector (myints, myints+9);
  vector<int>::iterator it;

  // using default comparison (operator <):
  partial_sort (myvector.begin(), myvector.begin()+5, myvector.end());

  // using function as comp
  partial_sort (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);

  // print out content:
  cout << "myvector contains:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout << " " << *it;

  cout << endl;

  return 0;
}


Output:
myvector contains: 1 2 3 4 5 9 8 7 6


Complexity

Performs approximately (last-first)*log(middle-first) comparisons.

See also

sort Sort elements in range (function template)
stable_sort Sort elements preserving order of equivalents (function template)
search Find subsequence in range (function template)
reverse Reverse range (function template)