Hierbei handelt es sich um eine alternative Variante, die besonders für Listen geeignet ist.
Auch hier ist die Idee einfach: 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 könnte nun ebenfalls eine entsprechende Variante 3 aus Bubblesort entwickelt werden.
Variante | 3.a (iterativ) |
Typ | alternativ, optimiert |
Eigenschaften | iterativ, in-place, instabil, parallelisierbar |
Datenstrukturen | einfachverkettete Listen, Felder |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit (p) | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
Vergleiche | n²/2 | n²/2 | n²/2 |
Verschiebungen | 0 | n | n |
simplesort(field A, int l, int r) {
for i:=r downto l+1 do pipelined {
for j:=l to i-1 do {
if (A[j] > A[i]) then {
move(A[j], A[i]);
j--;
}
}
}
}
| |
Variante | 3.b (rekursiv) |
Typ | alternativ, optimiert |
Eigenschaften | rekursiv, in-place, instabil, parallelisierbar |
Datenstrukturen | einfachverkettete Listen, Felder |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit (p) | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
Vergleiche | n²/2 | n²/2 | n²/2 |
Verschiebungen | 0 | n | n |
simplesort(field A, int l, int r) {
if (l < r) then {
do pipelined {
simple(A, l, r);
simplesort(A, l, r-1);
}
}
}
simple(field A, int l, int r) {
if (l < r) then {
if (A[l] > A[r]) then {
move(A[l], A[r]);
l--;
}
simple(A, l+1, r);
}
}
| |
Simplesort, Variante 3
|