|
Hierbei handelt es sich um eine verbesserte Variante. Aufgrund dieser Verbesserung ist eine iterative Realisierung nichtmehr möglich.
Die Idee ist einfach: Einige Elemente wurden bereits nach oben gebubbelt, bevor ein noch größeres
Element gefunden wurde. Die bis dahin gewonnenen Informationen werden nun berücksichtigt und nicht einfach weggeworfen.
Die Idee der Variante 2 ist hier implizit enthalten.
Diese Variante läßt sich analog zu Variante 1 parallelisieren. Jedoch läßt sich dies' nicht im u.a. Code darstellen.
| Variante | 3.a (halbiterativ) |
|---|
| Typ | optimiert |
|---|
| Eigenschaften | halbiterativ, in-place, stabil, parallelisierbar |
|---|
| Datenstrukturen | Felder, einfachverkettete Listen |
|---|
| Speicher | Ω(1) | Θ(n) | Ο(n) |
|---|
| Laufzeit (p) | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit | Ω(n) | Θ(n²) | Ο(n²) |
|---|
| Vergleiche | n | n²/4 | n²/2 |
|---|
| Vertauschungen | 0 | n²/4 | n²/2 |
|---|
bubblesort(field A, int l, int r) {
while (l < r) do {
r:= bubble(A, l, r);
}
}
int bubble(field A, int l, int r) {
for i:=l to r-1 do {
if (A[i] > A[i+1]) then {
exchange(A[i], A[i+1]);
} else {
r:= bubble(A i+1, r);
i--;
}
}
return r-1;
}
| |
| Variante | 3.b (rekursiv) |
|---|
| Typ | optimiert |
|---|
| 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 | n²/4 | n²/2 |
|---|
| Vertauschungen | 0 | n²/4 | n²/2 |
|---|
bubblesort(field A, int l, int r) {
if (l < r) then {
r:= bubble(A, l, r);
bubblesort(A, l, r);
}
}
int bubble(field A, int l, int r) {
if (l < r) then {
if (A[l] > A[l+1]) then {
exchange(A[l], A[l+1]);
r:= bubble(A, l+1, r);
} else {
r:= bubble(A, l+1, r);
r:= bubble(A, l, r);
}
return r;
} else {
return r-1;
}
}
| |
Bubblesort, Variante 3
|