partial_sort()

Module:  Standard C++ Library   Library:  Algorithms

Function

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

A generic algorithm for sorting collections of entities

#include <algorithm>

namespace std {
  template <class RandomAccessIterator>
  void partial_sort(RandomAccessIterator start,
                    RandomAccessIterator mid,
                    RandomAccessIterator finish);

  template <class RandomAccessIterator, class Compare>
  void partial_sort(RandomAccessIterator start,
                    RandomAccessIterator mid, 
                    RandomAccessIterator finish, 
                    Compare comp);
}

The partial_sort() algorithm takes the range [start,finish) and sorts the first mid - start values in ascending order. The remaining elements in the range (those in [mid, finish)) are not in any defined order. 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() does approximately (finish - start) * log(mid-start) comparisons. The Rogue Wave implementation of partial_sort() is implemented using heapsort, which is O(N * log(N)) in the worst case.

//
//  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_copy()

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

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