Informatik · Klasse 11

Ideen für aktives Lernen

Sortieralgorithmen: Bubble Sort und Selection Sort

Sortieralgorithmen wie Bubble Sort und Selection Sort sind ideal für aktive Lernformen, weil Schülerinnen und Schüler durch manuelle Simulationen und Programmierung ein tiefes Verständnis für die zugrundeliegenden Mechanismen entwickeln. Die kleinen Datenmengen ermöglichen es ihnen, jeden Schritt nachzuvollziehen und die Effizienz selbst zu erleben, statt sie nur theoretisch zu diskutieren.

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

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

Aktivität 01

• Erfahrungsorientiertes Lernen
• 30 Min. · Kleingruppen

Karten-Simulation: Bubble Sort

Teilen Sie Gruppen Karten mit Zahlen aus. Jede Gruppe simuliert Bubble Sort: Vergleichen Sie benachbarte Karten, tauschen Sie bei Bedarf und zählen Sie Schritte. Notieren Sie Iterationen pro Durchgang. Diskutieren Sie am Ende die Anzahl der Vertauschungen.

Warum ist Sortieren eine der wichtigsten Operationen in der Informatik?

Moderationstipp

Während der Karten-Simulation von Bubble Sort: Fordern Sie die Schülerinnen und Schüler auf, jede Vertauschung laut auszusprechen, um den Prozess zu verinnerlichen.

Worauf zu achten ist

Geben Sie den Schülerinnen und Schülern eine kleine unsortierte Zahlenliste (z.B. 7 Elemente). Bitten Sie sie, die ersten beiden Schritte von Bubble Sort und Selection Sort manuell durchzuführen und die Anzahl der Vergleiche und Vertauschungen zu notieren. Vergleichen Sie die Ergebnisse im Plenum.

• Anwenden
• Analysieren
• Bewerten
• Selbstwahrnehmung
• Selbststeuerung
• Sozialbewusstsein

Aktivität 02

• Erfahrungsorientiertes Lernen
• 45 Min. · Partnerarbeit

Programmier-Duell: Selection Sort

Paare implementieren Selection Sort in Python oder einer Blockprogrammierumgebung. Testen Sie mit Arrays unterschiedlicher Größe und messen Sie Ausführungszeit mit time-Modul. Vergleichen Sie Ergebnisse in einer Klassentabelle.

Vergleichen Sie die Funktionsweise und Effizienz von Bubble Sort und Selection Sort.

Moderationstipp

Beim Programmier-Duell: Lassen Sie die Schülerinnen und Schüler ihre Lösungen gegenseitig testen, um Fehlerquellen wie Edge-Cases zu identifizieren.

Worauf zu achten ist

Lassen Sie die Schülerinnen und Schüler auf einem Zettel zwei Sätze schreiben: 1. Beschreiben Sie einen Fall, in dem Bubble Sort besser geeignet sein könnte als Selection Sort. 2. Beschreiben Sie einen Fall, in dem Selection Sort besser geeignet sein könnte als Bubble Sort.

• Anwenden
• Analysieren
• Bewerten
• Selbstwahrnehmung
• Selbststeuerung
• Sozialbewusstsein

Aktivität 03

• Erfahrungsorientiertes Lernen
• 50 Min. · Ganze Klasse

Effizienz-Vergleich: Rennen der Algorithmen

Ganzer Klassenraum: Jede Reihe implementiert einen Algorithmus, testet mit zufälligen Daten und präsentiert Grafiken der Laufzeiten. Stimmen Sie über den Gewinner bei n=10 ab und analysieren Sie Gründe.

Analysieren Sie, welcher Algorithmus bei sehr kleinen Datenmengen am effizientesten ist.

Moderationstipp

Beim Effizienz-Vergleich: Geben Sie den Schülerinnen und Schülern Stoppuhren, um die Laufzeitunterschiede bei gleichen Datenmengen zu messen.

Worauf zu achten ist

Diskutieren Sie folgende Frage: Wenn Sie eine Liste mit nur 3 Elementen sortieren müssten, welcher der beiden Algorithmen wäre wahrscheinlich am schnellsten und warum? Begründen Sie Ihre Antwort anhand der Funktionsweise der Algorithmen.

• Anwenden
• Analysieren
• Bewerten
• Selbstwahrnehmung
• Selbststeuerung
• Sozialbewusstsein

Aktivität 04

• Erfahrungsorientiertes Lernen
• 20 Min. · Einzelarbeit

Schritt-für-Schritt: Manuelle Analyse

Individuell: Zeichnen Sie Arrays und führen Sie beide Algorithmen auf Papier aus. Zählen Sie Vergleiche und Vertauschungen. Teilen Sie Diagramme in Kleingruppen.

Warum ist Sortieren eine der wichtigsten Operationen in der Informatik?

Moderationstipp

Bei der manuellen Analyse: Bitten Sie die Schülerinnen und Schüler, ihre Ergebnisse in einer Tabelle festzuhalten, um Muster zu erkennen.

Worauf zu achten ist

Geben Sie den Schülerinnen und Schülern eine kleine unsortierte Zahlenliste (z.B. 7 Elemente). Bitten Sie sie, die ersten beiden Schritte von Bubble Sort und Selection Sort manuell durchzuführen und die Anzahl der Vergleiche und Vertauschungen zu notieren. Vergleichen Sie die Ergebnisse im Plenum.

• Anwenden
• Analysieren
• Bewerten
• Selbstwahrnehmung
• Selbststeuerung
• Sozialbewusstsein

Einige Hinweise zum Unterrichten dieser Einheit

Erfahrene Lehrkräfte beginnen mit einer klaren Demonstration der Algorithmen an der Tafel oder am Beamer, bevor die Schülerinnen und Schüler selbst aktiv werden. Wichtig ist, dass sie die Gemeinsamkeiten beider Algorithmen – insbesondere die quadratische Laufzeit – hervorheben und gleichzeitig die Unterschiede in der Anzahl der Vertauschungen betonen. Vermeiden Sie es, die Algorithmen als 'schlecht' darzustellen, da sie für kleine Datenmengen durchaus praktisch sind. Nutzen Sie Alltagsbeispiele wie das Sortieren von Spielkarten oder Büchern, um die Relevanz zu verdeutlichen.

Erfolgreiches Lernen zeigt sich, wenn Schülerinnen und Schüler nicht nur die Schritte der Algorithmen beschreiben, sondern auch ihre Effizienz in verschiedenen Szenarien vergleichen und begründen können. Sie erkennen, dass beide Algorithmen für kleine Datenmengen geeignet sind, aber unterschiedliche Vor- und Nachteile haben.

---

Vorsicht vor diesen Fehlvorstellungen

• During [Karten-Simulation: Bubble Sort], watch for Schülerinnen und Schüler, die annehmen, Bubble Sort sei immer langsamer als Selection Sort.

  Nutzen Sie die Simulation mit echten Karten, um die Schülerinnen und Schüler die Anzahl der Vertauschungen selbst zählen zu lassen. Zeigen Sie, dass bei kleinen Datenmengen beide Algorithmen ähnlich effizient sind und Selection Sort sogar mehr Vergleiche benötigt.

• During [Programmier-Duell: Selection Sort], watch for Schülerinnen und Schüler, die glauben, Algorithmen sortieren immer fehlerfrei.

  Fordern Sie die Schülerinnen und Schüler auf, ihre Programme mit verschiedenen Eingaben zu testen, insbesondere mit bereits sortierten oder umgekehrten Listen. Diskutieren Sie gemeinsam, warum Edge-Cases wichtig sind und wie man sie erkennt.

• During [Effizienz-Vergleich: Rennen der Algorithmen], watch for Schülerinnen und Schüler, die annehmen, mehr Iterationen bedeuten immer schlechtere Effizienz.

  Nutzen Sie die gemessenen Laufzeiten und Vergleichszahlen aus dem Rennen, um zu zeigen, dass beide Algorithmen O(n²) Komplexität haben. Betonen Sie, dass die Anzahl der Vergleiche und Vertauschungen bei kleinen n ähnlich ist.

---

In dieser Übersicht verwendete Methoden

• Erfahrungsorientiertes Lernen