|
Hierbei handelt es sich um die Original-Variante.
Analog zu Bubblesort (Variante 3 und 4) sind einige Optimierungen möglich.
| Variante | 1.a (iterativ) |
|---|
| Typ | standard |
|---|
| Eigenschaften | iterativ, in-place, stabil, nicht parallelisierbar |
|---|
| Datenstrukturen | Felder, einfachverkettete Listen |
|---|
| Speicher | Ω(1) | Θ(1) | Ο(1) |
|---|
| Laufzeit | Ω(n) | Θ(n²) | Ο(n²) |
|---|
| Vergleiche | n | n² | n² |
|---|
| Vertauschungen | 0 | n²/4 | n²/2 |
|---|
ripplesort(field A, int l, int r) {
do {
flipped:= false;
for i:=l to r-1 do {
if (A[i] > A[i+1]) then {
exchange(A[i], A[i+1]);
flipped:= true;
}
}
} while (flipped = true);
}
| |
| Variante | 1.b (rekursiv) |
|---|
| Typ | standard |
|---|
| Eigenschaften | rekursiv, in-place, stabil, nicht parallelisierbar |
|---|
| Datenstrukturen | Felder, einfachverkettete Listen |
|---|
| Speicher | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit | Ω(n) | Θ(n²) | Ο(n²) |
|---|
| Vergleiche | n | n² | n² |
|---|
| Vertauschungen | 0 | n²/4 | n²/2 |
|---|
ripplesort(field A, int l, int r) {
if (ripple(A, l, r) = true) then {
ripplesort(A, l, r);
}
}
boolean ripple(field A, int l, int r) {
if (l < r) then {
if (A[l] > A[l+1]) then {
exchange(A[l], A[l+1]);
flipped:= true;
} else {
flipped:= false;
}
return (ripple(A, l+1, r) or flipped);
}
}
| |
Ripplesort, Variante 1
|