Standard C++	Library
 		 Copyright 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