partial_sort_copy()

Library:  Algorithms

Function

• Local Index
• Summary
• Synopsis
• Description
• Complexity
• Example
• See Also
• Standards Conformance

Templatized algorithm for sorting collections of entities

#include <algorithm>

namespace std {
  template <class InputIterator,
            class RandomAccessIterator>
  void partial_sort_copy(InputIterator start,
                         InputIterator finish,
                         RandomAccessIterator result_start,
                         RandomAccessIterator result_finish);
  template <class InputIterator,
            class RandomAccessIterator,
            class Compare>
  void partial_sort_copy(InputIterator start,
                         InputIterator finish,
                         RandomAccessIterator result_start,
                         RandomAccessIterator result_finish,
                         Compare comp);
}

The partial_sort_copy() algorithm places the smaller of finish - start and result_finish - result_start sorted elements from the range [start, finish) into the range beginning at result_start (in other words, the range: [result_start, result_start+min(finish - start, result_finish - result_start)). The effect is as if the range [start,finish) were placed in a temporary buffer, sorted, and then as many elements as possible copied into the range [result_start, result_finish).

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

partial_sort_copy() does approximately (finish-start) * log(min(finish-start, result_finish-result_start)) comparisons.

//
//  partsort.cpp
//

#include <algorithm>   // for partial_sort
#include <iostream>    // for cout, endl
#include <iterator>    // for ostream_iterator
#include <vector>      // for vector



int main()
{
    typedef std::vector<int, std::allocator<int> > Vector;

    typedef std::ostream_iterator<int, char, 
                                  std::char_traits<char> >
            Iter;

    const Vector::value_type a[] = {
        17, 3,  5,  -4, 1, 12, -10, -1, 14, 7,
        -6, 8, 15, -11, 2, -2,  18,  4, -3, 0
    };

    Vector v1 (a + 0, a + sizeof a / sizeof *a);

    // Output original vector.
    std::cout << "For the vector: ";
    std::copy (v1.begin (), v1.end (), Iter (std::cout, " "));

    // Partial sort the first seven elements.
    std::partial_sort (v1.begin (), v1.begin () + 7, 
                       v1.end ());

    // Output result.
    std::cout << "\n\nA partial_sort of seven elements "
              << "gives: \n     ";
    std::copy (v1.begin (), v1.end (), Iter (std::cout, " "));
    std::cout << std::endl;

    // A vector of ten elements.
    Vector v2 (Vector::size_type (10), 0);

    // Sort the last ten elements in v1 into v2.
    std::partial_sort_copy (v1.begin () + 10, v1.end (),
                            v2.begin (), v2.end ());

    // Output result.
    std::cout
        << "\nA partial_sort_copy of the last ten elements "
        << "gives: \n     ";
    std::copy (v2.begin (), v2.end (), Iter (std::cout, " "));

    std::cout << std::endl;

    return 0;
}


Program 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 

sort()¸ stable_sort(), partial_sort()

ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.1.4