Simplesort, Variante 4 (Parallelisierung)

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

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

Damit diese Parallelisierung korrekt funktioniert, muß das CREW-Modell (concurrent read, exclusive write) ermöglicht werden.

Variante 4.a (iterativ)
Typ standard
Eigenschaften iterativ, in-place, stabil, 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²/16 n²/2

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

Variante 4.b (rekursiv)
Typ standard
Eigenschaften rekursiv, in-place, stabil, parallelisierbar
Datenstrukturen Felder, einfachverkettete Listen
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit (p) Ω(n) Θ(n) Ο(n)
Laufzeit Ω(n²) Θ(n²) Ο(n²)
Vergleiche n²/2 n²/2 n²/2
Vertauschungen 0 n²/16 n²/2

simplesort(field A, int l, int r) {
  if (l < r) then {
    simplesort(A, l, r, r-l-1);
  }
}

simplesort(field A, int l, int r, int i) {
  if (i >= 0) {
    simplesort(A, l, r, i-1);
    simple(A, l, r-i, i);
  }
}

simple(field A, int l, int r, int j) {
  if (j >= 0) then {
    do parallel {
      if (A[l+j] >= A[r+j]) then {
        exchange(A[l+j], A[r+j]);
      }
      simple(A, l, r, j-1);
    }
  }
}


Simplesort, Variante 4