Content deleted Content added
Removed collapse templates according to https://en.wikipedia.org/wiki/Wikipedia:Manual_of_Style#Scrolling_lists_and_collapsible_content |
|||
Line 11:
...
== Examples ==
=== Prefixsum ===
Line 21 ⟶ 22:
=== Selection ===
The [[selection problem]] is about finding the k-th smallest item in an unordered list <math>A</math> of size <math>N</math>.
The following code<ref name=":0" /> makes use of <code>PRAMSORT</code> which is a PRAM optimal sorting algorithm which runs in <math>O(\log N)</math>, and <code>SELECT</code>, which is a cache optimal single-processor selection algorithm.
'''if''' <math>N \leq P</math> '''then'''
Line 44:
'''return''' <math>\texttt{PEMSELECT}(A[t+1:N], P, k-t)</math>
'''end if'''
Under the assumption that the input is stored in contiguous memory, <code>PEMSELECT</code> has an I/O complexity of:
Line 53 ⟶ 52:
[[Distribution sort]] partitions an input list <math>A</math> of size <math>N</math> into <math>d</math> disjoint buckets of similar size. Every bucket is then sorted recursively and the results are combined into a fully sorted list.
If <math>P = 1</math> the task is delegated to a cache-optimal single-processor sorting algorithm.
Line 88 ⟶ 86:
recursively call <math>\texttt{PEMDISTSORT}</math> on bucket <math>j</math>of size <math>\mathcal{B}[j]</math>
using <math>O \left( \left \lceil \tfrac{\mathcal{B}[j]}{N / P} \right \rceil \right)</math> processors responsible for elements in bucket <math>j</math>
'''end for'''
'''end for'''|<code>PEMDISTSORT</code> pseudocode}}<br />The I/O complexity of <code>PEMDISTSORT</code> is:▼
▲
<math>O \left( \left \lceil \frac{N}{PB} \right \rceil \left ( \log_d P + \log_{M/B} \frac{N}{PB} \right ) + f(N,P,d) \cdot \log_d P \right)</math>
| |||