Selection algorithm: Difference between revisions

Revision as of 18:38, 29 May 2016

Revision as of 15:25, 25 July 2016

Line 104:

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.

[[Python (programming language)|Python]]'s standard library (since 2.4) includes <code>[https://docs.python.org/library/heapq.html heapq].nsmallest()</code> and <code>nlargest()</code>, returning sorted lists, in O(''n'' log ''k'') time.<ref>httphttps://stackoverflow.com/a/23038826</ref>

Because [[sorting algorithm#Language support|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 evaluation|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{{Citation needed|date=April 2014}}.