Computing › Stl › Algorithms › Sorting ›

partial_sort_copy

Copies elements in sorted order

View version details

Contents

Definition
Interface
Description
Return Value
Complexity
Page Comments

Key Facts

Gyroscopic Couple: The rate of change of angular momentum ( $\inline \tau$ ) = $\inline I\omega\Omega$ (In the limit).

$\inline I$ = Moment of Inertia.
$\inline \omega$ = Angular velocity
$\inline \Omega$ = Angular velocity of precession.

Blaise Pascal (1623-1662) was a French mathematician, physicist, inventor, writer and Catholic philosopher.

Leonhard Euler (1707-1783) was a pioneering Swiss mathematician and physicist.

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 - first2 and last1 - first1.

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).

References

http://www.tenouk.com/

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

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

partial_sort_copy

Key Facts

Definition

Interface

Description

Return Value

Complexity

References

Example - partial_sort_copy algorithm

See Also