Content deleted Content added
m Open access bot: doi added to citation with #oabot. |
Citation bot (talk | contribs) Add: issue, s2cid, title. Changed bare reference to CS1/2. Formatted dashes. | Use this bot. Report bugs. | Suggested by BrownHairedGirl | Linked from User:BrownHairedGirl/Articles_with_bare_links | #UCB_webform_linked 1650/2195 |
||
Line 99:
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.
[[Python (programming language)|Python]]'s standard library (since 2.4) includes <code>[https://docs.python.org/library/heapq.html heapq].nsmallest()</code> and <code>nlargest()</code>, returning sorted lists, in O(''n'' log ''k'') time.<ref>{{Cite web|url=https://stackoverflow.com/a/23038826|title=Python - What is the time complexity of heapq.nlargest?}}</ref>
[[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.
Line 114:
==Bibliography==
* {{Cite journal | last1 = Blum | first1 = M. | author-link1 = Manuel Blum| last2 = Floyd | first2 = R. W. | author-link2 = Robert Floyd| last3 = Pratt | first3 = V. R. | author-link3 = Vaughan Pratt| last4 = Rivest | first4 = R. L. | author-link4 = Ron Rivest| last5 = Tarjan | first5 = R. E. | author-link5 = Robert Tarjan | title = Time bounds for selection | doi = 10.1016/S0022-0000(73)80033-9 | journal = Journal of Computer and System Sciences | volume = 7 | issue = 4 | pages = 448–461 | date =August 1973 | url = http://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf| doi-access = free }}
* {{Cite journal | last1 = Floyd | first1 = R. W. | author-link1 = Robert W. Floyd | last2 = Rivest | first2 = R. L. | author-link2 = Ron Rivest | doi = 10.1145/360680.360691 | title = Expected time bounds for selection | journal = Communications of the ACM | volume = 18 | issue = 3 | pages = 165–172 | date=March 1975 | s2cid = 3064709 }}
* {{Cite journal | last1 = Kiwiel | first1 = K. C. | doi = 10.1016/j.tcs.2005.06.032 | title = On Floyd and Rivest's SELECT algorithm | journal = Theoretical Computer Science | volume = 347 | pages = 214–238 | year = 2005 | issue = 1–2 | doi-access = free }}
* [[Donald Knuth]]. ''[[The Art of Computer Programming]]'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. {{ISBN|0-201-89685-0}}. Section 5.3.3: Minimum-Comparison Selection, pp. 207–219.
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{ISBN|0-262-03293-7}}. Chapter 9: Medians and Order Statistics, pp. 183–196. Section 14.1: Dynamic order statistics, pp. 302–308.
| |||