Content deleted Content added
No edit summary |
No edit summary |
||
Line 21:
=== Selection ===
The selection problem is to find an item in an unordered list <math>A</math> of size <math>N</math>which is bigger than <math>k-1</math>other elements in <math>A</math>.
{{Collapse|1=
'''if''' <math>N \leq P</math>'''then'''
<math>\texttt{PRAMSORT}(A,P)</math>
Line 42 ⟶ 44:
'''return''' <math>\texttt{PEMSELECT}(A[t+1:N], P, k-t)</math>
'''end if'''
|2=PEM selection algorithm pseudocode}}
Under the assumption that the input is stored in contiguous memory, <code>PRAMSORT</code> runs in <math>O(\log N)</math>, and <code>SELECT</code> is a cache optimal single-processor selection algorithm, this algorithm has an I/O complexity of:
| |||