Hierbei handelt es sich um eine Beispielfolge.
Die Folge von Knuth "1,4,13,40,121,364,1093,3280,9841,...,x" verspricht eine Laufzeit, die in Ω(nlogn) und Ο(n3/2) liegt.
Jede Zahl ist das dreifache seines Nachfolgers plus eins (xp+1 = 3*xp+1 = 3p+1+xp, x <= (r-l+1)/2).
Diese Folge wird sehr häufig angewendet, liefert bei kleinem n das beste Ergebnis und ist hinsichtlich der Laufzeit der Sedgewick-Folge sehr ähnlich jedoch leichter zu berechnen.
Variante | 4.a (iterativ) |
Typ | Beispiel |
Eigenschaften | iterativ, in-place, instabil, parallelisierbar |
Datenstrukturen | Felder |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit (p) | Ω(n) | Θ(???) | Ο(???) |
Laufzeit | Ω(nlogn) | Θ(n(logn)1.7) | Ο(n3/2) |
Vergleiche | nlogn/1.58 | n(logn)1.6/2.80 | ??? |
Vertauschungen | 0 | n(logn)1.7/5.34 | ??? |
shellsort(field A, int l, int r) {
step:= 1;
while (step <= r-l) do {
step:= step*3+1;
}
do {
step:= (step-1)/3;
for i:=0 to step-1 do parallel {
insertsort(A, l+i, r, step);
}
} while (step > 1);
}
insertsort(field A, int l, int r, int step) {
...
}
| |
Variante | 4.b (rekursiv) |
Typ | Beispiel |
Eigenschaften | rekursiv, in-place, instabil, parallelisierbar |
Datenstrukturen | Felder |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit (p) | Ω(n) | Θ(???) | Ο(???) |
Laufzeit | Ω(nlogn) | Θ(n(logn)1.7) | Ο(n3/2) |
Vergleiche | nlogn/1.58 | n(logn)1.6/2.80 | ??? |
Vertauschungen | 0 | n(logn)1.7/5.34 | ??? |
shellsort(field A, int l, int r) {
shellsort(A, l, r, 1);
}
shellsort(field A, int l, int r, int step) {
if (step <= r-l) then {
shellsort(A, l, r, step*3+1));
shell(A, l, r, step-1, step);
}
}
shell(field A, int l, int r, int i, int step) {
...
}
insertsort(field A, int l, int r, int step) {
...
}
insert(field A, int l, int r, int step) {
...
}
| |
Shellsort, Variante 4
|