- Verglichen
- Getauscht
- Platziert
Bubblesort
Bubblesort geht eine Liste immer wieder durch, vergleicht jedes Paar von Nachbarn und tauscht sie, wenn der linke Wert größer ist. Nach jedem Durchlauf ist der größte noch falsch stehende Wert ans Ende aufgestiegen. Spielen Sie die Sortierung in beliebigem Tempo ab oder gehen Sie sie Vergleich für Vergleich durch, und beobachten Sie die Zähler für Vergleiche, Vertauschungen und Durchläufe. Drücken Sie „Abspielen“, um die Sortierung anzusehen, oder gehen Sie mit „Schritt“ und „Zurück“ einen Vergleich nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Die Kacheln zählen Vergleiche, Vertauschungen und Durchläufe. Wählen Sie die Anzahl der Balken und ihre Startreihenfolge, oder geben Sie eigene Zahlen ein. Ist das Feld ausgewählt, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.
Wie es funktioniert
- Wählen Sie die Anzahl der Balken und ihre Startreihenfolge: zufällig, fast sortiert, umgekehrt oder mit wenigen verschiedenen Werten. Oder geben Sie eigene Zahlen ein.
- Drücken Sie „Abspielen“ oder gehen Sie mit „Schritt“ und „Zurück“ einen Vergleich nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle der Sortierung zu springen.
- Die Kacheln zählen Vergleiche, Vertauschungen und Durchläufe. Vergleichen Sie sie mit dem schlimmsten Fall.
So funktioniert Bubblesort
Beginnen Sie links. Vergleichen Sie die ersten beiden Werte; ist der linke größer, tauschen Sie sie. Gehen Sie einen Platz nach rechts und vergleichen Sie erneut, bis zum Ende der Liste. Das ist ein Durchlauf, und danach steht der größte Wert am letzten Platz. Der nächste Durchlauf endet einen Platz früher. Machen Sie weiter, bis ein Durchlauf nichts mehr tauscht oder nur noch ein Wert übrig ist.
Den Aufwand zählen
Bei n Werten macht der erste Durchlauf n − 1 Vergleiche, der nächste n − 2 und so weiter. Eine vollständige Sortierung braucht also höchstens n(n − 1)/2 Vergleiche. Die Zahl der Vertauschungen ist immer die Zahl der Inversionen in der Startliste: Paare von Werten in falscher Reihenfolge. Eine umgekehrte Liste hat die meisten, n(n − 1)/2. Eine sortierte Liste hat keine, und mit dem frühen Abbruch braucht sie nur einen Durchlauf mit n − 1 Vergleichen.
Häufig gestellte Fragen
Warum heißt es Bubblesort?
Weil große Werte wie Blasen (englisch „bubbles“) im Wasser ans Ende der Liste aufsteigen. In jedem Durchlauf wandert der größte noch nicht platzierte Wert Schritt für Schritt nach rechts, bis er seinen endgültigen Platz erreicht.
Wie viele Vergleiche und Vertauschungen macht Bubblesort?
Höchstens n(n − 1)/2 Vergleiche bei n Werten: 45 bei 10 Werten, 780 bei 40. Die Zahl der Vertauschungen entspricht immer der Zahl der Inversionen in der Startliste, von null bei einer sortierten bis n(n − 1)/2 bei einer umgekehrten Liste.
Was bewirkt der frühe Abbruch?
Wenn ein ganzer Durchlauf nichts tauscht, stehen alle Nachbarn in der richtigen Reihenfolge. Die Liste ist also sortiert, und die Sortierung kann enden. Mit frühem Abbruch braucht eine sortierte Liste einen Durchlauf. Ohne ihn macht Bubblesort immer alle n − 1 Durchläufe.
Wird Bubblesort in der Praxis verwendet?
Selten. Es ist einfach und stabil, braucht aber im Mittel Zeit proportional zu n². Insertionsort erledigt dieselbe Aufgabe bei kleinen oder fast sortierten Listen mit weniger Schritten, und Mergesort oder Quicksort sind bei großen Listen viel schneller.
Werden meine Zahlen irgendwohin gesendet?
Nein. Die Sortierung läuft in Ihrem Browser, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor