Bubblesort
Das zweite Verfahren, das beim Kartensortieren oft erfunden wird: Statt gezielt das Minimum zu suchen, vergleicht man immer nur Nachbarn.
Die Idee
Bubblesort vergleicht der Reihe nach jedes Element mit seinem rechten Nachbarn und vertauscht die beiden, wenn sie in falscher Reihenfolge stehen.
Nach einem vollständigen Durchlauf steht das größte Element ganz rechts – es ist wie eine Blase nach oben gestiegen. Das wiederholt man, bis nichts mehr zu tauschen ist.
Ein Durchlauf mit 5 2 4 1 8:
| Vergleich | Feld | Aktion |
|---|---|---|
| 5 ↔ 2 | 5 2 4 1 8 |
tauschen |
| 5 ↔ 4 | 2 5 4 1 8 |
tauschen |
| 5 ↔ 1 | 2 4 5 1 8 |
tauschen |
| 5 ↔ 8 | 2 4 1 5 8 |
passt |
| Ende | 2 4 1 5 8 |
die 8 steht sicher hinten |
Führe die restlichen Durchläufe auf Papier durch, bis das Feld sortiert ist.
Wie viele vollständige Durchläufe brauchst du? Woran merkst du, dass du fertig bist?
Auflösung
| Durchlauf | Ergebnis |
|---|---|
| 1 | 2 4 1 5 8 |
| 2 | 2 1 4 5 8 |
| 3 | 1 2 4 5 8 |
| 4 | 1 2 4 5 8 – keine Vertauschung mehr |
Nach dem dritten Durchlauf ist das Feld sortiert. Der vierte Durchlauf stellt das fest, indem er keine einzige Vertauschung mehr vornimmt.
Genau das ist der Hinweis: Wenn ein ganzer Durchlauf ohne Vertauschung vergeht, ist das Feld sortiert.
Die einfache Fassung
Zwei Verbesserungen finden
Die Fassung oben funktioniert, macht aber unnötige Arbeit. Finde zwei unabhängige Verbesserungen.
a) Denk daran, was nach dem ersten Durchlauf schon feststeht. Muss die innere Schleife wirklich jedes Mal bis ganz nach hinten laufen?
b) Denk an deine Beobachtung von oben: Woran erkennt man, dass das Feld fertig sortiert ist?
Beschreibe beide Verbesserungen in Worten, bevor du sie umsetzt.
Auflösung a): die innere Schleife verkürzen
Nach dem ersten Durchlauf steht das größte Element sicher ganz rechts. Nach dem zweiten die beiden größten. Die innere Schleife muss also in jedem Durchlauf eine Position weniger prüfen:
for (int i = 0; i < pWerte.length - 1 - durchlauf; i++) {Damit halbiert sich die Anzahl der Vergleiche ungefähr.
Auflösung b): früh abbrechen
Merke dir in einer boolean-Variablen, ob in einem Durchlauf überhaupt getauscht wurde. Wenn nicht, ist das Feld sortiert und du kannst aufhören:
boolean getauscht = true;
int durchlauf = 0;
while (getauscht) {
getauscht = false;
for (...) {
if (...) {
// tauschen
getauscht = true;
}
}
durchlauf++;
}Bei einem bereits sortierten Feld braucht das Verfahren damit nur einen Durchlauf statt n − 1.
Die verbesserte Fassung
Führe das Programm aus und erkläre die drei Ergebnisse.
Warum braucht das bereits sortierte Feld genau einen Durchlauf – und nicht null?
Auflösung
- unsortiert: 4 Durchläufe
- sortiert: 1 Durchlauf
- rückwärts: 5 Durchläufe
Null Durchläufe sind unmöglich: Man muss mindestens einmal hinschauen, um festzustellen, dass nichts zu tun ist. Dieser eine Durchlauf ist der Preis dafür, dass der Algorithmus nichts über die Daten voraussetzt.
Das rückwärts sortierte Feld ist der schlechteste Fall: Jedes Element muss einzeln durch das ganze Feld wandern.
Zwei Verfahren vergleichen
Du kennst jetzt zwei Sortierverfahren. Vergleiche sie.
a) Wie viele Vergleiche macht jedes im schlechtesten Fall?
b) Wie viele Vertauschungen?
c) Welches Verfahren ist im besten Fall schneller? Was ist der beste Fall bei jedem der beiden?
d) Beurteile: Welches würdest du wofür einsetzen?
Auflösung
| Sortieren durch Auswählen | Bubblesort (verbessert) | |
|---|---|---|
| Vergleiche, schlechtester Fall | n·(n−1)/2 | n·(n−1)/2 |
| Vertauschungen, schlechtester Fall | n − 1 | n·(n−1)/2 |
| bester Fall | immer gleich viele Vergleiche | ein Durchlauf, also n − 1 Vergleiche |
| bester Fall ist… | gibt es nicht – das Verfahren merkt nie, dass es fertig ist | ein bereits sortiertes Feld |
d) Beides sind quadratische Verfahren, für große Datenmengen also beide ungeeignet. Aber:
- Sortieren durch Auswählen ist gut, wenn Vertauschungen teuer sind – etwa weil die Elemente groß sind oder auf einer Festplatte liegen. Es macht nie mehr als n − 1 davon.
- Bubblesort ist gut, wenn die Daten fast sortiert sind. Dann erkennt es das nach einem Durchlauf.
Dass es kein bestes Verfahren gibt, sondern nur passende, ist eine Erkenntnis, die dich durch die ganze Informatik begleitet.
Aufgabe: Selbst implementieren
Setze beide Verbesserungen um, sodass alle Tests grün werden.
Tipp: sortiere aus sortiereUndZaehle bauen
Schreib erst sortiereUndZaehle vollständig. Dann besteht sortiere aus einer einzigen Zeile:
public void sortiere(int[] pWerte) {
sortiereUndZaehle(pWerte);
}Das Ergebnis wird einfach nicht weiterverwendet.
Zusatzaufgabe
Bubblesort lässt sich auch in die andere Richtung laufen lassen: Statt das größte Element nach rechts zu schieben, kann man das kleinste nach links schieben.
Kombiniert man beides und lässt die Durchläufe abwechselnd nach rechts und nach links laufen, entsteht Shakersort.
a) Setze Shakersort um.
b) Vergleiche die Anzahl der Durchläufe mit dem normalen Bubblesort bei dem Feld 2 3 4 5 1. Wo ist der Unterschied besonders groß, und warum?