Informatik · Klasse 9

Ideen für aktives Lernen

Sortierverfahren: Selection Sort

Das Sortierverfahren Selection Sort eignet sich besonders für den Einstieg in Algorithmen, weil es einfach nachvollziehbar ist und durch visuelle sowie praktische Methoden wie Simulationen oder Code-Implementierungen direkt greifbar wird. Schülerinnen und Schüler können so die abstrakten Konzepte von Vergleichen, Tauschen und Zeitkomplexität durch eigenes Handeln begreifen und nicht nur theoretisch verstehen.

• KMK Bildungsstandards
• KMK: Sekundarstufe I - Algorithmen
• KMK: Sekundarstufe I - Problemlösen

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

Aktivität 01

• Kollaboratives Problemlösen
• 30 Min. · Kleingruppen

Karten-Simulation: Selection Sort live

Teilen Sie eine gemischte Kartendeck in kleine Gruppen auf. Jede Gruppe simuliert Selection Sort, indem sie das kleinste Karten im unsortierten Stapel sucht und es vorne platziert. Notieren Sie Vertauschungen und vergleichen Sie mit einer Bubble-Sort-Runde.

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

Moderationstipp

Während der Karten-Simulation (Activity 1) achten Sie darauf, dass die Schülerinnen und Schüler jede Vergleiche und Tauschoperation laut mitzählen, um die Anzahl der Operationen klar zu erfassen.

Worauf zu achten ist

Lassen Sie die Schülerinnen und Schüler eine kleine unsortierte Zahlenliste (z.B. 5 Elemente) auf einem Arbeitsblatt manuell mit Selection Sort sortieren. Fragen Sie: 'Wie viele Vergleiche wurden in jedem Durchgang durchgeführt?' und 'Wie viele Vertauschungen gab es insgesamt?'

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

Aktivität 02

• Kollaboratives Problemlösen
• 45 Min. · Partnerarbeit

Paar-Programmierung: Implementierung

In Paaren codieren Schülerinnen und Schüler Selection Sort und Bubble Sort. Testen Sie mit Listen unterschiedlicher Größe und messen Sie Ausführungszeiten. Diskutieren Sie die Ergebnisse.

Analysieren Sie die Anzahl der Vertauschungen bei Selection Sort.

Moderationstipp

Bei der Paar-Programmierung (Activity 2) geben Sie den Schülerpaaren konkrete Testfälle vor, um die Implementierung zu überprüfen und Debugging-Schritte zu fördern.

Worauf zu achten ist

Bitten Sie die Schülerinnen und Schüler, auf einem Zettel zu notieren: 'Nennen Sie einen Vorteil von Selection Sort gegenüber Bubble Sort und begründen Sie diesen.' und 'Beschreiben Sie eine Situation, in der Selection Sort weniger effizient wäre als Bubble Sort.'

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

Aktivität 03

• Kollaboratives Problemlösen
• 40 Min. · Ganze Klasse

Klassenvergleich: Effizienzdiagramm

Die ganze Klasse führt beide Algorithmen auf gemeinsamen Datensätzen aus. Erstellen Sie ein Diagramm zur Anzahl der Operationen und besprechen Sie Vor- und Nachteile.

Begründen Sie, wann Selection Sort gegenüber anderen Sortierverfahren vorteilhaft sein könnte.

Moderationstipp

Beim Klassenvergleich (Activity 3) bereiten Sie ein vorbereitetes Diagramm vor, in das die Schülerinnen und Schüler ihre Messergebnisse eintragen können, um die Effizienz direkt sichtbar zu machen.

Worauf zu achten ist

Stellen Sie die Frage: 'Stellen Sie sich vor, Sie sortieren eine Liste von Musikstücken nach Interpret. Wenn das Kopieren eines Interpretennamens sehr langsam ist, welcher der beiden Algorithmen (Selection Sort oder Bubble Sort) wäre dann wahrscheinlich besser geeignet und warum?' Leiten Sie eine kurze Klassendiskussion.

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

Aktivität 04

• Kollaboratives Problemlösen
• 20 Min. · Einzelarbeit

Individuelle Analyse: Tauschzahlen

Jede Schülerin und jeder Schüler analysiert eine Liste und zählt manuell Vertauschungen für beide Algorithmen. Reichen Sie die Ergebnisse ein und vergleichen Sie in der Plenum.

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

Worauf zu achten ist

Lassen Sie die Schülerinnen und Schüler eine kleine unsortierte Zahlenliste (z.B. 5 Elemente) auf einem Arbeitsblatt manuell mit Selection Sort sortieren. Fragen Sie: 'Wie viele Vergleiche wurden in jedem Durchgang durchgeführt?' und 'Wie viele Vertauschungen gab es insgesamt?'

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

Einige Hinweise zum Unterrichten dieser Einheit

Erfahrene Lehrkräfte beginnen mit einer physischen Simulation, weil sie den Algorithmus zunächst ohne Technik begreifbar macht. Dann folgt die Implementierung in Python, die durch vorgegebene Code-Gerüste mit Lücken unterstützt wird. Vermeiden Sie es, den Algorithmus nur theoretisch zu erklären, da Schülerinnen und Schüler dann die Unterschiede zwischen den Algorithmen nicht nachvollziehen können. Nutzen Sie stattdessen den direkten Vergleich, um die Vor- und Nachteile zu verdeutlichen.

Am Ende der Einheit sollen die Schülerinnen und Schüler den Selection Sort in Python implementieren können, die Unterschiede zu Bubble Sort erklären und begründen, warum Selection Sort in bestimmten Situationen vorteilhafter ist. Sie erkennen, dass beide Algorithmen eine quadratische Komplexität besitzen, Selection Sort jedoch weniger Tauschoperationen benötigt.

---

Vorsicht vor diesen Fehlvorstellungen

• Während der Karten-Simulation (Activity 1) beobachten Sie, dass Schülerinnen und Schüler annehmen, Selection Sort führe immer weniger Vergleiche durch als Bubble Sort.

  Nutzen Sie die gezählten Vergleichswerte aus der Simulation, um gemeinsam mit der Klasse zu berechnen, dass beide Algorithmen etwa n(n-1)/2 Vergleiche benötigen. Diskutieren Sie, warum die Annahme falsch ist und welche Rolle die Tauschoperationen dabei spielen.

• Während der Paar-Programmierung (Activity 2) hören Sie, dass Schülerinnen und Schüler behaupten, Selection Sort sei generell schneller als Bubble Sort.

  Lassen Sie die Schülerpaare ihre Implementierungen mit großen Listen testen und die Laufzeit messen. Diskutieren Sie gemeinsam, warum beide Algorithmen bei großen Listen langsam sind, Selection Sort aber tatsächlich weniger Tauschoperationen benötigt.

• Während der Karten-Simulation (Activity 1) oder der Implementierung (Activity 2) denken Schülerinnen und Schüler, Selection Sort tausche nur benachbarte Elemente.

  Zeigen Sie in der Simulation oder im Code, dass Selection Sort das globale Minimum sucht und dieses direkt an die richtige Position tauscht. Verdeutlichen Sie den Unterschied zu Bubble Sort, der tatsächlich nur benachbarte Elemente vergleicht.

---

In dieser Übersicht verwendete Methoden

• Kollaboratives Problemlösen