Hierbei handelt es sich um eine geringfügig verbesserte Variante.
Die Idee ist einfach: Wenn keine einzige Vertauschung mehr nötig ist, so ist das Feld fertig sortiert.
Weitere Vergleiche würden keine neuen Erkenntnisse bringen. Der Algorithmus kann vorzeitig beendet werden (vorzeitiger Abbruch).
Im Normalfall ist der Gewinn minimal.
Variante | 2.a (iterativ) |
Typ | optimiert |
Eigenschaften | iterativ, in-place, stabil, nicht parallelisierbar |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit | Ω(n) | Θ(n²) | Ο(n²) |
Vergleiche | n | n²/2 | n²/2 |
Vertauschungen | 0 | n²/4 | n²/2 |
bubblesort(field A, int l, int r) {
for i:=r downto l+1 do {
flipped:= false;
for j:=l to i-1 do {
if (A[j] > A[j+1]) then {
exchange(A[j], A[j+1]);
flipped:= true;
}
}
if (not flipped) then {
return;
}
}
}
| |
Variante | 2.b (rekursiv) |
Typ | optimiert |
Eigenschaften | rekursiv, in-place, stabil, nicht parallelisierbar |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(n) | Θ(n²) | Ο(n²) |
Vergleiche | n | n²/2 | n²/2 |
Vertauschungen | 0 | n²/4 | n²/2 |
bubblesort(field A, int l, int r) {
if (l < r) then {
if bubble(A, l, r) then {
bubblesort(A, l, r-1);
}
}
}
boolean bubble(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 bubble(A, l+1, r) or flipped;
}
}
| |
Bubblesort, Variante 2
|