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-|j|-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
|