blob: 69c251a3ed7ffb01f338cea4b568462f8e7125bd [file] [log] [blame]
 partial_sort()
Apache C++ Standard Library Reference Guide

partial_sort()

Library:  Algorithms

Function

Local Index

No Entries

Summary

A generic algorithm for sorting collections of entities

Synopsis

#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);
}

Description

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.

Complexity

partial_sort() does approximately (finish - start) * log(mid-start) comparisons. This implementation of partial_sort() is implemented using heapsort, which is O(N * log(N)) in the worst case.

Example

//
//  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