Hierbei handelt es sich um eine alternative Original-Variante, die jedoch hinsichtlich er Laufzeit einige schwächen aufweist.
Es wurde lediglich die Richtung der inneren for-Schleife umgekehrt.
Analog zu Bubblesort (Variante 3) sind hier ebenfalls einige Optimierungen möglich. Die Realisierung wäre jedoch etwas komplizierter.
Mit etwas Geschick ist diese Variante parallelisierbar. Genauere Informationen dazu finden sie in Variante 5.
Variante | 2.a (iterativ) |
Typ | standard |
Eigenschaften | iterativ, in-place, instabil, 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 |
simplesort(field A, int l, int r) {
for i:=r downto l+1 do pipelined {
for j:=i-1 to l do {
if (A[j] > A[i]) then {
exchange(A[j], A[i]);
}
}
}
}
| |
Variante | 2.b (rekursiv) |
Typ | standard |
Eigenschaften | rekursiv, in-place, instabil, 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 |
simplesort(field A, int l, int r) {
if (l < r) then {
do pipelined {
simple(A, l, r-1, r);
simplesort(A, l, r-1);
}
}
}
simple(field A, int l, int j, int r) {
if (l <= i) then {
if (A[i] > A[r]) then {
exchange(A[i], A[r]);
}
simple(A, l, i-1, r);
}
}
| |
Simplesort, Variante 2
|