partial_sort_copy()

Module:  Standard C++ Library   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

Copyright (c) 1994-2006 Rogue Wave Software, a Quovadx Division.
Licensed under the Apache License, Version 2.0.
Contact Rogue Wave about documentation or support issues. You can also seek help from other developers through the Apache stdcxx community (see below).