Informatik · Klasse 13

Ideen für aktives Lernen

Sortierverfahren im Vergleich

Aktives Ausprobieren hilft hier, weil abstrakte Konzepte wie Zeit- und Platzkomplexität durch direkte Beobachtung greifbar werden. Schülerinnen und Schüler erkennen selbst, warum bestimmte Algorithmen in bestimmten Situationen besser funktionieren, statt sie nur auswendig zu lernen.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Algorithmen
• KMK: Sekundarstufe II - Modellieren und Implementieren

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

Aktivität 01

• Forschungskreis
• 45 Min. · Partnerarbeit

Paarprogrammierung: Quicksort implementieren

Paare coden Quicksort in Python oder Java, wählen einen Pivot und testen mit sortierten, umgekehrten und zufälligen Arrays. Sie messen Laufzeiten mit timeit und notieren Beobachtungen. Abschließend diskutieren sie Optimierungen.

Vergleichen Sie die Zeit- und Platzkomplexität verschiedener Sortieralgorithmen.

Moderationstipp

Beobachten Sie während der Paarprogrammierung gezielt, wie die Schülerinnen und Schüler den Pivot-Wert wählen und wie sie mit Rekursion umgehen.

Worauf zu achten ist

Stellen Sie den Schülern ein kleines Array (z.B. 5-7 Elemente) vor. Bitten Sie sie, die Schritte von Quicksort mit einem selbst gewählten Pivot und die Schritte von Mergesort manuell durchzuführen und das Ergebnis zu notieren. Vergleichen Sie die Anzahl der durchgeführten Vergleiche und Zuweisungen.

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

Aktivität 02

• Forschungskreis
• 60 Min. · Kleingruppen

Gruppenvergleich: Algorithmus-Turnier

Gruppen implementieren Quicksort und Mergesort, generieren Datensätze (z. B. 1000-10000 Elemente) und vergleichen Laufzeiten in einer Tabelle. Sie visualisieren Ergebnisse mit Matplotlib und ziehen Empfehlungen.

Erklären Sie die Funktionsweise von Quicksort und Mergesort.

Moderationstipp

Bilden Sie heterogene Gruppen beim Algorithmus-Turnier, um unterschiedliche Perspektiven auf die Performance-Vergleiche zu fördern.

Worauf zu achten ist

Geben Sie den Schülern hypothetische Szenarien: 'Ein Datensatz ist bereits fast vollständig sortiert.' oder 'Ein Datensatz enthält viele Duplikate.' Lassen Sie sie in Kleingruppen diskutieren und begründen, welcher Algorithmus (Quicksort mit bestimmter Pivot-Strategie oder Mergesort) hier voraussichtlich besser performt und warum.

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

Aktivität 03

• Forschungskreis
• 50 Min. · Ganze Klasse

Klassenexperiment: Worst-Case-Simulation

Die Klasse simuliert Worst-Case für Quicksort mit physischen Kartenstapeln, partitioniert nach Pivot und misst Schritte. Danach kodieren sie es und vergleichen mit Mergesort.

Analysieren Sie, welcher Sortieralgorithmus sich am besten für spezifische Datensätze eignet.

Moderationstipp

Stellen Sie beim Experiment im Klassenverband sicher, dass jede Gruppe systematisch die Datensätze variiert und ihre Beobachtungen strukturiert protokolliert.

Worauf zu achten ist

Jeder Schüler erhält eine Karte mit einer Big-O-Notation (z.B. O(n log n) average, O(n^2) worst). Sie sollen den Algorithmus (Quicksort oder Mergesort) nennen, der typischerweise zu dieser Komplexität führt, und eine kurze Begründung für die Wahl des Algorithmus für einen großen, zufälligen Datensatz geben.

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

Aktivität 04

• Forschungskreis
• 30 Min. · Einzelarbeit

Individuelle Analyse: Komplexitätsrechner

Jeder Schüler erstellt eine Tabelle mit Big-O für verschiedene Algorithmen und bewertet sie für Szenarien wie fast sortierte Daten. Sie begründen Wahlkriterien schriftlich.

Vergleichen Sie die Zeit- und Platzkomplexität verschiedener Sortieralgorithmen.

Moderationstipp

Fordern Sie die Lernenden beim individuellen Komplexitätsrechner auf, ihre Berechnungen nicht nur numerisch, sondern auch grafisch zu dokumentieren.

Worauf zu achten ist

Stellen Sie den Schülern ein kleines Array (z.B. 5-7 Elemente) vor. Bitten Sie sie, die Schritte von Quicksort mit einem selbst gewählten Pivot und die Schritte von Mergesort manuell durchzuführen und das Ergebnis zu notieren. Vergleichen Sie die Anzahl der durchgeführten Vergleiche und Zuweisungen.

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

Einige Hinweise zum Unterrichten dieser Einheit

Erfahrene Lehrkräfte starten mit einer visuellen Demonstration der Algorithmen, bevor die Schüler selbst aktiv werden. Wichtig ist, dass sie explizit auf die Rolle des Pivots und der Rekursion eingehen, ohne zu sehr ins Detail zu gehen. Vermeiden Sie es, die Algorithmen nur theoretisch zu erklären – praktische Anwendung und Reflexion führen zu nachhaltigem Verständnis.

Erfolgreiches Lernen zeigt sich daran, dass Lernende selbstständig die Vor- und Nachteile von Quicksort und Mergesort begründen können und gezielt den passenden Algorithmus für gegebene Datensätze auswählen. Sie nutzen Fachsprache korrekt und analysieren Komplexität mit Big-O-Notation fundiert.

---

Vorsicht vor diesen Fehlvorstellungen

• Während der Paarprogrammierung Quicksort implementieren, achten Sie darauf, ob die Schüler annehmen, Quicksort sei immer der schnellste Algorithmus.

  Nutzen Sie die Implementierungsphase, um bewusst den Worst-Case (z. B. bereits sortierte Daten) zu testen und die Performance zu vergleichen. Diskutieren Sie anschließend in der Klasse, warum Pivot-Strategien entscheidend sind.

• Während des Algorithmus-Turniers beobachten Sie, ob Lernende annehmen, Mergesort verbrauche immer unnötig viel Speicher.

  Lassen Sie die Gruppen im Turnier explizit den Speicherbedarf beider Algorithmen dokumentieren und vergleichen. Zeigen Sie, wie Mergesort in der Praxis durch optimierte Implementierungen Speicher sparen kann.

• Während des Klassenexperiments Worst-Case-Simulation kann der Eindruck entstehen, die Komplexität sei unabhängig vom Datentyp.

  Fügen Sie bewusst Datensätze mit verschiedenen Typen (Zahlen, Strings, Objekte) in das Experiment ein. Lassen Sie die Schüler analysieren, wie sich die Vergleichsoperationen auf die Laufzeit auswirken.

---

In dieser Übersicht verwendete Methoden

• Forschungskreis