nth_element()

Module:  Standard C++ Library   Library:  Algorithms

Function

• Local Index
• Summary
• Synopsis
• Description
• Complexity
• Example
• See Also
• Standards Conformance

An algorithm that rearranges a collection so that all elements lower in sorted order than the nth element come before it, and all elements higher in sorted order than the nth element come after it

#include <algorithm>

namespace std {
  template <class RandomAccessIterator>
  void nth_element(RandomAccessIterator start,
                   RandomAccessIterator nth,
                   RandomAccessIterator finish);

  template <class RandomAccessIterator, class Compare>
  void nth_element(RandomAccessIterator start,
                   RandomAccessIterator nth,
                   RandomAccessIterator finish,
                   Compare comp);
}

The nth_element() algorithm rearranges a collection according to either operator<() or the function object comp. After the algorithm is applied, the follwoing hold:

• The element that would be in the nth position if the sequence were completely sorted is in the nth position

• All elements prior to the nth position would also precede that position in an ordered sequence

• All elements following the nth position would also follow that position in an ordered sequence

That is, for any iterator i in the range [start, nth) and any iterator j in the range [nth, finish), 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.

The algorithm is linear, on average, where N is the size of the range [start, finish).

//
//  nthelem.cpp
//
 
#include <algorithm>   // for swap
#include <vector>      // for vector
#include <iostream>    // for cout, endl



template<class RandomAccessIterator>
void quik_sort (RandomAccessIterator start, RandomAccessIterator end)
{
    size_t dist = end - start;

    // Stop condition for recursion.
    if (dist > 2) {
        // Use nth_element to do all the work for quik_sort.
        std::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 (2 == dist && *(end - 1) < *start)
        std::swap (start, end);
}


int main ()
{
    typedef std::vector<int, std::allocator<int> > Vector;

    // Initialize a vector using an array of integers.
    Vector::value_type arr[] = { 37, 12,  2, -5, 14, 
                                  1,  0, -1, 14, 32 };

    Vector v (arr + 0, arr + sizeof arr / sizeof *arr);

    // Print the initial vector.
    std::cout << "The unsorted values are: \n     ";

    for (Vector::iterator i = v.begin (); i != v.end (); ++i)
        std::cout << *i << ", ";

    std::cout << "\n\n";

    // Use the new sort algorithm.
    quik_sort (v.begin (), v.end ());

    // Output the sorted vector.
    std::cout << "The sorted values are: \n     ";
    for (Vector::iterator i = v.begin (); i != v.end (); ++i)
        std::cout << *i << ", ";

    std::cout << std::endl << std::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, 

Algorithms

ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.2

Copyright (c) 1994-2006 Rogue Wave Software, a Quovadx Division.
Licensed under the Apache License, Version 2.0.
Contact Rogue Wave about documentation or support issues. You can also seek help from other developers through the Apache stdcxx community (see below).