Hierbei handelt es sich um die Original-Variante.
Analog zu Bubblesort (Variante 2, 3 und 4) sind auch hier einige zusätzliche Optimierungen möglich.
Variante | 1.a (iterativ) |
Typ | standard |
Eigenschaften | iterativ, in-place, stabil, nicht parallelisierbar |
Datenstrukturen | Felder, doppeltverkettete Listen |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
Vergleiche | n²/2 | n²/2 | n²/2 |
Vertauschungen | 0 | n²/4 | n²/2 |
shakersort(field A, int l, int r) {
while (l < r) do {
shaker1(A, l, r);r--;
shaker2(A, l, r);l++;
}
}
shaker1(field A, int l, int r) {
for j:=l to r-1 do {
if (A[j] > A[j+1]) then {
exchange(A[j], A[j+1]);
}
}
}
shaker2(field A, int l, int r) {
for j:=r-1 downto l do {
if (A[j] > A[j+1]) then {
exchange(A[j], A[j+1]);
}
}
}
| |
Variante | 1.b (rekursiv) |
Typ | standard |
Eigenschaften | rekursiv, in-place, stabil, nicht parallelisierbar |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
Vergleiche | n²/2 | n²/2 | n²/2 |
Vertauschungen | 0 | n²/4 | n²/2 |
shakersort(field A, int l, int r) {
if (l < r) do {
shaker(A, l, r);
shakersort(A, l+1, r-1);
}
}
shaker(field A, int l, int r) {
if (l < r) then {
if (A[l] > A[l+1]) then {
exchange(A[l], A[l+1]);
}
shaker(A, l+1, r);
if (A[l] > A[l+1]) then {
exchange(A[l], A[l+1]);
}
}
}
| |
Shakersort, Variante 1
|