Simplesort, Variante 5 (Parallelisierung)

Hierbei handelt es sich um die Parallelisierung der alternativen Original-Variante.

Die Beschreibung der Parallelisierung in Variante 2 ist sehr ungenau. Deshalb finden Sie hier den exakten (besser realisierbaren) Code.

Auch wenn man es dem Code nicht direkt ansieht, ist dieser Algorithmus sehr einfach mittels eines systolischen Feldes realisierbar.

Eine rekursive Realisierung (Variante 5.b) ist möglich.

Variante 5.a (iterativ)
Typ standard
Eigenschaften iterativ, in-place, instabil, parallelisierbar
Datenstrukturen Felder, einfachverkettete Listen
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit (p) Ω(n) Θ(n) Ο(n)
Laufzeit Ω(n²) Θ(n²) Ο(n²)
Vergleiche n²/2 n²/2 n²/2
Vertauschungen 0 n²/4 n²/2

simplesort(field A, int l, int r) {
  for i:="r-1" downto "2*l-r+1" do {
    for j:="l-i" to "((r-i+1) div 2)-1" do parallel {
      if (j >= 0) and (A[i+j] > A[r-j]) then {
        exchange(A[i+j], A[r-j]);
      }
    }
  }
}


Simplesort, Variante 5