Revision as of 07:50, 20 May 2014 edit Qwertyus (talk \| contribs) Extended confirmed users 31,640 edits →Language support: C++'s partial_sort is a partial sorting algo; nth_element is the selection algo ← Previous edit		Revision as of 03:27, 20 August 2014 edit undo Chmarkine (talk \| contribs) 3,951 edits m →Language support: change to https if the server sends HSTS header, replaced: http://docs.python.org → https://docs.python.org using AWB Next edit →
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>[~~http~~https://docs.python.org/library/heapq.html heapq].nsmallest()</code> and <code>nlargest()</code>, returning sorted lists, the former in O(''n'' + ''k'' log ''n'') time, the latter in O(''n'' log ''k'') time. 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}}.

Selection algorithm: Difference between revisions