|
Hierbei handelt es sich um die Original-Variante.
Analog zu Bubblesort (Variante 3) sind hier ebenfalls einige Optimierungen möglich. Die Realisierung wäre jedoch etwas komplizierter.
Mit etwas Geschick ist diese Variante parallelisierbar. Genauere Informationen dazu finden sie in Variante 4.
| Variante | 1.a (iterativ) |
|---|
| Typ | standard |
|---|
| Eigenschaften | iterativ, in-place, stabil, parallelisierbar |
|---|
| Datenstrukturen | Felder, einfachverkettete Listen |
|---|
| Speicher | Ω(1) | Θ(1) | Ο(1) |
|---|
| Laufzeit (p) | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
|---|
| Vergleiche | n²/2 | n²/2 | n²/2 |
|---|
| Vertauschungen | 0 | n²/16 | n²/2 |
|---|
simplesort(field A, int l, int r) {
for i:=r downto l+1 do pipelined {
for j:=l to i-1 do {
if (A[j] >= A[i]) then {
exchange(A[j], A[i]);
}
}
}
}
| |
| Variante | 1.b (rekursiv) |
|---|
| Typ | standard |
|---|
| Eigenschaften | rekursiv, in-place, stabil, parallelisierbar |
|---|
| Datenstrukturen | Felder, einfachverkettete Listen |
|---|
| Speicher | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit (p) | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
|---|
| Vergleiche | n²/2 | n²/2 | n²/2 |
|---|
| Vertauschungen | 0 | n²/16 | n²/2 |
|---|
simplesort(field A, int l, int r) {
if (l < r) then {
do pipelined {
simple(A, l, r);
simplesort(A, l, r-1);
}
}
}
simple(field A, int l, int r) {
if (l < r) then {
if (A[l] >= A[r]) then {
exchange(A[l], A[r]);
}
simple(A, l+1, r);
}
}
| |
Simplesort, Variante 1
|