8.1 PRAM Sort

Gegeben n Zahlen a₀,a₁,...,a_{n - 1} ; alle verschieden. Die Aufgabe besteht darin, die n Zahlen zu sortieren.

Idee:

Beschreibe eine Matrix c mit dem Ergebnis aller paarweisen Vergleiche. Ermittele dann für jede Zahl, wie viele Zahlen kleiner sind.

Verwendet wird eine CREW PRAM mit n ² Prozessoren.

FOR ALL 0 $\leq$ i,j $\leq$ n - 1 DO IN PARALLEL
     P_ij : IF a[i] < a[j] THEN c[i,j] := 1
             ELSE c[i,j] := 0
         END
END Die Anzahl der Einsen in der j -ten Spalte der Matrix c gibt an, wie viele Zahlen kleiner sind als a_j . Also liefert die Spaltensumme

die Position von Zahl a_j in der sortierten Folge.

n ² Prozessoren berechnen c_ij in Zeit O(1) .
n ² Prozessoren berechnen b_j in Zeit O(log n) .
Gesamtzeit: O(log n) , Kosten O(n ² · log n) .