Hierbei handelt es sich um eine alternative, optimierte Variante. Die Idee ist einfach:
Eine binäre Suche benötigt deutlich weniger Vergleiche, als eine sequentielle.
Leider ändert sich die asymtotische Laufzeit nicht, da die Vertauschungen nicht optimiert werden können und Verschiebungen nicht möglich sind.
Variante | 5.a (iterativ) |
Typ | alternativ, optimiert |
Eigenschaften | iterativ, in-place, stabil, nicht parallelisierbar |
Datenstrukturen | Felder |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit | Ω(nlogn) | Θ(n²) | Ο(n²) |
Vergleiche | nlogn | nlogn | nlogn |
Vertauschungen | 0 | n²/4 | n²/2 |
insertsort(field A, int l, int r) {
for i:=l+1 to r do {
q:= insert(A, l, i-1, i);
move(A[i], A[q]);
}
}
int insert(field A, int l, int r, int i) {
while (l <= r) do {
q:= (l+r) div 2;
if (A[q] > A[i]) then {
r:= q-1;
} else {
l:= q+1;
}
}
return l;
}
| |
Variante | 5.b (rekursiv) |
Typ | alternativ, optimiert |
Eigenschaften | rekursiv, in-place, stabil, nicht parallelisierbar |
Datenstrukturen | Felder |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(nlogn) | Θ(n²) | Ο(n²) |
Vergleiche | nlogn | nlogn | nlogn |
Vertauschungen | 0 | n²/4 | n²/2 |
insertsort(field A, int l, int r) {
if (l < r) then {
insertsort(A, l, r-1);
q:= insert(A, l, r-1, r);
move(A[r], A[q]);
}
}
int insert(field A, int l, int r, int i) {
if (l <= r) then {
q:= (l+r) div 2;
if (A[q] > A[i]) then {
return insert(l, q-1, i);
} else {
return insert(q+1, r, i);
}
} else {
return l;
}
}
| |
Insertsort, Variante 5
|