Selection algorithm: Difference between revisions

Revision as of 07:50, 4 September 2015

Revision as of 02:09, 9 October 2015

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 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. NoIt algorithmcan isalso providedbe used to solve the problem forof selecting the greatestlargest ''"k''" elements sincein thislinear should be donetime by inverting the ordering, [[Predicatei.e. (computerpassing programmingin std::greater<>()|predicate]] 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.