Selection algorithm: Difference between revisions

Revision as of 13:38, 1 September 2013

Revision as of 21:24, 16 September 2013

Line 102:

C++ also provides the [http://www.sgi.com/tech/stl/partial_sort.html partial_sort] algorithm, which solves the problem of selecting the smallest ''k'' elements (sorted), with a time complexity of O(''n'' log ''k''). 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 [httphttps://search.cpanmetacpan.org/distmodule/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 [httphttps://search.cpanmetacpan.org/distmodule/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://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.