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:
“Surrealism is not a school of poetry but a movement of liberation.... A way of rediscovering the language of innocence, a renewal of the primordial pact, poetry is the basic text, the foundation of the human order. Surrealism is revolutionary because it is a return to the beginning of all beginnings.”
—Octavio Paz (b. 1914)
“The interest in Wisdom is fading. Soon there will not be enough left to support the aphorism, even though it tries to amuse by half-mocking the Wisdom it propounds.”
—Mason Cooley (b. 1927)