I have forgotten
my Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttps://me.yahoo.com
ComputingStlAlgorithmsSorting

//

Copies elements in sorted order

Definition

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

Interface

#include <algorithm>
template < class InputIterator, class RandomAccessIterator >
   RandomAccessIterator partial_sort_copy(
      InputIterator first1, 
      InputIterator last1,
      RandomAccessIterator first2, 
      RandomAccessIterator last2
   );
template < class InputIterator, class RandomAccessIterator, 
           class BinaryPredicate >
   RandomAccessIterator partial_sort_copy(
      InputIterator first1, 
      InputIterator last1,
      RandomAccessIterator first2, 
      RandomAccessIterator last2,
      BinaryPredicate comp
   );

Parameters:
Parameter Description
first1 An input iterator addressing the position of the first element in the source range
last1 An input iterator addressing the position one past the final element in the source range
first2 A random-access iterator addressing the position of the first element in the sorted destination range
last2 A random-access iterator addressing the position one past the final element in the sorted destination range
comp User-defined predicate function object that defines the condition to be satisfied if two elements are to be taken as equivalent. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied

Description

Partial_sort_copy function does the same that partial_sort but puts the result in a new range. The number of elements copied is the minimum of last2 - fi rst2 and last1 - fi rst1.

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

Return Value

Returns an iterator on the element following the last element copied.

Complexity

The complexity is between linear and O(N log(N)) (approximately (last1 - first1)*log(last2 - first2) comparisons).
Example:

Example - partial_sort_copy algorithm
Problem
The following example demonstrates the use of partial_sort_copy() (default version).
Workings
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <iostream>
 
using namespace std;
 
int main()
{
  vector<int> v1, v2;
  list<int> list1;
  vector<int>::iterator iter1, iter2;
  list<int>::iterator list1_Iter, list1_inIter;
 
  int i;
  for (i = 0; i <= 9; i++)
    v1.push_back(i);
 
  random_shuffle(v1.begin(), v1.end());
 
  list1.push_back(60);
  list1.push_back(50);
  list1.push_back(20);
  list1.push_back(30);
  list1.push_back(40);
  list1.push_back(10);
 
  cout <<"Vector v1 = ( " ;
  for (iter1 = v1.begin(); iter1 != v1.end(); iter1++)
    cout <<*iter1<<" ";
  cout <<")"<<endl;
 
  cout <<"List list1 = ( " ;
  for (list1_Iter = list1.begin(); list1_Iter!= list1.end(); list1_Iter++)
    cout <<*list1_Iter<<" ";
  cout <<")"<<endl;
 
  // Copying a partially sorted copy of list1 into v1
  vector<int>::iterator result1;
  result1 = partial_sort_copy(list1.begin(), list1.end(),
                              v1.begin(), v1.begin() + 3);
 
  cout <<"List list1 Vector v1 = ( " ;
  for (iter1 = v1.begin() ; iter1 != v1.end() ; iter1++)
    cout <<*iter1<<" ";
  cout <<")"<<endl;
  cout <<"The first v1 element one position beyond"
       <<"\n the last L 1 element inserted was "<<*result1<<"."<<endl;
 
  // Copying a partially sorted copy of list1 into v2
  int ii;
  for (ii = 0; ii <= 9; ii++)
    v2.push_back(ii);
 
  random_shuffle(v2.begin(), v2.end());
  vector<int>::iterator result2;
  result2 = partial_sort_copy(list1.begin(), list1.end(),
                              v2.begin(), v2.begin() + 6);
 
  cout <<"List list1 into Vector v2 = ( " ;
  for (iter2 = v2.begin() ; iter2 != v2.end(); iter2++)
    cout <<*iter2<<" ";
  cout <<")"<<endl;
  cout <<"The first v2 element one position beyond"
       <<"\n the last L 1 element inserted was "<<*result2<<"."<<endl;
 
  return 0;
}
Solution
Output:

Vector v1 = ( 8 1 9 2 0 5 7 3 4 6 )
List list1 = ( 60 50 20 30 40 10 )
List list1 Vector v1 = ( 10 20 30 2 0 5 7 3 4 6 )
The first v1 element one position beyond
the last L 1 element inserted was 2.
List list1 into Vector v2 = ( 10 20 30 40 50 60 1 8 5 2 )
The first v2 element one position beyond
the last L 1 element inserted was 1.
References