Editing Selection algorithm (section)

== References ==
{{reflist|refs=

<ref name=akss>{{cite journal
 | last1 = Ajtai | first1 = Miklós | author1-link = Miklós Ajtai
 | last2 = Komlós | first2 = János | author2-link = János Komlós (mathematician)
 | last3 = Steiger | first3 = W. L.
 | last4 = Szemerédi | first4 = Endre | author4-link = Endre Szemerédi
 | doi = 10.1016/0022-0000(89)90035-4
 | issue = 1
 | journal = [[Journal of Computer and System Sciences]]
 | mr = 990052
 | pages = 125–133
 | title = Optimal parallel selection has complexity <math>O(\log\log n)</math>
 | volume = 38
 | year = 1989}}</ref>

<ref name=azapip>{{cite journal
 | last1 = Azar | first1 = Yossi
 | last2 = Pippenger | first2 = Nicholas | author2-link = Nick Pippenger
 | doi = 10.1016/0166-218X(90)90128-Y
 | issue = 1–2
 | journal = [[Discrete Applied Mathematics]]
 | mr = 1055590
 | pages = 49–58
 | title = Parallel selection
 | volume = 27
 | year = 1990}}</ref>

<ref name=benjoh>{{cite conference
 | last1 = Bent | first1 = Samuel W.
 | last2 = John | first2 = John W.
 | editor-last = Sedgewick | editor-first = Robert
 | contribution = Finding the median requires <math>2n</math> comparisons
 | doi = 10.1145/22145.22169
 | pages = 213–216
 | publisher = Association for Computing Machinery
 | 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>

<ref name=bfprt>{{cite journal
 | last1 = Blum | first1 = Manuel | author1-link = Manuel Blum
 | last2 = Floyd | first2 = Robert W. | author2-link = Robert W. Floyd
 | last3 = Pratt | first3 = Vaughan | author3-link = Vaughan Pratt
 | last4 = Rivest | first4 = Ronald L. | author4-link = Ron Rivest
 | last5 = Tarjan | first5 = Robert E. | author5-link = Robert Tarjan
 | doi = 10.1016/S0022-0000(73)80033-9 | doi-access = free
 | journal = [[Journal of Computer and System Sciences]]
 | mr = 329916
 | pages = 448–461
 | title = Time bounds for selection
 | url = http://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf
 | volume = 7
 | year = 1973| issue = 4 }}</ref>

<ref name=bks>{{cite journal
 | last1 = Babenko | first1 = Maxim
 | last2 = Kolesnichenko | first2 = Ignat
 | last3 = Smirnov | first3 = Ivan
 | doi = 10.1007/s00224-018-9866-1
 | issue = 4
 | journal = Theory of Computing Systems
 | mr = 3942251
 | pages = 637–646
 | title = Cascade heap: towards time-optimal extractions
 | volume = 63
 | year = 2019| s2cid = 253740380
 }}</ref>

<ref name=brodal>{{cite conference
 | last = Brodal | first = Gerth Stølting | author-link = Gerth Stølting Brodal
 | editor1-last = Brodnik | editor1-first = Andrej
 | editor2-last = López-Ortiz | editor2-first = Alejandro
 | editor3-last = Raman | editor3-first = Venkatesh
 | editor4-last = Viola | editor4-first = Alfredo
 | contribution = A survey on priority queues
 | doi = 10.1007/978-3-642-40273-9_11
 | pages = 150–163
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | 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
 | last = Brown | first = Theodore
 | date = September 1976
 | doi = 10.1145/355694.355704
 | issue = 3
 | journal = ACM Transactions on Mathematical Software
 | pages = 301–304
 | title = Remark on Algorithm 489
 | volume = 2| s2cid = 13985011
 }}</ref>

<ref name=carroll>{{cite book|title=Lawn Tennis Tournaments: The True Method of Assigning Prizes with a Proof of the Fallacy of the Present Method|first=Charles L.|last=Dodgson|author-link=Lewis Carroll|year=1883|location=London|publisher=Macmillan and Co.}} See also {{cite book|title=The Mathematical World of Charles L. Dodgson (Lewis Carroll)|editor1-first=Robin|editor1-last=Wilson|editor2-first=Amirouche|editor2-last=Moktefi|publisher=Oxford University Press|year=2019|isbn=9780192549013|contribution=Lawn tennis tournaments|page=129|contribution-url=https://books.google.com/books?id=OBGIDwAAQBAJ&pg=PA129}}</ref>

<ref name=chan>{{cite journal
 | last = Chan | first = Timothy M. | author-link = Timothy M. Chan
 | doi = 10.1145/1721837.1721842
 | issue = 2
 | journal = [[ACM Transactions on Algorithms]]
 | mr = 2675693
 | page = A26:1–A26:16
 | title = Comparison-based time-space lower bounds for selection
 | volume = 6
 | year = 2010| s2cid = 11742607 }}</ref>

<ref name=chr>{{cite conference
 | last1 = Chaudhuri | first1 = Shiva
 | last2 = Hagerup | first2 = Torben
 | last3 = Raman | first3 = Rajeev
 | editor1-last = Borzyszkowski | editor1-first = Andrzej M.
 | editor2-last = Sokolowski | editor2-first = Stefan
 | contribution = Approximate and exact deterministic parallel selection
 | doi = 10.1007/3-540-57182-5_27
 | pages = 352–361
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Mathematical Foundations of Computer Science 1993, 18th International Symposium, MFCS'93, Gdansk, Poland, August 30 – September 3, 1993, Proceedings
 | volume = 711
 | year = 1993| hdl = 11858/00-001M-0000-0014-B748-C
 | isbn = 978-3-540-57182-7
 | hdl-access = free
 }}</ref>

<ref name=clrs>{{Introduction to Algorithms|edition=3|chapter=Chapter 9: Medians and order statistics|pages=213–227}}; "Section 14.1: Dynamic order statistics", pp. 339–345</ref>

<ref name=cormut>{{cite journal
 | last1 = Cormode | first1 = Graham
 | last2 = Muthukrishnan | first2 = S. | author2-link = S. Muthukrishnan (computer scientist)
 | doi = 10.1016/j.jalgor.2003.12.001
 | issue = 1
 | journal = Journal of Algorithms
 | mr = 2132028
 | pages = 58–75
 | title = An improved data stream summary: the count-min sketch and its applications
 | volume = 55
 | year = 2005}}</ref>

<ref name=cunmun>{{cite journal
 | last1 = Cunto | first1 = Walter
 | last2 = Munro | first2 = J. Ian | author2-link = Ian Munro (computer scientist)
 | doi = 10.1145/62044.62047
 | issue = 2
 | journal = [[Journal of the ACM]]
 | mr = 1072421
 | pages = 270–279
 | title = Average case selection
 | volume = 36
 | year = 1989| s2cid = 10947879
 | doi-access = free
 }}</ref>

<ref name=devroye>{{cite journal
 | last = Devroye | first = Luc
 | doi = 10.1016/0022-0000(84)90009-6
 | issue = 1
 | journal = Journal of Computer and System Sciences
 | mr = 761047
 | pages = 1–7
 | title = Exponential bounds for the running time of a selection algorithm
 | url = http://luc.devroye.org/devroye-selection1984.pdf
 | volume = 29
 | year = 1984}} {{cite journal
 | last = Devroye | first = Luc
 | doi = 10.1007/s00453-001-0046-2
 | issue = 3
 | journal = Algorithmica
 | mr = 1855252
 | pages = 291–303
 | title = On the probabilistic worst-case time of 'find'
 | url = https://luc.devroye.org/wcfind.pdf
 | volume = 31
 | year = 2001| s2cid = 674040
 }}</ref>

<ref name=dieram>{{cite journal
 | last1 = Dietz | first1 = Paul F.
 | last2 = Raman | first2 = Rajeev
 | doi = 10.1006/jagm.1998.0971
 | issue = 1
 | journal = [[Journal of Algorithms]]
 | mr = 1661179
 | pages = 33–51
 | title = Small-rank selection in parallel, with applications to heap construction
 | volume = 30
 | year = 1999}}</ref>

<ref name=dz99>{{cite journal
 | last1 = Dor | first1 = Dorit | author1-link = Dorit Dor
 | last2 = Zwick | first2 = Uri | author2-link = Uri Zwick
 | doi = 10.1137/S0097539795288611
 | issue = 5
 | journal = [[SIAM Journal on Computing]]
 | mr = 1694164
 | pages = 1722–1758
 | title = Selecting the median
 | volume = 28
 | year = 1999| s2cid = 2633282
 }}</ref>

<ref name=dz01>{{cite journal
 | last1 = Dor | first1 = Dorit | author1-link = Dorit Dor
 | last2 = Zwick | first2 = Uri | author2-link = Uri Zwick
 | doi = 10.1137/S0895480199353895
 | issue = 3
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 1857348
 | pages = 312–325
 | title = Median selection requires <math>(2+\varepsilon)N</math> comparisons
 | volume = 14
 | year = 2001}}</ref>

<ref name=erickson>{{cite book|title=Algorithms|url=https://jeffe.cs.illinois.edu/teaching/algorithms/|first=Jeff|last=Erickson|date=June 2019|chapter=1.8: Linear-time selection|pages=35–39}}</ref>

<ref name=floriv>{{cite journal
 | last1 = Floyd | first1 = Robert W. | author1-link = Robert W. Floyd
 | last2 = Rivest | first2 = Ronald L. | author2-link = Ron Rivest
 | date = March 1975
 | doi = 10.1145/360680.360691
 | issue = 3
 | journal = [[Communications of the ACM]]
 | pages = 165–172
 | s2cid = 3064709
 | title = Expected time bounds for selection
 | volume = 18| doi-access = free
 }} See also "Algorithm 489: the algorithm SELECT—for finding the {{nowrap|<math>i</math>th}} smallest of <math>n</math> elements", p. 173, {{doi|10.1145/360680.360694}}.</ref>

<ref name=frederickson>{{cite journal
 | last = Frederickson | first = Greg N.
 | doi = 10.1006/inco.1993.1030
 | issue = 2
 | journal = [[Information and Computation]]
 | mr = 1221889
 | pages = 197–214
 | title = An optimal algorithm for selection in a min-heap
 | volume = 104
 | year = 1993| doi-access = free
 }}</ref>

<ref name=frejoh>{{cite journal
 | last1 = Frederickson | first1 = Greg N.
 | last2 = Johnson | first2 = Donald B. | author2-link = Donald B. Johnson
 | doi = 10.1137/0213002
 | issue = 1
 | journal = [[SIAM Journal on Computing]]
 | mr = 731024
 | pages = 14–30
 | title = Generalized selection and ranking: sorted matrices
 | volume = 13
 | year = 1984}}</ref>

<ref name=gkp>{{cite journal
 | last1 = Gasarch | first1 = William | author1-link = William Gasarch
 | last2 = Kelly | first2 = Wayne
 | last3 = Pugh | first3 = William
 | date = July 1996
 | doi = 10.1145/235767.235772
 | issue = 2
 | journal = [[ACM SIGACT News]]
 | pages = 88–96
 | title = Finding the {{nowrap|<math>i</math>th}} largest of <math>n</math> for small <math>i,n</math>
 | volume = 27| s2cid = 3133332 }}</ref>

<ref name=gootam>{{cite book|title=Algorithm Design and Applications|first1=Michael T.|last1=Goodrich|author1-link= Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|publisher=Wiley|year=2015|chapter=9.2: Selection|pages=270–275|isbn=978-1-118-33591-8}}</ref>

<ref name=gurwitz>{{cite journal
 | last = Gurwitz | first = Chaya
 | doi = 10.1109/13.144650
 | issue = 3
 | journal = IEEE Transactions on Education
 | pages = 230–232
 | title = On teaching median-finding algorithms
 | volume = 35
 | year = 1992| bibcode = 1992ITEdu..35..230G
 }}</ref>

<ref name=hadsob>{{cite report|first1=Abdollah|last1=Hadian|first2=Milton|last2=Sobel|author2-link=Milton Sobel|hdl=11299/199105|series=School of Statistics Technical Reports|volume=121|publisher=University of Minnesota|title=Selecting the {{nowrap|<math>t</math>-th}} largest using binary errorless comparisons|date=May 1969}}</ref>

<ref name=han>{{cite journal
 | last = Han | first = Yijie
 | doi = 10.1145/1290672.1290675
 | issue = 4
 | journal = [[ACM Transactions on Algorithms]]
 | mr = 2364962
 | page = A38:1–A38:11
 | title = Optimal parallel selection
 | volume = 3
 | year = 2007| s2cid = 9645870
 }}</ref>

<ref name=hoare>{{cite journal
 | last = Hoare | first = C. A. R. | author-link = Tony Hoare
 | date = July 1961
 | doi = 10.1145/366622.366647
 | issue = 7
 | journal = [[Communications of the ACM]]
 | pages = 321–322
 | title = Algorithm 65: Find
 | volume = 4}}</ref>

<ref name=karrag>{{cite journal
 | last1 = Karloff | first1 = Howard J.
 | last2 = Raghavan | first2 = Prabhakar | author2-link = Prabhakar Raghavan
 | doi = 10.1145/174130.174132
 | issue = 3
 | journal = [[Journal of the ACM]]
 | mr = 1370358
 | pages = 454–476
 | title = Randomized algorithms and pseudorandom numbers
 | volume = 40
 | year = 1993| s2cid = 17956460
 | doi-access = free
 }}</ref>

<ref name=kkzz>{{cite conference
 | last1 = Kaplan | first1 = Haim
 | last2 = Kozma | first2 = László
 | last3 = Zamir | first3 = Or
 | last4 = Zwick | first4 = Uri | author4-link = Uri Zwick
 | editor1-last = Fineman | editor1-first = Jeremy T.
 | editor2-last = Mitzenmacher | editor2-first = Michael | editor2-link = Michael Mitzenmacher
 | arxiv = 1802.07041
 | contribution = Selection from heaps, row-sorted matrices, and <math>X+Y</math> using soft heaps
 | doi = 10.4230/OASIcs.SOSA.2019.5
 | pages = 5:1–5:21
 | publisher = Schloss Dagstuhl – Leibniz-Zentrum für Informatik
 | series = OASIcs
 | title = 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8–9, 2019, San Diego, CA, USA
 | volume = 69
 | year = 2019| doi-access = free
 }}</ref>

<ref name=kletar>{{cite book
 | last1 = Kleinberg | first1 = Jon | author1-link = Jon Kleinberg
 | last2 = Tardos | first2 = Éva | author2-link = Éva Tardos
 | contribution = 13.5 Randomized divide and conquer: median-finding and quicksort
 | isbn = 9780321295354
 | pages = 727–734
 | publisher = Addison-Wesley
 | title = Algorithm Design
 | year = 2006}}</ref>

<ref name=knuth>{{cite book
 | last = Knuth | first = Donald E. | author-link = Donald Knuth
 | contribution = Section 5.3.3: Minimum-comparison selection
 | edition = 2nd
 | isbn = 0-201-89685-0
 | pages = 207–219
 | publisher = Addison-Wesley
 | title = The Art of Computer Programming, Volume 3: Sorting and Searching
 | title-link = The Art of Computer Programming
 | year = 1998}}</ref>

<ref name=kpaths>{{cite journal
 | last = Eppstein | first = David | author-link = David Eppstein
 | doi = 10.1137/S0097539795290477
 | issue = 2
 | journal = [[SIAM Journal on Computing]]
 | mr = 1634364
 | pages = 652–673
 | title = Finding the <math>k</math> shortest paths
 | volume = 28
 | year = 1999}}</ref>

<ref name=musser>{{cite journal
 | last = Musser | first = David R.
 | date = August 1997
 | doi = 10.1002/(sici)1097-024x(199708)27:8<983::aid-spe117>3.0.co;2-#
 | issue = 8
 | journal = Software: Practice and Experience
 | pages = 983–993
 | publisher = Wiley
 | title = Introspective sorting and selection algorithms
 | volume = 27}}</ref>

<ref name=pattho>{{cite conference
 | last1 = Pătraşcu | first1 = Mihai | author1-link = Mihai Pătrașcu (computer scientist)
 | last2 = Thorup | first2 = Mikkel
 | arxiv = 1408.3045
 | contribution = Dynamic integer sets with optimal rank, select, and predecessor search
 | doi = 10.1109/FOCS.2014.26
 | pages = 166–175
 | 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
 | last1 = Postmus | first1 = J. T.
 | last2 = Rinnooy Kan | first2 = A. H. G. | author2-link = Alexander Rinnooy Kan
 | last3 = Timmer | first3 = G. T.
 | doi = 10.1145/182.358440
 | issue = 11
 | journal = [[Communications of the ACM]]
 | mr = 784120
 | pages = 878–881
 | title = An efficient dynamic selection method
 | volume = 26
 | year = 1983| s2cid = 3211474
 | doi-access = free
 }}</ref>

<ref name=reischuk>{{cite journal
 | last = Reischuk | first = Rüdiger
 | doi = 10.1137/0214030
 | issue = 2
 | journal = [[SIAM Journal on Computing]]
 | mr = 784745
 | pages = 396–409
 | title = Probabilistic parallel algorithms for sorting and selection
 | volume = 14
 | year = 1985}}</ref>

<ref name=skiena>{{cite book
 | last = Skiena | first = Steven S. | author-link = Steven Skiena
 | chapter = 17.3: Median and selection
 | doi = 10.1007/978-3-030-54256-6
 | edition = Third
 | isbn = 978-3-030-54255-9
 | mr = 4241430
 | pages = 514–516
 | publisher = Springer
 | series = Texts in Computer Science
 | title = The Algorithm Design Manual
 | year = 2020| s2cid = 22382667 }}</ref>

<ref name=spp>{{cite journal
 | last1 = Schönhage | first1 = A. | author1-link = Arnold Schönhage
 | last2 = Paterson | first2 = M. | author2-link = Mike Paterson
 | last3 = Pippenger | first3 = N. | author3-link = Nick Pippenger
 | doi = 10.1016/S0022-0000(76)80029-3
 | issue = 2
 | journal = [[Journal of Computer and System Sciences]]
 | mr = 428794
 | pages = 184–199
 | title = Finding the median
 | volume = 13
 | year = 1976| s2cid = 29867292 }}</ref>

<ref name=valiant>{{cite journal
 | last = Valiant | first = Leslie G. | author-link = Leslie Valiant
 | doi = 10.1137/0204030
 | issue = 3
 | journal = [[SIAM Journal on Computing]]
 | mr = 378467
 | pages = 348–355
 | title = Parallelism in comparison problems
 | volume = 4
 | year = 1975}}</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://github.com/python/cpython/blob/main/Lib/heapq.py|title=heapq package source code|work=Python library|access-date=2023-08-06}}; see also the linked [https://code.activestate.com/recipes/577573-compare-algorithms-for-heapqsmallest/ comparison of algorithm performance on best-case data].</ref>

}}

{{DEFAULTSORT:Selection Algorithm}}
[[Category:Selection algorithms| ]]