# Man Page nth_element.3

```
Standard C++ Library
Copyright 1998, Rogue Wave Software, Inc.

```

## NAME

```     nth_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 com-
parison operator given by the user. After the  algorithm  is
applied, three things are true:

o    The element that would be in the nth  position  if  the
collection  were  completely sorted is in the nth posi-
tion

o    All elements prior to the nth position would also  pre-
cede that position in an ordered collection

o    All elements following the nth position would also fol-
low 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  posi-
tion  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 Output

The 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  parame-
ters,  then you always need to supply the Allocator template
argument. For instance, you need to write:

vector<int, allocator<int> >

vector<int>

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

```

```     Algorithms

```