Hierbei handelt es sich um eine verbesserte Variante. Trotz dieser Verbesserung ist eine iterative Realisierung möglich (vgl. Bubblesort).
Die Idee ist einfach: Wenn ein Element an der richtigen Stelle platziert wurde, dann ist der "Einfügevorgang" beendet.
Diese Variante läßt sich analog zu Variante 1 parallelisieren.
Diese Variante ist bekannter als die echte Standard-Variante. Wundern sie sich also nicht, wenn Ihnen woanders nur diese Variante geboten wird.
Variante | 2.a (iterativ) |
Typ | optimiert |
Eigenschaften | iterativ, in-place, stabil, parallelisierbar |
Datenstrukturen | Felder, doppeltverkettete Listen |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit (p) | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(n) | Θ(n²) | Ο(n²) |
Vergleiche | n | n²/4 | n²/2 |
Vertauschungen | 0 | n²/4 | n²/2 |
insertsort(field A, int l, int r) {
for i:=l+1 to r do pipelined {
j:= i;
while ((j > l) and (A[j-1] > A[j])) do {
exchange(A[j-1], A[j]);
j--;
}
}
}
| |
Variante | 2.b (rekursiv) |
Typ | optimiert |
Eigenschaften | rekursiv, in-place, stabil, nicht parallelisierbar |
Datenstrukturen | Felder, doppeltverkettete Listen |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit (p) | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(n) | Θ(n²) | Ο(n²) |
Vergleiche | n | n²/4 | n²/2 |
Vertauschungen | 0 | n²/4 | n²/2 |
insertsort(field A, int l, int r) {
if (l < r) then {
do pipelined {
insertsort(A, l, r-1);
insert(A, l, r);
}
}
}
insert(field A, int l, int r) {
if (l < r) and (A[r-1] > A[r]) then {
exchange(A[r-1], A[r]);
insert(A, l, r-1);
}
}
| |
Insertsort, Variante 2
|