|
Hierbei handelt es sich um eine Beispielfolge.
Die Folge von Papernov-Stasevich (1965) "1,3,7,15,31,63,127,255,511,...,x" verspricht eine Laufzeit, die in Ω(nlogn) und Ο(n3/2) liegt.
Jede Zahl ist eine Zweierpotenz minus eins. (xp+1 = 2*xp+1 = 2p+1-1, x <= (r-l+1)/2).
| Variante | 3.a (iterativ) |
|---|
| Typ | Beispiel |
|---|
| Eigenschaften | iterativ, in-place, instabil, parallelisierbar |
|---|
| Datenstrukturen | Felder |
|---|
| Speicher | Ω(1) | Θ(1) | Ο(1) |
|---|
| Laufzeit (p) | Ω(n) | Θ(???) | Ο(???) |
|---|
| Laufzeit | Ω(nlogn) | Θ(n(logn)²) | Ο(n3/2) |
|---|
| Vergleiche | nlogn | n(logn)1.7/3.42 | ??? |
|---|
| Vertauschungen | 0 | n(logn)2.1/17.01 | ??? |
|---|
shellsort(field A, int l, int r) {
q:= Round(Down, log(r-l+1));
step:= power(2, q) - 1;
do {
step:= (step-1)/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 | 3.b (rekursiv) |
|---|
| Typ | Beispiel |
|---|
| Eigenschaften | rekursiv, in-place, instabil, parallelisierbar |
|---|
| Datenstrukturen | Felder |
|---|
| Speicher | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit (p) | Ω(n) | Θ(???) | Ο(???) |
|---|
| Laufzeit | Ω(nlogn) | Θ(n(logn)²) | Ο(n3/2) |
|---|
| Vergleiche | nlogn | n(logn)1.7/3.42 | ??? |
|---|
| Vertauschungen | 0 | n(logn)2.1/17.01 | ??? |
|---|
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+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 3
|