Informatik · Klasse 11

Ideen für aktives Lernen

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.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Algorithmen entwerfen
• KMK: Sekundarstufe II - Implementieren

• 30–50 Min.
• Partnerarbeit → Ganze Klasse
• 4 Aktivitäten

Aktivität 01

• 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.

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.

Worauf zu achten ist

Stellen Sie den Schülern eine Liste mit 10 unsortierten Zahlen vor. Bitten Sie sie, die ersten beiden Schritte des Merge Sort Algorithmus auf Papier zu skizzieren, einschließlich der Aufteilung und der ersten Merge-Operation. Überprüfen Sie, ob die Aufteilung korrekt erfolgt und die erste Zusammenführung logisch ist.

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

Aktivität 02

• 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.

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.

Worauf zu achten ist

Leiten Sie eine Diskussion über die Speicherintensität von Rekursion. Fragen Sie: 'Unter welchen Umständen könnte ein rekursiver Quick Sort mehr Speicher verbrauchen als ein iterativer Bubble Sort, obwohl Quick Sort im Durchschnitt schneller ist? Geben Sie ein Beispiel für eine Datenanordnung, die dieses Szenario auslöst.'

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

Aktivität 03

• 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.

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.

Worauf zu achten ist

Geben Sie jedem Schüler eine Karte mit einem der beiden Algorithmen (Merge Sort oder Quick Sort). Bitten Sie die Schüler, auf der Karte eine Stärke und eine Schwäche des ihnen zugewiesenen Algorithmus für die Sortierung von 1 Million Datensätzen aufzuschreiben.

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

Aktivität 04

• 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.

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.

Worauf zu achten ist

Stellen Sie den Schülern eine Liste mit 10 unsortierten Zahlen vor. Bitten Sie sie, die ersten beiden Schritte des Merge Sort Algorithmus auf Papier zu skizzieren, einschließlich der Aufteilung und der ersten Merge-Operation. Überprüfen Sie, ob die Aufteilung korrekt erfolgt und die erste Zusammenführung logisch ist.

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

Einige Hinweise zum Unterrichten dieser Einheit

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.

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

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

  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.

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

  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.

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

  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.

---

In dieser Übersicht verwendete Methoden

• Problemorientiertes Lernen