Bubble Sort Übungen
Hier können Sie Bubble Sort direkt im Browser üben – ohne Arbeitsblatt, mit sofortiger Rückmeldung. Wie der Algorithmus funktioniert, steht auf der Seite BubbleSort. Zur Erinnerung: Bubble Sort vergleicht immer zwei benachbarte Elemente. Ist das linke größer als das rechte, werden die beiden getauscht.
Die Positionen im Array zählen wir ab 0: Das erste Element ist array[0]. Bei den meisten Übungen gibt es den Knopf »Neue Werte« bzw. »Nächste Aufgabe« – Sie können also so lange üben, wie Sie möchten. Gespeichert wird nichts.
Der Größte-Zahl-ans-Ende-Algorithmus
(1) Schritt für Schritt: Die größte Zahl nach hinten bringen
Das sind die Lottozahlen vom Arbeitsblatt. Entscheiden Sie bei jedem Vergleich: tauschen oder nicht? Am Ende muss die größte Zahl ganz rechts stehen.
(2) Tabelle: Größte Zahl ans Ende
Jetzt ohne Hilfe: Tragen Sie nach jedem Vergleich ein, wie das Array aussieht. Mit »Prüfen« sehen Sie, welche Einträge stimmen – und bei jeder richtigen Zeile, welche beiden Zahlen verglichen und ob sie getauscht wurden.
Das ganze Array sortieren
Was ist eine Bubble-Phase?
Eine Bubble-Phase ist ein kompletter Durchlauf des Größte-Zahl-ans-Ende-Algorithmus durch den noch unsortierten Teil des Arrays: Man vergleicht von links nach rechts jeweils zwei Nachbarn und tauscht sie, wenn der linke größer ist. Am Ende der Bubble-Phase ist die größte noch unsortierte Zahl ganz nach hinten »geblubbert« und steht an ihrem endgültigen Platz. (Auf der Seite BubbleSort heißt eine Bubble-Phase noch »Durchgang«.)
- Jede Bubble-Phase ist um einen Vergleich kürzer als die vorige – hinten wird der sortierte Bereich immer größer.
- Ein Array mit n Elementen braucht n − 1 Bubble-Phasen, dann ist es sortiert.
(3) Schritt für Schritt: Bubble Sort komplett
Jetzt alle Bubble-Phasen. Oben sehen Sie, in welcher Bubble-Phase Sie gerade sind. Der grau dargestellte Bereich ist schon fertig sortiert – dort wird nicht mehr verglichen.
(4) Münzen sortieren
Sortieren Sie die Münzen mit Bubble Sort nach ihrem Wert – die wertvollste Münze soll am Ende ganz rechts liegen. Verglichen werden immer die beiden grün umrandeten Münzen. Muss getauscht werden, ziehen Sie die linke Münze auf die rechte (auf dem Handy: mit dem Finger ziehen oder beide Münzen nacheinander antippen).
(5) Tabelle: Namensliste sortieren
Die Namensliste vom Arbeitsblatt – diesmal online. Sortieren Sie die Namen alphabetisch mit Bubble Sort und tragen Sie nach jedem Vergleich den Zustand ein.
(6) Tabelle: Ergebnis nach jeder Bubble-Phase
Wie in der Klassenarbeit: Tragen Sie das Ergebnis nach den einzelnen Bubble-Phasen ein. Mit »Neue Werte« bekommen Sie ein neues Array.
Bubble Sort verstehen
(7) Wie oft wird verglichen?
Wie viele Bubble-Phasen, wie viele Vergleiche, wie viele Vertauschungen? Rechnen Sie, bevor Sie »Prüfen« drücken – danach sehen Sie die Lösung an einem ausführlichen Beispiel.
(8) Münzen nach der Bubble-Phase hinlegen
Oben sehen Sie, wie die Münzen am Anfang liegen. Spielen Sie die Bubble-Phase im Kopf durch und ziehen Sie dann die Münzen vom Haufen auf die Array-Plätze, an denen sie danach liegen. (Auf dem Handy: Münze antippen, dann den Platz antippen.)
(9) Fehler finden
Hier wurde nach jeder Bubble-Phase notiert, wie das Array aussieht – aber einmal ist etwas schiefgegangen.