Selection algorithm: Difference between revisions

Revision as of 14:12, 6 April 2014

Revision as of 16:12, 6 April 2014

Line 106:

[[Python (programming language)|Python]]'s standard library (since 2.4) includes <code>[http://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}}.

== See also ==