Selection algorithm: Difference between revisions

Revision as of 20:44, 17 May 2014

Revision as of 07:50, 20 May 2014

Line 100:

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 thean <code>nth_element</code> template function,<ref>{{cite web |title=std::nth_element |website=cppreference.com [|url=http://wwwen.sgicppreference.com/techw/stlcpp/partial_sort.htmlalgorithm/nth_element partial_sort]|accessdate=20 algorithm,May 2014}}</ref> which solves the problem of selecting the smallest ''k'' elementselement (sorted), within alinear time complexitywhile ofreordering O(''n''its loginput ''k'')sequence. No algorithm is provided for selecting the greatest ''k'' elements since this should be done by inverting the ordering [[Predicate (computer programming)|predicate]].

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.