|
Hierbei handelt es sich um eine Beispielfolge.
Die 11/5-Folge(?) "1,3,7,16,36,80,177,390,859,...,x" verspricht eine Laufzeit, die in Ω(nlogn) und Ο(n3/2) liegt.
Jede Zahl ist das 11/5-fache seines Vorgängers plus eins (xp+1 = 11/5*xp+1, x <= (r-l+1)/2). Die Folge wurde von mir etwas modifiziert.
Diese Folge liefert momentan das beste asymptotische Ergebnis im average case. Leider weiß ich ich von wem diese Folge wann entdeckt wurde.
| Variante | 5.a (iterativ) |
|---|
| Typ | Beispiel |
|---|
| Eigenschaften | iterativ, in-place, instabil, parallelisierbar |
|---|
| Datenstrukturen | Felder |
|---|
| Speicher | Ω(1) | Θ(1) | Ο(1) |
|---|
| Laufzeit (p) | Ω(n) | Θ(???) | Ο(???) |
|---|
| Laufzeit | Ω(nlogn) | Θ(n(logn)1.5) | Ο(n3/2) |
|---|
| Vergleiche | nlogn | n(logn)1.3/1.46 | ??? |
|---|
| Vertauschungen | 0 | n(logn)1.5/4.83 | ??? |
|---|
shellsort(field A, int l, int r) {
step:= 1;
while (step <= (r-l)) do {
step:= Round(Down, step*11/5+1);
}
do {
step:= Round(Up, (step-1)*5/11);
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 | 5.b (rekursiv) |
|---|
| Typ | Beispiel |
|---|
| Eigenschaften | rekursiv, in-place, instabil, parallelisierbar |
|---|
| Datenstrukturen | Felder |
|---|
| Speicher | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit (p) | Ω(n) | Θ(???) | Ο(???) |
|---|
| Laufzeit | Ω(nlogn) | Θ(n(logn)1.5) | Ο(n3/2) |
|---|
| Vergleiche | nlogn | n(logn)1.3/1.46 | ??? |
|---|
| Vertauschungen | 0 | n(logn)1.5/4.83 | ??? |
|---|
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, Round(Down,(step*11/5)+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 5
|