Selection algorithm: Difference between revisions

Revision as of 18:52, 16 December 2016

Revision as of 09:55, 21 February 2017

Line 99:

== 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 <code>nth_element</code> method with a guarantee of expected linear time, and also partitions the data, requiring that the ''n''th element be sorted into its correct place, elements before the ''n''th element are less than it, and elements after the ''n''th element are greater than it. It is implied but not required that it is based on Hoare's algorithm (or some variant) by its requirement of expected linear time and partitioning of data.<ref>Section 25.3.2 of ISO/IEC 14882:2003(E) and 14882:1998(E)</ref><ref>[http://www.sgi.com/tech/stl/nth_element.html nth_element], SGI STL</ref>

C++ also provides an <code>nth_element</code> template function,<ref>{{cite web |title=std::nth_element |website=cppreference.com |url=http://en.cppreference.com/w/cpp/algorithm/nth_element |accessdate=20 May 2014}}</ref> which solves the problem of selecting the smallest ''k'' element in linear time while reordering its input sequence. It can also be used to solve the problem of selecting the largest "k" elements in linear time by inverting the ordering, i.e. passing in std::greater<>() as the fourth argument.

For [[Perl]], the module [https://metacpan.org/module/Sort::Key::Top 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. Furthermore, the [https://metacpan.org/module/Statistics::CaseResampling Statistics::CaseResampling] module provides a function to calculate quantiles using quickselect.