Bubblesort, Variante 5 (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.

Diese Variante stimmt exakt mit der Variante 6 von Insertsort überein!

Variante 5.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²/4 n²/2

bubblesort(field A, int l, int r) {
  for i:= "l-r+1" to "r-l-1" do {
    for j:= r-|i|-1 downto l step 2 do parallel {
      if (A[j] > A[j+1]) then {
        exchange(A[j], A[j+1]);
      }
    }
  }
}

Variante 5.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²/4 n²/2

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

bubblesort(field A, int l, int r, int j) {
  if (j <= r-l-1) then {
    bubble(A, l, r-|j|-1);
    bubblesort(A, l, r, j+1);
  }
}

bubble(field A, int l, int r) {
  if (l < r) then {
    do parallel {
      if (A[r] > A[r+1]) then {
        exchange(A[r], A[r+1]);
      }
      bubble(A, l, r-2);
    }
  }
}


Bubblesort, Variante 5