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

     instead of:

     vector<int>

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

SEE ALSO

     Algorithms