partial_sort_copy

10,000+ views

GPL — licence
Edit / fork this page
Contents
  1. Definition
  2. Interface
  3. Description
  4. Return Value
  5. Complexity
  6. References
  7. See Also

Copies elements in sorted order

You're viewing an older version of this page (#4164). View the current version.

Computing Stl Algorithms Sorting

View versions (1)

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:

ParameterDescription
first1An input iterator addressing the position of the first element in the source range
last1An input iterator addressing the position one past the final element in the source range
first2A random-access iterator addressing the position of the first element in the sorted destination range
last2A random-access iterator addressing the position one past the final element in the sorted destination range
compUser-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 http://www.codecogs.com/reference/computing/stl/algorithms/sorting/partial_sort.php"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

Example 1
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

See Also