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:
“Philosophy is written in this grand book—I mean the universe—
which stands continually open to our gaze, but it cannot be understood unless one first learns to comprehend the language and interpret the characters in which it is written. It is written in the language of mathematics, and its characters are triangles, circles, and other geometrical figures, without which it is humanly impossible to understand a single word of it.”
—Galileo Galilei (1564–1642)
“Certainly parents play a crucial role in the lives of individuals who are intellectually gifted or creatively talented. But this role is not one of active instruction, of teaching children skills,... rather, it is support and encouragement parents give children and the intellectual climate that they create in the home which seem to be the critical factors.”
—David Elkind (20th century)