|
Hierbei handelt es sich um eine Alternative zu Variante 3, die besonders für einfachverkettete Listen geeignet ist.
| Variante | 4.a (iterativ) |
|---|
| Typ | alternativ, optimiert |
|---|
| Eigenschaften | iterativ, in-place, stabil, nicht parallelisierbar |
|---|
| Datenstrukturen | einfachverkettete 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:= l;
while (j < i) and (A[j] <= A[i]) do {
j++;
}
move(A[i], A[j]);
}
}
| |
| Variante | 4.b (rekursiv) |
|---|
| Typ | alternativ, optimiert |
|---|
| Eigenschaften | rekursiv, in-place, stabil, nicht parallelisierbar |
|---|
| Datenstrukturen | einfachverkettete 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[l] <= A[q]) then {
insert(A, l+1, r, q);
} else {
move(A[q], A[l]);
}
}
| |
Insertsort, Variante 4
|