Personal tools
partial_sort
Click on the banner to return to the class reference home page.
partial_sort
Algorithm
- Summary
- Data Type and Member Function Indexes
- Synopsis
- Description
- Complexity
- Example
- Warning
- See Also
Summary
Templated algorithm for sorting collections of entities.
Data Type and Member Function Indexes
(exclusive of constructors and destructors)
None
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
©Copyright 1996, Rogue Wave Software, Inc.