CodeCogs

Sorts until the first n elements are correct

Definition

The partial_sort() algorithm is defined in the standard header <algorithm> and in the nonstandard backward-compatibility header <algo.h>.

Interface

#include <algorithm>
template < class RandomAccessIterator >
   void partial_sort(
      RandomAccessIterator first, 
      RandomAccessIterator sortEnd,
      RandomAccessIterator last
   );
template < class RandomAccessIterator, class BinaryPredicate >
   void partial_sort(
      RandomAccessIterator first, 
      RandomAccessIterator sortEnd,
      RandomAccessIterator last
      BinaryPredicate comp
   );

Parameters:

Parameter	Description
first	A random-access iterator addressing the position of the first element in the range to be sorted
last	A random-access iterator addressing the position one past the final element in the range to be partially sorted
sortEnd	A random-access iterator addressing the position one past the final element in the sub-range to be sorted
comp	User-defined predicate function object that defines the comparison criterion to be satisfied by successive elements in the ordering. A binary predicate takes two arguments and returns `true` when satisfied and `false` when not satisfied

Description

Partial_sort algorithm partially sorts a range. After calling this function, the elements between first and sortEnd will be sorted and the elements between sortEnd and last will be in an unspecied order.

This function sorts a range of size sortEnd - first by taking its elements between first and last.

The first version compares objects using operator<, and the second compares objects using a function object comp.

Return Value

None.

Complexity

This algorithm performs approximately (last - first) * log(sortEnd - first) comparisons.

References

http://msdn.microsoft.com/en-us/

Example 1

Problem

This program illustrates the use of the STL partial_sort() algorithm (default version) to partially sort a vector of integers of size 12 by getting its 5 smallest values into ascending order at the beginning of the vector.

The following range of values may also be sorted (by chance), but the algorithm does not guarantee this, and you should not expect it.

Workings

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  int a[] = {10,  2,  6, 11,  9,  3, 4, 12,  8,  7,  1,  5};
  vector<int> v(a, a+12);
  cout <<"\nHere are the initial contents of the vector:\n";
  for (vector<int>::size_type i=0; i<v.size(); i++)
    cout <<v.at(i)<<" ";

  cout <<"\nNow we make the following call:";
  cout <<"\npartial_sort(v.begin(), v.begin()+5, v.end());";
  partial_sort(v.begin(), v.begin()+5, v.end());

  cout <<"\nAnd here are the (partially sorted) contents of the "
         "vector,\nup to and including its 5th element:\n";
  for (vector<int>::size_type i=0; i<v.size(); i++)
    cout <<v.at(i)<<" ";

  return 0;
}

Solution

Output:

Here are the initial contents of the vector:
10 2 6 11 9 3 4 12 8 7 1 5

Now we make the following call:
partial_sort(v.begin(), v.begin()+5, v.end());

And here are the (partially sorted) contents of the vector,
up to and including its 5th element:
1 2 3 4 5 11 10 12 9 8 7 6

References

http://www.smu.ca/academic/science/compsci/

Example 2

Problem

This program illustrates the use of the STL partial_sort() algorithm (extended version) to partially order a vector of integers of size 12 by moving the first5 values in the given ordering to the beginning of the "vector, in the proper order.

The range of values following this value may also be ordered, but the algorithm does not guarantee this, and you should not expect it. In this case the order of the elements is determined by one integer preceding another if and only if it has a smaller digit sum.

Workings

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/* Tests if one integer has a smaller digit sum than another.
   i1 and i2 have been initialized and i1, i2 are both > 0.
   Returns true if sum of the digits in i1 is < sum of digits in i2, and otherwise returns false. */

bool hasSmallerDigitSum(int i1, int i2)
{
  int digitSum1 = 0;
  while (i1 != 0)
  {
    digitSum1 += i1 % 10;
    i1 /= 10;
  }

  int digitSum2 = 0;
  while (i2 != 0)
  {
    digitSum2 += i2 % 10;
    i2 /= 10;
  }
  return digitSum1 < digitSum2;
}

int main()
{
  int a[] = {92,  21,  53, 84,  46,  13, 41, 76,  45,  61,  11,  15};
  vector<int> v(a, a+12);
  cout <<"\nHere are the initial contents of the vector:\n";
  for (vector<int>::size_type i=0; i<v.size(); i++)
    cout <<v.at(i)<<" ";

  cout <<"\nNow we make the following call:";
  cout <<"\npartial_sort(v.begin(), v.begin()+5, "
         "v.end(), hasSmallerDigitSum);";
  partial_sort(v.begin(), v.begin()+5, v.end(), hasSmallerDigitSum);

  cout <<"\nAnd here are the (partially sorted) contents of the "
         "vector,\nup to and including its 7th element:\n";
  for (vector<int>::size_type i=0; i<v.size(); i++)
    cout <<v.at(i)<<" ";

  return 0;
}

Solution

Output:

Here are the initial contents of the vector:
92 21 53 84 46 13 41 76 45 61 11 15

Now we make the following call:
partial_sort(v.begin(), v.begin()+5, v.end(), hasSmallerDigitSum);

And here are the (partially sorted) contents of the vector,
up to and including its 7th element:
11 21 13 41 15 84 92 76 46 45 53 61

References

http://www.smu.ca/academic/science/compsci/

partial_sort

Definition

Interface

Description

Return Value

Complexity

References

Example 1

Example 2

See Also