Hierbei handelt es sich um eine Beispielfolge.
Die Folge von D.L. Shell (1959) "1,2,4,8,16,32,64,128,256,...,x" verspricht eine Laufzeit, die in Ω(nlogn) und Ο(n²) liegt.
Jede Zahl ist eine Zweierpotenz. (xp+1 = 2*xp = 2p+1, x <= (r-l+1)/2). Diese Folge ist sehr ungünstig und sollte nicht angewendet werden.
Die empirische Laufzeit wurde bei einer 2er-Potenz-Feldgröße ermittelt und stellt somit den ungünstigsten Fall dar.
Variante | 2.a (iterativ) |
Typ | Beispiel |
Eigenschaften | iterativ, in-place, instabil, parallelisierbar |
Datenstrukturen | Felder |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit (p) | Ω(n) | Θ(???) | Ο(???) |
Laufzeit | Ω(nlogn) | Θ(n(logn)4) | Ο(n²) |
Vergleiche | nlogn | n(logn)3.0/35 | ??? |
Vertauschungen | 0 | n(logn)3.8/326 | ??? |
shellsort(field A, int l, int r) {
step:= r-l+1;
do {
step:= Round(Up, step/2);
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 | 2.b (rekursiv) |
Typ | Beispiel |
Eigenschaften | rekursiv, in-place, instabil, parallelisierbar |
Datenstrukturen | Felder |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit (p) | Ω(n) | Θ(???) | Ο(???) |
Laufzeit | Ω(nlogn) | Θ(n(logn)4) | Ο(n²) |
Vergleiche | nlogn | n(logn)3.0/35 | ??? |
Vertauschungen | 0 | n(logn)3.8/326 | ??? |
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+1) div 2) then {
shellsort(A, l, r, step*2));
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 2
|