partial_sort (3C++std) - Tru64 UNIX
Standard C++ LibraryCopyright 1996, Rogue Wave Software, Inc.
NAME
partial_sort - Templated algorithm for sorting collections of entities.
SYNOPSIS
#include <algorithm>
template <class RandomAccessIterator>
void partial_sort (RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void partial_sort (RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last, Compare comp);
DESCRIPTION
The partial_sort algorithm takes the range [first,last) and places the
first middle - first values into sorted order. The result is that the
range [first, middle)is sorted like it would be if the entire range
[first,last) were sorted. The remaining elements in the range (those in
[middle, last)) are not in any defined order. 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.
COMPLEXITY
partial_sort does approximately (last - first) * log(middle-first)
comparisons.
EXAMPLE
//
// 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,char>(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 seven 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
WARNING
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>
SEE ALSO
sort, stable_sort, partial_sort_copy
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
privacy and legal statement