Content deleted Content added
→Sublinear data structures: more nowrap |
found a source for O(n + k log n) heap select |
||
Line 17:
The time for this method is dominated by the sorting step, which requires <math>\Theta(n\log n)</math> time using a {{nowrap|[[comparison sort]].{{r|clrs|skiena}}}} Even when [[integer sorting]] algorithms may be used, these are generally slower than the linear time that may be achieved using specialized selection algorithms. Nevertheless, the simplicity of this approach makes it attractive, especially when a highly-optimized sorting routine is provided as part of a runtime library, but a selection algorithm is not. For inputs of moderate size, sorting can be faster than non-random selection algorithms, because of the smaller constant factors in its running {{nowrap|time.{{r|erickson}}}} This method also produces a sorted version of the collection, which may be useful for other later computations, and in particular for selection with other choices {{nowrap|of <math>k</math>.{{r|skiena}}}}
For a sorting algorithm that generates one item at a time, such as [[selection sort]], the scan can be done in tandem with the sort, and the sort can be terminated once the {{nowrap|<math>k</math>th}} element has been found. One possible design of a consolation bracket in a [[single-elimination tournament]], in which the teams who lost to the eventual winner play another mini-tournament to determine second place, can be seen as an instance of this {{nowrap|method.{{r|bfprt}}}} Applying this optimization to [[heapsort]] produces the [[heapselect]] algorithm, which can select the {{nowrap|<math>k</math>th}} smallest value in {{nowrap|time <math>O(n+k\log n)</math>.{{r|brodal}}}} This is fast when <math>k</math> is small relative {{nowrap|to <math>n</math>,}} but degenerates to <math>O(n\log n)</math> for larger values {{nowrap|of <math>k</math>,}} such as the choice <math>k=n/2</math> used for median finding.
===Pivoting===
Line 110:
| year = 1973}}</ref>
<ref name=bks>{{
| last1 = Babenko | first1 = Maxim
| last2 = Kolesnichenko | first2 = Ignat
Line 122:
| volume = 63
| year = 2019}}</ref>
<ref name=brodal>{{cite conference
| last = Brodal | first = Gerth Stølting
| 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}}</ref>
<ref name=brown>{{cite journal
| |||