Sortieralgorithmen: Merge Sort und Quick Sort

Aktive Lernmethoden eignen sich besonders gut für Sortieralgorithmen, weil Schüler durch eigenes Handeln die abstrakten Konzepte der rekursiven Teilung und Zusammenführung konkret begreifen. Die Kombination aus physischen Materialien und digitalen Simulationen macht die Unterschiede zwischen Merge Sort und Quick Sort greifbar und reduziert so typische Verständnisschwierigkeiten bei Rekursion und Laufzeitanalyse.

• Klasse 11
• Informatik in der Oberstufe: Algorithmen, Daten und Gesellschaft
• 4 Aktivitäten
• 30 Min.–50 Min.

Lernziele

1. Erklären Sie das Divide-and-Conquer-Prinzip anhand von Merge Sort und Quick Sort.
2. Vergleichen Sie die Zeitkomplexität von Merge Sort und Quick Sort im Worst-Case- und Average-Case-Szenario.
3. Analysieren Sie die Speicheranforderungen rekursiver Algorithmen im Vergleich zu iterativen Ansätzen.
4. Implementieren Sie eine einfache Version von Merge Sort oder Quick Sort in einer Programmiersprache.
5. Bewerten Sie die Eignung von Merge Sort und Quick Sort für verschiedene Datengrößen und -verteilungen.

Problemorientiertes Lernen

⏱ 30 Min.·Partnerarbeit

Karten-Sortierung: Merge Sort

Teilen Sie Schüler in Paare auf. Jede Gruppe erhält 16 sortierbare Karten mit Zahlen. Sie teilen den Stapel rekursiv, sortieren die Hälften und mergen sie. Nach jeder Runde notieren sie Schritte und Zeit.

Vorbereitung & Details

Erklären Sie das Divide-and-Conquer-Prinzip am Beispiel von Merge Sort.

Moderationstipp: Beobachten Sie während der Karten-Sortierung genau, ob alle Schüler die Aufteilung der Listen in zwei Hälften korrekt vornehmen, bevor sie mit dem Mergen beginnen.

Setup: Gruppentische mit Zugang zu Recherchequellen

Materials: Dokumentation des Problemszenarios, KWL-Tabelle (Wissen, Wollen, Lernen) oder Inquiry-Framework, Ressourcenpool / Handapparat, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Entscheidungsfähigkeit
• Selbststeuerung
• Beziehungsfähigkeit

Problemorientiertes Lernen

⏱ 45 Min.·Kleingruppen

Quick Sort Simulation: Pivot-Wahl

In kleinen Gruppen wählen Schüler ein Pivot aus einer Liste von 20 Zahlen auf Papier, partitionieren und rekurrieren. Sie variieren die Pivot-Strategie und protokollieren Partitionen. Gruppen präsentieren eine Runde.

Vorbereitung & Details

Vergleichen Sie die Worst-Case-Szenarien von Quick Sort und Merge Sort.

Moderationstipp: Fordern Sie die Schüler bei der Quick Sort Simulation auf, ihre Pivot-Wahl zu begründen und zu dokumentieren, um das Verständnis für die Partitionierung zu vertiefen.

Setup: Gruppentische mit Zugang zu Recherchequellen

Materials: Dokumentation des Problemszenarios, KWL-Tabelle (Wissen, Wollen, Lernen) oder Inquiry-Framework, Ressourcenpool / Handapparat, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Entscheidungsfähigkeit
• Selbststeuerung
• Beziehungsfähigkeit

Problemorientiertes Lernen

⏱ 40 Min.·Einzelarbeit

Pseudocode-Implementierung: Vergleich

Individuell schreiben Schüler Pseudocode für Merge und Quick Sort. Dann diskutieren sie in Paaren Worst-Case-Beispiele und optimieren den Quick-Sort-Pivot. Gemeinsam testen sie mit Beispiellisten.

Vorbereitung & Details

Analysieren Sie, warum rekursive Algorithmen oft eleganter, aber potenziell speicherintensiver sind.

Moderationstipp: Verlangen Sie von den Schülern, ihre Pseudocode-Implementierungen gegenseitig zu prüfen, um logische Fehler früh zu identifizieren.

Setup: Gruppentische mit Zugang zu Recherchequellen

Materials: Dokumentation des Problemszenarios, KWL-Tabelle (Wissen, Wollen, Lernen) oder Inquiry-Framework, Ressourcenpool / Handapparat, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Entscheidungsfähigkeit
• Selbststeuerung
• Beziehungsfähigkeit

Problemorientiertes Lernen

⏱ 50 Min.·Ganze Klasse

Laufzeit-Messung: Programmtest

Als ganze Klasse implementieren Schüler Algorithmen in Python oder Pseudocode. Generieren zufällige Listen, messen Zeiten für verschiedene Größen und vergleichen Diagramme auf dem Beamer.

Vorbereitung & Details

Erklären Sie das Divide-and-Conquer-Prinzip am Beispiel von Merge Sort.

Moderationstipp: Messen Sie die Laufzeit beider Algorithmen mit denselben Datensätzen und fordern Sie die Schüler auf, die Unterschiede in den Ergebnissen zu interpretieren.

Setup: Gruppentische mit Zugang zu Recherchequellen

Materials: Dokumentation des Problemszenarios, KWL-Tabelle (Wissen, Wollen, Lernen) oder Inquiry-Framework, Ressourcenpool / Handapparat, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Entscheidungsfähigkeit
• Selbststeuerung
• Beziehungsfähigkeit

Dieses Thema unterrichten

Erfahrene Lehrer beginnen mit einfachen, handlungsorientierten Aktivitäten, um die Grundidee von Divide-and-Conquer zu verankern. Sie vermeiden es, sofort auf komplexe Laufzeitanalysen einzugehen, sondern lassen Schüler zunächst die Algorithmen selbst erleben. Wichtig ist, die Rekursion schrittweise einzuführen: Zuerst die Basisfälle klären, dann die rekursiven Aufrufe visualisieren. Vermeiden Sie es, zu früh über optimale Pivot-Strategien zu sprechen – konzentrieren Sie sich stattdessen auf die Auswirkungen schlechter Entscheidungen. Nutzen Sie die Rekursionsbäume als visuelles Hilfsmittel, um die Speichertiefe zu verdeutlichen.

Was Sie erwartet

Am Ende der Einheit können Schüler die beiden Algorithmen Schritt für Schritt anwenden, ihre Laufzeitkomplexität in einfachen Fällen bestimmen und Vor- und Nachteile im Kontext von Rekursion und Speicherbedarf abwägen. Zudem erkennen sie, wie kleine Änderungen der Parameter (z.B. Pivot-Wahl) das Ergebnis dramatisch beeinflussen können.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Während der Aktivität Karten-Sortierung: Merge Sort, hören Sie möglicherweise Aussagen wie 'Schnellere Sortierung geht nur mit Quick Sort'.

Was Sie stattdessen lehren sollten

Lenken Sie die Aufmerksamkeit auf die gleichmäßige Teilung der Liste und die konstante Laufzeit O(n log n) von Merge Sort. Vergleichen Sie gemeinsam die Anzahl der Operationen bei beiden Algorithmen für eine kleine Liste mit 8 Elementen.

Häufige Fehlvorstellung

Während der Quick Sort Simulation: Pivot-Wahl, könnte ein Schüler behaupten 'Rekursion macht immer Probleme' oder 'Der Algorithmus stürzt ab'.

Was Sie stattdessen lehren sollten

Fordern Sie den Schüler auf, den Rekursionsbaum für eine kleine Liste zu zeichnen und die Anzahl der Aufrufe zu zählen. Zeigen Sie, dass bei ausgewogener Partitionierung die Tiefe logarithmisch bleibt und kein Stapelüberlauf droht.

Häufige Fehlvorstellung

Während der Aktivität Pseudocode-Implementierung: Vergleich, meinen einige Schüler 'Merge Sort verändert die Reihenfolge gleicher Elemente'.

Was Sie stattdessen lehren sollten

Geben Sie den Schülern eine Liste mit Duplikaten und markierten Elementen. Lassen Sie sie die Merge-Operationen Schritt für Schritt durchführen und die Stabilität des Algorithmus überprüfen.

Ideen zur Lernstandserhebung

Kurze Überprüfung

Nach der Aktivität Karten-Sortierung: Merge Sort prüfen Sie die Skizzen der Schüler zu den ersten beiden Schritten. Achten Sie darauf, dass die Liste korrekt in Hälften geteilt wird und die erste Merge-Operation logisch durchgeführt wird.

Diskussionsfrage

Nach der Aktivität Quick Sort Simulation: Pivot-Wahl leiten Sie eine Diskussion darüber ein, warum Quick Sort in bestimmten Fällen mehr Speicher verbraucht als Bubble Sort. Die Schüler sollen Beispiele für Datenanordnungen nennen, die dieses Szenario auslösen.

Lernstandskontrolle

Nach der Aktivität Pseudocode-Implementierung: Vergleich sammeln Sie die Karten der Schüler und lesen Sie jeweils eine Stärke und Schwäche des zugewiesenen Algorithmus vor. Diskutieren Sie die Antworten im Plenum und korrigieren Sie falsche Vorstellungen.

Erweiterungen & Unterstützung

• Fordern Sie leistungsstärkere Schüler auf, eine Hybridversion aus Merge Sort und Quick Sort zu entwickeln, die die Vorteile beider Algorithmen kombiniert.
• Für Schüler mit Schwierigkeiten stellen Sie vorbereitete Rekursionsbäume mit Lücken bereit, die sie vervollständigen müssen.
• Vertiefen Sie das Thema, indem Sie die Schüler analysieren lassen, wie sich die Algorithmen bei fast sortierten Daten verhalten und welche Optimierungen möglich sind.

Schlüsselvokabular

Divide and Conquer	Ein Lösungsansatz, bei dem ein Problem in kleinere, leichter zu lösende Teilprobleme zerlegt wird, deren Lösungen dann kombiniert werden.
Rekursion	Eine Methode, bei der eine Funktion sich selbst aufruft, um ein Problem zu lösen, typischerweise mit einer Basisbedingung, die den Abbruch der Rekursion sicherstellt.
Pivot-Element	Ein Element, das bei Quick Sort ausgewählt wird, um die Partitionierung der Datenmenge in zwei Teilmengen zu steuern.
Merge-Operation	Der Prozess des Zusammenführens zweier bereits sortierter Teillisten zu einer einzigen sortierten Liste.
Rekursionsstapel	Ein Speicherbereich, der Informationen über aktive Funktionsaufrufe speichert, einschließlich lokaler Variablen und Rücksprungadressen, was bei tiefen Rekursionen zu hohem Speicherverbrauch führen kann.