Selection algorithm: Difference between revisions

Revision as of 06:38, 31 March 2023

Revision as of 06:47, 31 March 2023

Line 70:

[[Python (programming language)|Python]]'s standard library (since 2.4) includes <code>heapq.nsmallest</code> and <code>heapq.nlargest</code> subroutines for returning the smallest or largest elements from a collection, in sorted order. As of Python version 3.11, these subroutines use heapselect, taking time <math>O(n+k\log n)</math> to return a list of <math>k</math> elements. When <math>k</math> is large relative to <math>n</math>, they revert to sorting the whole input and then returning a slice of the resulting sorted array. A linear-time selection algorithm is not included.{{r|python}}

Since 2017, [[Matlab]] includeshas included <code>maxk()</code> and <code>mink()</code> functions, which return the maximal (minimal) k values in a vector as well as their indices. The Matlab documentation does not specify which algorithm these functions use or what their running time is.{{r|matlab}}

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.

[[Matlab]] includes <code>maxk()</code> and <code>mink()</code> functions, which return the maximal (minimal) k values in a vector as well as their indices.

== History==

Line 297 ⟶ 295:

| volume = 13

| year = 1976}}</ref>

<ref name=matlab>{{cite web|url=https://www.mathworks.com/help/matlab/ref/mink.html|title=mink: Find k smallest elements of array|work=Matlab R2023a documentation|publisher=Mathworks|access-date=2023-03-30}}</ref>

<ref name=python>{{cite web|url=https://svn.python.org/projects/python/trunk/Lib/|title=heapq package source code|work=Python library|access-date=2023-03-29}}</ref>