|
Hierbei handelt es sich um die Original-Variante.
Mit etwas Geschick ist diese Variante parallelisierbar. Genauere Informationen dazu finden sie in Variante 6.
| Variante | 1.a (iterativ) |
|---|
| Typ | standard |
|---|
| 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²/2 | n²/2 | n²/2 |
|---|
| Vertauschungen | 0 | n²/4 | n²/2 |
|---|
insertsort(field A, int l, int r) {
for i:=l to r-1 do pipelined {
for j:= i downto l do {
if (A[j] > A[j+1]) then {
exchange(A[j], A[j+1]);
}
}
}
}
| |
| Variante | 1.b (rekursiv) |
|---|
| Typ | standard |
|---|
| Eigenschaften | rekursiv, in-place, stabil, parallelisierbar |
|---|
| Datenstrukturen | Felder, doppeltverkettete Listen |
|---|
| Speicher | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit (p) | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
|---|
| Vergleiche | n²/2 | n²/2 | 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) then {
if (A[r-1] > A[r]) then {
exchange(A[r-1], A[r]);
}
insert(A, l, r-1);
}
}
| |
Insertsort, Variante 1
|