nth_element(3C++) - nth_element(3C++)
Standard C++ Library Copyright 1998, Rogue Wave Software, Inc.
NAMEnth_element
- Rearranges a collection so that all elements lower in sorted order
than the nth element come before it and all elements higher in sorter
order than the nth element come after it.
SYNOPSIS
#include <algorithm>
template <class RandomAccessIterator>
void nth_element (RandomAccessIterator first,
RandomAccessIterator nth,
RandomAccessIterator last);
template <;class RandomAccessIterator, class Compare>
void nth_element (RandomAccessIterator first,
RandomAccessIterator nth,
RandomAccessIterator last,
Compare comp);
DESCRIPTION
The nth_element algorithm rearranges a collection according to either
the default comparison operator (>) or a comparison operator given by
the user. After the algorithm is applied, three things are true:
· The element that would be in the nth position if the collection
were completely sorted is in the nth position
· All elements prior to the nth position would also precede that
position in an ordered collection
· All elements following the nth position would also follow that
position in an ordered collection
That is, for any iterator i in the range [first, nth) and any iterator
j in the range [nth, last), it holds that !(*i > *j) or comp(*i, *j) ==
false.
Note that the elements that precede or follow the nth position are not
necessarily sorted relative to each other. The nth_element algorithm
does not sort the entire collection.
COMPLEXITY
The algorithm is linear, on average, where N is the size of the range
[first, last).
EXAMPLE
//
// nthelem.cpp
//
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
template<;class RandomAccessIterator>
void quik_sort(RandomAccessIterator start,
RandomAccessIterator end)
{
size_t dist = 0;
distance(start, end, dist);
//Stop condition for recursion
if(dist > 2)
{
//Use nth_element to do all the work for quik_sort
nth_element(start, start+(dist/2), end);
//Recursive calls to each remaining unsorted portion
quik_sort(start, start+(dist/2-1));
quik_sort(start+(dist/2+1), end);
}
if(dist == 2 && *end < *start)
swap(start, end);
}
int main()
{
//Initialize a vector using an array of ints
int arr[10] = {37, 12, 2, -5, 14, 1, 0, -1, 14, 32};
vector<int> v(arr, arr+10);
//Print the initial vector
cout << "The unsorted values are: " << endl << " ";
vector<int>::iterator i;
for(i = v.begin(); i != v.end(); i++)
cout << *i << ", ";
cout << endl << endl;
//Use the new sort algorithm
quik_sort(v.begin(), v.end());
//Output the sorted vector
cout << "The sorted values are: " << endl << " ";
for(i = v.begin(); i != v.end(); i++)
cout << *i << ", ";
cout << endl << endl;
return 0;
}
Program OutputThe unsorted values are:
37, 12, 2, -5, 14, 1, 0, -1, 14, 32,
The sorted values are:-5, -1, 0, 1, 2, 12, 14, 14, 32, 37,
WARNINGS
If your compiler does not support default template parameters, then you
always need to supply the Allocator template argument. For instance,
you need to write:
vector<int, allocator<int> >
instead of:
vector<int>
If your compiler does not support namespaces, then you do not need the
using declaration for std.
SEE ALSO
Algorithms
Rogue Wave Software 02 Apr 1998 nth_element(3C++)
