Hierbei handelt es sich um eine alternative Variante, die besonders für Listen geeignet ist.
Auch hier ist die Idee simpel: Da bei Listen Verschiebungen billiger als Vertauschungen sind,
wird der Algorithmus dem entsprechend angepaßt. Dadurch werden sogar Bewegungsoperationen eingespart, so daß es sich
nicht nur um eine Alternative, sondern um eine Optimierung handelt.
Analog zur Variante 1 kann nun ebenfalls eine entsprechende Variante 2 bzw. 3 entwickelt werden.
Variante | 4.a (iterativ) |
Typ | alternativ, optimiert |
Eigenschaften | iterativ, in-place, stabil, nicht parallelisierbar |
Datenstrukturen | einfachverkettete Listen, Felder |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit | Ω(n) | Θ(n²) | Ο(n²) |
Vergleiche | n²/2 | n²/2 | n²/2 |
Verschiebungen | 0 | n²/12 | n²/2 |
bubblesort(list A, int l, int r) {
for i:=r downto l+1 do {
q:= l;
for j:=l to i-1 do {
if (A[j+1] > A[q]) then {
move(A[q], A[j]);
q:= j+1;
}
}
move(A[q], A[i]);
}
}
| |
Variante | 4.b (rekursiv) |
Typ | alternativ, optimiert |
Eigenschaften | rekursiv, in-place, stabil, nicht parallelisierbar |
Datenstrukturen | einfachverkettete Listen, Felder |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(n) | Θ(n²) | Ο(n²) |
Vergleiche | n²/2 | n²/2 | n²/2 |
Verschiebungen | 0 | n²/12 | n²/2 |
bubblesort(field A, int l, int r) {
if (l < r) then {
bubble(A, l, l, r);
bubblesort(A, l, r-1);
}
}
bubble(field A, int q, int l, int r) {
if (l < r) then {
if (A[l+1] > A[q]) then {
move(A[q], A[l]);
q:= l+1;
}
bubble(A, q, l+1, r);
} else {
move(A[q], A[r]);
}
}
| |
Bubblesort, Variante 4
|