.\" ident @(#)nth_element.3
.\" Standard Template Library
.\" $$RW_INSERT_HEADER "slyrs.man"
.TH nth_element 3C++ "02 Apr 1998" "Rogue Wave Software" "-"
.ce2
Standard C++ Library   
Copyright 1998, Rogue Wave Software, Inc.   

.SH NAME

\f2nth_element\fP

\ - Rearranges a collection so that all elements lower in sorted order than the \f2nth\fP element come before it and all elements higher in sorter order than the \f2nth\fP element come after it.



.SH  SYNOPSIS


.br
#include <algorithm>
.br
template <class RandomAccessIterator>
.br
void nth_element (RandomAccessIterator first,
.RE
.RS 18
RandomAccessIterator nth,
.br
RandomAccessIterator last);
.RE
.RS 0

.br
template <class RandomAccessIterator, class Compare>
.br
void nth_element (RandomAccessIterator first,
.RE
.RS 18
RandomAccessIterator nth,
.br
RandomAccessIterator last,
.br
Compare comp);



.SH  DESCRIPTION


The nth_element algorithm rearranges a collection according to either the default comparison operator (\f2>\fP) or a comparison operator given by the user. After the algorithm is applied, three things are \f2true\fP:


.HP .5i
\(bu	The element that would be in the \f2nth\fP position if the collection were completely sorted is in the \f2nth\fP position
.HP .5i
\(bu	All elements prior to the \f2nth\fP position would also precede that position in an ordered collection
.HP .5i
\(bu	All elements following the \f2nth\fP position would also follow that position in an ordered collection
.HP 0

That is, for any iterator \f2i\fP in the range \f2[first, nth)\fP and any iterator \f2j\fP in the range \f2[nth, last)\fP, it holds that \f2!(*i > *j)\fP or \f2comp(*i, *j) == false\fP. 

Note that the elements that precede or follow the \f2nth\fP position are not necessarily sorted relative to each other. The nth_element algorithm does not sort the entire collection.



.SH  COMPLEXITY


The algorithm is linear, on average, where \f2N\fP is the size of the range \f2[first, last)\fP.



.SH  EXAMPLE



.RE
.RS 0
//
.br
// nthelem.cpp
.br
//
.RE
.RS 1
#include <algorithm>
.br
#include <vector>
.br
#include <iostream>
.RE
.RS 0
using namespace std;
.br

.br
template<class RandomAccessIterator>
.br
void quik_sort(RandomAccessIterator start, 
.RE
.RS 15
RandomAccessIterator end)
.RE
.RS 1
{
.RE
.RS 2
size_t dist = 0;
.br
distance(start, end, dist);
.RE
.RS 0

.RE
.RS 3
//Stop condition for recursion
.RE
.RS 2
if(dist > 2)
.RE
.RS 3
{
.RE
.RS 5
//Use nth_element to do all the work for quik_sort
.br
nth_element(start, start+(dist/2), end);
.RE
.RS 0

.RE
.RS 5
//Recursive calls to each remaining unsorted portion
.RE
.RS 4
quik_sort(start, start+(dist/2-1));
.br
quik_sort(start+(dist/2+1), end);
.RE
.RS 3
}
.RE
.RS 0

.RE
.RS 2
if(dist == 2 && *end < *start)
.RE
.RS 4
swap(start, end);
.RE
.RS 1
}
.RE
.RS 0

.br
int main()
.RE
.RS 1
{
.RE
.RS 3
//Initialize a vector using an array of ints
.RE
.RS 2
int arr[10] = {37, 12, 2, -5, 14, 1, 0, -1, 14, 32};
.br
vector<int> v(arr, arr+10);
.RE
.RS 0

.RE
.RS 3
//Print the initial vector
.RE
.RS 2
cout << "The unsorted values are: " << endl << "     ";
.br
vector<int>::iterator i; 
.br
for(i = v.begin(); i != v.end(); i++)
.RE
.RS 4
cout << *i << ", ";
.RE
.RS 2
cout << endl << endl;
.RE
.RS 0

.RE
.RS 3
//Use the new sort algorithm
.RE
.RS 2
quik_sort(v.begin(), v.end());
.RE
.RS 0

.RE
.RS 3
//Output the sorted vector
.RE
.RS 2
cout << "The sorted values are: " << endl << "     ";
.br
for(i = v.begin(); i != v.end(); i++)
.RE
.RS 4
cout << *i << ", ";
.RE
.RS 2
cout << endl << endl;
.RE
.RS 0

.RE
.RS 2
return 0;
.RE
.RS 1
}

.br
.RE
.RS 0
Program Output



.RE
.RS 0

.br
The unsorted values are:
.RE
.RS 4
37, 12, 2, -5, 14, 1, 0, -1, 14, 32,
.RE
.RS 0
The sorted values are:
.RE
.RS 5
-5, -1, 0, 1, 2, 12, 14, 14, 32, 37,



.SH  WARNINGS


If your compiler does not support default template parameters, then you always need to supply the \f2Allocator\fP template argument. For instance, you need to write:

\f2vector<int, allocator<int> >\fP

instead of:

\f2vector<int>\fP

If your compiler does not support namespaces, then you do not need the using declaration for \f2std\fP.



.SH  SEE ALSO


Algorithms