Hierbei handelt es sich um die Original-Variante. Diese Folge wurde erstmalig von Richard Box und Stephen Lacey vorgestellt (April 1991).
(*) Ich habe keinen plausiblen Grund finden können, warum am Ende die Folge "11, 8, 6, 4, 3, 2, 1" sichergestellt werden muß.
Hinsichtlich der Laufzeit bringt das keine großen Vorteile. Ich empfehle daher diesen Teil wegzulassen.
Variante | 2.a (iterativ) |
Typ | Beispiel |
Eigenschaften | iterativ, in-place, instabil, nicht parallelisierbar |
Datenstrukturen | Felder |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit | Ω(nlogn) | Θ(n(logn)1.4) | Ο(???) |
Vergleiche | 2.64*nlogn | n(logn)1.4/1.17 | ??? |
Vertauschungen | 0 | n(logn)1.3/4.57 | ??? |
combsort(field A, int l, int r) {
gap:= r-l;
do {
if (gap > 1) then {
gap:= Round(Down, gap/1.3);
if ((gap = 9) or (gap = 10)) then { // (*)
gap:= 11; // (*)
} // (*)
}
} while ((comb(A, l, r, gap)) or (gap > 1));
}
boolean comb(field A, int l, int r, int gap) {
flipped:= false;
for i:= l to r-gap do {
if (A[i] > A[i+gap]) then {
exchange(A[i], A[i+gap]);
flipped:= true;
}
}
return flipped;
}
| |
Variante | 2.b (rekursiv) |
Typ | Beispiel |
Eigenschaften | rekursiv, in-place, instabil, nicht parallelisierbar |
Datenstrukturen | Felder |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(nlogn) | Θ(n(logn)1.4) | Ο(???) |
Vergleiche | 2.64*nlogn | n(logn)1.4/1.17 | ??? |
Vertauschungen | 0 | n(logn)1.3/4.57 | ??? |
combsort(field A, int l, int r) {
if combsort(A, l, r, 1) then {
ripplesort(A, l, r);
}
}
ripplesort(field A, int l, int r) {
if comp(A, l, r, 1) then {
ripplesort(A, l, r);
}
}
combsort(field A, int l, int r, int gap) {
if (gap < (r-l)) then {
combsort(A, l, r, Round(Up, gap*1.3));
return comb(A, l, r, gap);
} else {
return true;
}
}
boolean comb(field A, int l, int r, int gap) {
if (l <= r-gap) then {
if (A[l] > A[l+gap]) then {
exchange(A[l], A[l+gap]);
comb(A, l+1, r, gap);
return true;
} else {
return comb(A, l+1, r, gap);
}
} else {
return false;
}
}
| |
Combsort, Variante 2
|