partial_sort_copy

Algorithm

• Summary
• Data Type and Member Function Indexes
• Synopsis
• Description
• Complexity
• Example
• Warning
• See Also

Templated algorithm for sorting collections of entities.

None

#include <algorithm>

template <class InputIterator,
          class RandomAccessIterator>
 void partial_sort_copy (InputIterator first,
                         InputIterator last,
                         RandomAccessIterator result_first,
                         RandomAccessIterator result_last);
template <class InputIterator,
          class RandomAccessIterator,
          class Compare>
 void partial_sort_copy (InputIterator first,
                         InputIterator last,
                         RandomAccessIterator result_first,
                         RandomAccessIterator result_last,
                         Compare comp);

The partial_sort_copy algorithm places the smaller of last - first and result_last - result_first sorted elements from the range [first, last) into the range beginning at result_first. (i.e., the range: [result_first, result_first+min(last - first, result_last - result_first)). Basically, the effect is as if the range [first,last) were placed in a temporary buffer, sorted and then as many elements as possible were copied into the range [result_first, result_last).

The first version of the algorithm uses less than (operator<) as the comparison operator for the sort. The second version uses the comparison function comp.

partial_sort_copy does approximately (last-first) * log(min(last-first, result_last-result_first)) comparisons.

//
// partsort.cpp
// #include <vector>
 #include <algorithm>
 #include <iostream.h>
 int main()
 {
   int d1[20] = {17, 3,  5,  -4, 1, 12, -10, -1, 14, 7,
                 -6, 8, 15, -11, 2, -2,  18,  4, -3, 0};
   //
   // Set up a vector.
   //
   vector<int> v1(d1+0, d1+20);
   //
   // Output original vector.
   //
   cout << "For the vector: ";
   copy(v1.begin(), v1.end(), ostream_iterator<int>(cout," "));
   //
   // Partial sort the first seven elements.
   //
   partial_sort(v1.begin(), v1.begin()+7, v1.end());
   //
   // Output result.
   //
   cout << endl << endl << "A partial_sort of 7 elements gives: " 
        << endl << "     ";
   copy(v1.begin(), v1.end(), 
        ostream_iterator<int,char>(cout," "));
   cout << endl;
   //
   // A vector of ten elements.
   //
   vector<int> v2(10, 0);
   //
   // Sort the last ten elements in v1 into v2.
   //
   partial_sort_copy(v1.begin()+10, v1.end(), v2.begin(),
                     v2.end());
   //
   // Output result.
   //
   cout << endl << "A partial_sort_copy of the last ten elements 
                    gives: " << endl << "     ";
   copy(v2.begin(), v2.end(), 
        ostream_iterator<int,char>(cout," "));
   cout << endl;
   return 0;
 }
Output :
For the vector: 17 3 5 -4 1 12 -10 -1 14 7 -6 8 15 -11 2 -2 18 4 -3 0
A partial_sort of seven elements gives:
     -11 -10 -6 -4 -3 -2 -1 17 14 12 7 8 15 5 3 2 18 4 1 0
A partial_sort_copy of the last ten elements gives:
     0 1 2 3 4 5 7 8 15 18

If your compiler does not support default template parameters, then you need to always provide the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

sort_ stable_sort, partial_sort

©Copyright 1996, Rogue Wave Software, Inc.