Standard C++ LibraryCopyright 1996, 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 the provided comparison operator.  After
  the algorithm applies, 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 precede that position
       in an ordered collection

  •       All elements following the nth position would 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.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<int> >

  instead of :

  vector<int>

SEE ALSO

  Algorithms

STANDARDS CONFORMANCE

  ANSI X3J16/ISO WG21 Joint C++ Committee



privacy and legal statement