Selection algorithm: Difference between revisions

Revision as of 19:37, 29 September 2023

Latest revision as of 20:59, 28 January 2025

(5 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 (since 2.4) includes <code>heapq.nsmallest</code> and <code>heapq.nlargest</code> subroutinesfunctions for returning the smallest or largest elements from a collection, in sorted order. Different versions of Python have used different algorithms for these subroutines. As of Python version 3.13, theThe implementation maintains a [[binary heap]], limited to holding <math>k</math> elements, and initialized to the first <math>k</math> elements in the collection. Then, each subsequent itemsitem of the collection may replace the largest or smallest element in the heap (respectivelyif forit <code>heapqis smaller or larger than this element.nsmallest</code> andThe algorithm's memory usage is superior to heapselect (the former only holds <codemath>heapq.nlargestk</codemath>) ifelements itin ismemory smallerat ora largertime thanwhile thisthe elementlatter requires manipulating the entire dataset into memory). The worst-caseRunning time fordepends thison implementationdata ordering. The best case is <math>O((n - k) + k\log k)</math>, worsefor thanalready thesorted data. The worst-case is <math>O(n+k\log nk)</math> thatfor wouldreverse be achievedsorted by heapselectdata. However,In for randomaverage input sequencescases, 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