Aktivität 01
Kartenrotation: Quicksort vs. Mergesort
Teilen Sie Kartenstapel mit Zahlen und Duplikaten aus. Gruppen sortieren nacheinander mit Quicksort (Pivot wählen, partitionieren) und Mergesort (teilen, mergen). Notieren Sie Schritte, Zeit und Stabilität. Diskutieren Sie Ergebnisse plenum.
Wann ist ein „stabiler" Sortieralgorithmus wichtig?
ModerationstippLegen Sie während der Kartenrotation zwei sichtbare Tabellen an, um die Partitionierungsschritte von Quicksort und die Merge-Schritte von Mergesort vergleichend festzuhalten.
Worauf zu achten istGeben Sie jeder Schülerin und jedem Schüler eine Karte mit einem der beiden Algorithmen (Quicksort oder Mergesort). Bitten Sie sie, zwei Sätze zu schreiben: 1. Ein Vorteil dieses Algorithmus. 2. Eine Situation, in der der andere Algorithmus besser geeignet wäre.
AnwendenAnalysierenBewertenErschaffenSozialbewusstseinEntscheidungsfähigkeit
Komplette Unterrichtsstunde erstellen→· · ·
Aktivität 02
Coding-Challenge: Laufzeit messen
Schüler implementieren beide Algorithmen in Python. Generieren Sie Zufallsdaten unterschiedlicher Größe, messen Sie Laufzeiten mit timeit. Vergleichen Sie Diagramme in Gruppen und analysieren Stabilität mit sortierten Listen.
Analysieren Sie die Divide-and-Conquer-Strategie bei Mergesort.
ModerationstippFühren Sie die Coding-Challenge mit vorgegebenen Datensätzen durch, damit alle Gruppen vergleichbare Ergebnisse erzielen und die Messung der Laufzeiten fair bleibt.
Worauf zu achten istStellen Sie die Frage: 'Warum ist Quicksort oft schneller als Mergesort, obwohl beide O(n log n) sind?' Bitten Sie die Schüler, ihre Antworten auf einem Blatt Papier zu notieren und dann mit einem Nachbarn zu vergleichen. Sammeln Sie einige Antworten im Plenum.
AnwendenAnalysierenBewertenErschaffenSozialbewusstseinEntscheidungsfähigkeit
Komplette Unterrichtsstunde erstellen→· · ·
Aktivität 03
Analyse-Stationen: Strategien vergleichen
Richten Sie Stationen ein: 1. Mergesort-Schritte zeichnen, 2. Quicksort-Pivot-Strategien testen, 3. Stabilitätsbeispiele mit farbigen Karten, 4. Laufzeitformeln ableiten. Gruppen rotieren und protokollieren.
Begründen Sie, warum Quicksort in der Praxis oft schneller ist als andere O(n log n) Algorithmen.
ModerationstippBereiten Sie für die Analyse-Stationen klare Leitfragen vor, die die Divide-and-Conquer-Strategie und die Stabilität beider Algorithmen gezielt herausarbeiten.
Worauf zu achten istLeiten Sie eine Diskussion mit der Frage: 'Stellen Sie sich vor, Sie sortieren eine Liste von Mitarbeitern nach Gehalt, aber Sie möchten, dass die Mitarbeiter mit gleichem Gehalt in der Reihenfolge ihrer Einstellung erscheinen. Welchen Sortieralgorithmus würden Sie wählen und warum?'
AnwendenAnalysierenBewertenErschaffenSozialbewusstseinEntscheidungsfähigkeit
Komplette Unterrichtsstunde erstellen→· · ·
Aktivität 04
Diskussionsrunde: Praxisanwendungen
Präsentieren Gruppen Szenarien (z.B. Namenssortierung). Begründen Sie Algorithmuswahl. Whole class stimmt ab und diskutiert.
Wann ist ein „stabiler" Sortieralgorithmus wichtig?
ModerationstippSteuern Sie die Diskussionsrunde, indem Sie gezielt Beispiele aus der Praxis einbringen, um die Relevanz der Stabilität und Laufzeit zu verdeutlichen.
Worauf zu achten istGeben Sie jeder Schülerin und jedem Schüler eine Karte mit einem der beiden Algorithmen (Quicksort oder Mergesort). Bitten Sie sie, zwei Sätze zu schreiben: 1. Ein Vorteil dieses Algorithmus. 2. Eine Situation, in der der andere Algorithmus besser geeignet wäre.
AnwendenAnalysierenBewertenErschaffenSozialbewusstseinEntscheidungsfähigkeit
Komplette Unterrichtsstunde erstellen→Einige Hinweise zum Unterrichten dieser Einheit
Erfahrene Lehrkräfte beginnen mit einer klaren Visualisierung der Algorithmen, bevor es an die Umsetzung geht. Sie vermeiden es, die Algorithmen nur theoretisch zu erklären, sondern setzen auf konkrete Beispiele und Vergleiche. Wichtig ist, die Schüler aktiv in die Analyse einzubinden und sie durch gezielte Fragen dazu zu bringen, selbst Unterschiede und Vorteile zu erkennen. Vermeiden Sie es, die Komplexität der Rekursion zu sehr zu vertiefen, sondern fokussieren Sie sich auf die praktischen Auswirkungen.
Erfolgreiches Lernen zeigt sich darin, dass die Schülerinnen und Schüler die Unterschiede zwischen Quicksort und Mergesort erklären, Laufzeitkomplexitäten vergleichen und praktische Anwendungen begründet auswählen können. Sie erkennen, wann Stabilität entscheidend ist und wie Rekursion sowie Pivotwahl die Performance beeinflussen.
Vorsicht vor diesen Fehlvorstellungen
Während der Kartenrotation beobachten viele Schüler, dass Quicksort die Reihenfolge gleichwertiger Elemente verändert.
Während der Kartenrotation leiten Sie die Schüler an, die Partitionierungsschritte von Quicksort genau zu beobachten und mit den stabilen Merge-Schritten von Mergesort zu vergleichen. Bitten Sie sie, die Positionen gleichwertiger Elemente vor und nach dem Sortieren zu markieren und die Unterschiede zu diskutieren.
Während der Coding-Challenge äußern einige Schüler die Annahme, Mergesort sei wegen der Rekursion immer langsamer.
Während der Coding-Challenge lassen Sie die Schüler die Laufzeiten beider Algorithmen auf verschiedenen Datensätzen messen und die Ergebnisse in einer gemeinsamen Tabelle sammeln. Diskutieren Sie gemeinsam, warum Mergesort trotz Rekursion in bestimmten Fällen stabiler und effizienter sein kann.
Während der Analyse-Stationen gehen einige davon aus, dass beide Algorithmen in der Praxis identische Laufzeiten haben.
Während der Analyse-Stationen konfrontieren Sie die Schüler mit realen Laufzeitdaten und Cache-Effekten. Bitten Sie sie, die Vorteile von Quicksort bei guten Pivot-Wahlen und die Stabilität von Mergesort gegenüberzustellen und die Unterschiede zu erklären.
In dieser Übersicht verwendete Methoden