Top of document
©Copyright 1999 Rogue Wave Software

nth_element


     Algorithm

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.

Contents

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 the provided comparison operator. After the algorithm applies, three things are true:

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 postion 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.h>
 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;
 }
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,

Warning

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

vector<int, allocator>

instead of :

vector<int>

See Also

Algorithms


Top of document