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:
“One can say of language that it is potentially the only human home, the only dwelling place that cannot be hostile to man.”
—John Berger (b. 1926)
“American feminists have generally stressed the ways in which men and women should be equal and have therefore tried to put aside differences.... Social feminists [in Europe] ... believe that men and society at large should provide systematic support to women in recognition of their dual role as mothers and workers.”
—Sylvia Ann Hewitt (20th century)