## nth_element

    Algorithm

- Summary
- Data Type and Member Function Indexes
- Synopsis
- Description
- Complexity
- Example
- Warnings
- See Also

### Summary

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.

### Data Type and Member Function Indexes
(exclusive of constructors and destructors)

None

### 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 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 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

Copyright (c) 1998, Rogue Wave Software, Inc.
Send mail to report errors or comment on the documentation.
OEM Release, June 1998