Selection algorithm: Difference between revisions

Revision as of 18:53, 23 June 2024

Latest revision as of 20:59, 28 January 2025

(4 intermediate revisions by 4 users not shown)

Line 78:

Very few languages have built-in support for general selection, although many provide facilities for finding the smallest or largest element of a list. A notable exception is the [[Standard Template Library]] for [[C++]], which provides a templated <code>nth_element</code> method with a guarantee of expected linear time.{{r|skiena}}

[[Python (programming language)|Python]]'s standard library includes <code>heapq.nsmallest</code> and <code>heapq.nlargest</code> functions for returning the smallest or largest elements from a collection, in sorted order. The implementation maintains a [[Binary heap|binary heap]], limited to holding <math>k</math> elements, and initialized to the first <math>k</math> elements in the collection. Then, each subsequent item of the collection may replace the largest or smallest element in the heap if it is smaller or larger than this element. The algorithm's memory usage is superior to heapselect (the former only holds <math>k</math> elements in memory at a time while the latter requires manipulating the entire dataset into memory). Running time depends on data ordering. The best case is <math>O((n - k) + k\log k)</math> for already sorted data. The worst-case is <math>O(n\log k)</math> for reverse sorted data. In average cases, there are likely to be few heap updates and most input elements are processed with only a single comparison. For example, extracting the 100 largest or smallest values out of 10,000,000 random inputs makes 10,009,401 comparisons on average.{{r|python}}

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

Line 128:

| title = Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6–8, 1985, Providence, Rhode Island, USA

| year = 1985| doi-access = free

| isbn = 0-89791-151-2

}}</ref>

Line 172 ⟶ 173:

| title = Space-Efficient Data Structures, Streams, and Algorithms – Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday

| volume = 8066

| year = 2013| isbn = 978-3-642-40272-2 }}</ref>

<ref name=brown>{{cite journal

Line 212 ⟶ 213:

| volume = 711

| year = 1993| hdl = 11858/00-001M-0000-0014-B748-C

| isbn = 978-3-540-57182-7

| hdl-access = free

}}</ref>

Line 420 ⟶ 422:

| title = 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8–9, 2019, San Diego, CA, USA

| volume = 69

| year = 2019}}</ref>| doi-access = free

}}</ref>

<ref name=kletar>{{cite book

Line 474 ⟶ 477:

| publisher = IEEE Computer Society

| title = 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18–21, 2014

| year = 2014| isbn = 978-1-4799-6517-5 }}</ref>

<ref name=prt>{{cite journal