Hierbei handelt es sich um eine alternative Variante (Alternative zu Variante 2!), die besonders für Listen geeignet ist.
Auch hier ist die Idee einfach: Da bei Listen Verschiebungen billiger als Vertauschungen sind,
wird der Algorithmus dem entsprechend angepaßt. Dadurch werden sogar Bewegungsoperationen eingespart, so daß es
sich um eine echte Optimierung handelt.
Variante | 3.a (iterativ) |
Typ | alternativ, optimiert |
Eigenschaften | iterativ, in-place, stabil, nicht parallelisierbar |
Datenstrukturen | doppeltverkettete Listen, Felder |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit | Ω(n) | Θ(n²) | Ο(n²) |
Vergleiche | n | n²/4 | n²/2 |
Verschiebungen | 0 | n | n |
insertsort(list A, int l, int r) {
for i:=l+1 to r do {
j:= i;
while (j > l) and (A[j-1] > A[i]) do {
j--;
}
move(A[i], A[j]);
}
}
| |
Variante | 3.b (rekursiv) |
Typ | alternativ, optimiert |
Eigenschaften | rekursiv, in-place, stabil, nicht parallelisierbar |
Datenstrukturen | doppeltverkettete Listen, Felder |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(n) | Θ(n²) | Ο(n²) |
Vergleiche | n | n²/4 | n²/2 |
Verschiebungen | 0 | n | n |
insertsort(field A, int l, int r) {
if (l < r) then {
insertsort(A, l, r-1);
insert(A, l, r, r);
}
}
insert(field A, int l, int r, int q) {
if (l < r) and (A[r-1] > A[q]) then {
insert(A, l, r-1, q);
} else {
move(A[q], A[r]);
}
}
| |
Insertsort, Variante 3
|