Language Support
Very few languages have built-in support for general selection, although many provide facilities for finding the smallest or largest element of a list. A notable exception is C++, which provides a templated nth_element method with a guarantee of expected linear time. It is implied but not required that it is based on Hoare's algorithm by its requirement of expected linear time. (Ref section 25.3.2 of ISO/IEC 14882:2003(E) and 14882:1998(E), see also SGI STL description of nth_element)
C++ also provides the partial_sort algorithm, which solves the problem of selecting the smallest k elements (sorted), with a time complexity of O(n log k). No algorithm is provided for selecting the greatest k elements since this should be done by inverting the ordering predicate.
For Perl, the module Sort::Key::Top, available from CPAN, provides a set of functions to select the top n elements from a list using several orderings and custom key extraction procedures.
Python's standard library (since 2.4) includes heapq.nsmallest and nlargest, returning sorted lists, the former in O(n + k log n) time, the latter in O(n log k) time.
Because language support for sorting is more ubiquitous, the simplistic approach of sorting followed by indexing is preferred in many environments despite its disadvantage in speed. Indeed for lazy languages, this simplistic approach can even achieve the best complexity possible for the k smallest/greatest sorted (with maximum/minimum as a special case) if the sort is lazy enough.
Read more about this topic: Selection Algorithm
Famous quotes containing the words language and/or support:
“It’s not that we want the political jobs themselves ... but they seem to be the only language the men understand. We don’t really want these $200 a year jobs. But the average man doesn’t understand working for a cause.”
—Jennie Carolyn Van Ness (b. c. 1890–?)
“‘Tis not enough to help the feeble up,
But to support him after.”
—William Shakespeare (1564–1616)