Wie funktioniert ein Algorithmus? Das Bubble Sort-Verfahren
Kompetenzen der Digitalen Grundbildung
- Information
Ressourcen
Kontext
Bubble Sort ist ein einfacher Sortieralgorithmus. Er vergleicht wiederholt benachbarte Elemente einer Liste und tauscht sie, falls sie in der falschen Reihenfolge stehen. Dieser Vorgang wird so lange wiederholt, bis die gesamte Liste sortiert ist. Dabei "blubbern" die größten Elemente schrittweise nach oben (an das Ende der Liste), ähnlich wie Luftblasen im Wasser aufsteigen. Daher der Name "Bubble Sort".
Einstieg
INPUT | Anschauung von Bubble Sort
Plenum
Die Lehrperson erklärt kurz und einfach den Bubble Sort-Algorithmus: “Beim Bubble Sort vergleichen wir immer zwei benachbarte Zahlen und tauschen sie, wenn die linke Zahl größer ist als die rechte. Dies wiederholen wir, bis alle Zahlen in der richtigen Reihenfolge sind.”
Die Lehrperson demonstriert den Algorithmus an der Tafel, zeigt diese Animation als Anschauungsbeispiel und erklärt zugleich den Sortiervorgang.
GRUPPENSPIEL | Bubble Sort Übung
Plenum
Nun stellen sich alle Schüler:innen oder eine Auswahl an Schüler:innen in einem Halbkreis im Klassenzimmer auf. Die Reihenfolge ist zunächst zufällig. Die gedruckten und zugeschnittenen Zahlenkärtchen werden gemischt und zufällig an die Schüler:innen verteilt. Jede:r Schüler:in soll das Kärtchen sichtbar vor sich halten. Die Lehrperson erklärt die Schritte und leitet die Schüler:innen an, die folgenden Anweisungen zu befolgen:
Erster Durchgang:
Die Lehrperson sagt: “Wir beginnen mit dem/der ersten Schüler:in auf der linken Seite und vergleichen immer zwei benachbarte Zahlen.”
- Der erste Schüler (Schüler A) zeigt seine Zahl der/dem nächsten Schüler:in (Schülerin B).
- Schüler A und Schülerin B vergleichen ihre Zahlen.
- Wenn Schüler A eine größere Zahl hat als Schülerin B, tauschen sie die Plätze. Wenn nicht, bleiben sie stehen.
- Schülerin B wiederholt den Vergleich mit der/dem nächsten Schüler:in (Schülerin C).
- Dies wird fortgesetzt, bis der/die letzte Schüler:in im Halbkreis erreicht ist.
Wiederholung der Durchgänge:
Die Lehrperson erklärt: "Wir wiederholen diesen Prozess mehrere Male, bis keine Zahlen mehr getauscht werden müssen."
Der Prozess des Vergleichens und Tauschens wird so oft wiederholt, bis die Schüler:innen keine weiteren Tauschvorgänge mehr machen müssen. Die Lehrperson beobachtet und hilft bei Bedarf, bis alle Schüler:innen ihre endgültigen Plätze gefunden haben.
Kontrolle:
Die Lehrperson überprüft mit den Schüler:innen gemeinsam, ob die Zahlen jetzt in der richtigen Reihenfolge stehen. Falls nötig, wird der Prozess noch einmal durchgeführt.
INPUT | Erklärung der Logik
Die Lehrperson erläutert die Logik des Bubble Sort noch einmal und geht auf eventuelle Fragen ein.
- Warum mussten wir so viele Durchgänge machen?
- Was passiert, wenn wir zwei Zahlen nicht tauschen, obwohl wir sollten?
Anwendung im Alltag:
Die Lehrperson gibt Beispiele, wo solche Sortieralgorithmen im Alltag angewendet werden könnten (z.B. Sortieren von Büchern nach Größe, Münzen nach Wert, Farben im Schrank, Obst nach Reifegrad etc.). Durch diese praktische Übung wird den Schüler:innen der Bubble Sort-Algorithmus auf spielerische und verständliche Weise nähergebracht.
Vertiefung:
In weiteren Durchläufen soll die Lehrperson möglichst nicht mehr eingreifen, sondern die Schüler:innen sollen selbst die Durchgänge durchspielen. Eine höhere Schwierigkeitsstufe besteht darin, die Sortierung ohne verbale Kommunikation zu schaffen.
Reflexion
Die Lehrperson diskutiert mit den Schüler:innen, wie der Prozess verlaufen ist:
- Was ist euch bei diesem Prozess aufgefallen?
- War es schwierig, die richtigen Entscheidungen zu treffen?
Weiterführende Ideen
Erweiterung des Spiels: Parameter verändern
Die Sortierung kann an anderen Parametern geübt werden. Zum Beispiel die Größe der Schüler:innen oder das Alter (von jung bis alt). Zur Vereinfachung können die Schüler:innen dafür ihr Geburtsdatum auf einen Zettel schreiben und ihn vor sich halten.
In der Volksschule lässt sich mit dieser Übung auch sehr gut die Reihenfolge des Alphabets üben.