Informatik · Klasse 9 · Algorithmen und komplexe Datenstrukturen · 1. Halbjahr

Sortierverfahren: Selection Sort

Die Schülerinnen und Schüler implementieren den Selection Sort Algorithmus und vergleichen ihn mit Bubble Sort.

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

Über dieses Thema

Der Selection Sort Algorithmus sortiert eine Liste, indem er wiederholt das kleinste Element im unsortierten Teil findet und es an die richtige Position tauscht. Schülerinnen und Schüler in Klasse 9 implementieren diesen Algorithmus in einer Programmiersprache wie Python und vergleichen ihn mit dem Bubble Sort. Beim Bubble Sort werden benachbarte Elemente verglichen und bei Bedarf vertauscht, bis keine Umkehrungen mehr nötig sind. Beide Algorithmen weisen eine Zeitkomplexität von O(n²) auf, doch Selection Sort benötigt weniger Vertauschungen, da pro Durchgang nur ein Tausch erfolgt.

Im Rahmen der KMK-Standards zu Algorithmen und Problemlösen fördert dieses Thema das analytische Denken. Schülerinnen und Schüler analysieren die Anzahl der Vergleiche und Vertauschungen, vergleichen die Funktionsweise und begründen, wann Selection Sort vorteilhaft ist, etwa bei Listen mit wenigen Duplikaten oder wenn Tauschoperationen teuer sind. Dies stärkt das Verständnis komplexer Datenstrukturen und bereitet auf fortgeschrittene Sortierverfahren vor.

Aktives Lernen eignet sich hervorragend für dieses Thema, da Schülerinnen und Schüler durch physische Simulationen mit Karten oder interaktive Programmieraufgaben die Schritte nachvollziehen und Effizienzunterschiede direkt erleben. Solche Ansätze machen abstrakte Konzepte konkret und fördern tiefes Verständnis durch Trial-and-Error.

Leitfragen

1. Vergleichen Sie die Funktionsweise und Effizienz von Selection Sort und Bubble Sort.
2. Analysieren Sie die Anzahl der Vertauschungen bei Selection Sort.
3. Begründen Sie, wann Selection Sort gegenüber anderen Sortierverfahren vorteilhaft sein könnte.

Lernziele

• Vergleichen Sie die Anzahl der Vergleiche und Vertauschungen von Selection Sort mit denen von Bubble Sort für gegebene Datensätze.
• Implementieren Sie den Selection Sort Algorithmus in einer Programmiersprache (z.B. Python) und demonstrieren Sie dessen Funktionsweise.
• Analysieren Sie die Zeitkomplexität von Selection Sort und begründen Sie seine Effizienz im Vergleich zu Bubble Sort.
• Bewerten Sie die Eignung von Selection Sort für spezifische Szenarien, z.B. bei kostenintensiven Tauschoperationen.

Bevor es losgeht

Grundlagen der Programmierung: Variablen und Datentypen

Warum: Schülerinnen und Schüler müssen Variablen und grundlegende Datentypen wie Listen oder Arrays verstehen, um Algorithmen implementieren zu können.

Kontrollstrukturen: Schleifen (for, while)

Warum: Die Implementierung von Sortieralgorithmen erfordert zwingend den Einsatz von Schleifen zur Iteration über Datenelemente.

Grundlagen der Algorithmen: Was ist ein Algorithmus?

Warum: Ein grundlegendes Verständnis davon, was ein Algorithmus ist und wie er schrittweise Probleme löst, ist notwendig, um spezifische Algorithmen wie Selection Sort zu lernen.

Schlüsselvokabular

Selection Sort	Ein Sortieralgorithmus, der wiederholt das kleinste (oder größte) Element aus dem unsortierten Teil der Liste auswählt und an den Anfang (oder das Ende) des sortierten Teils stellt.
Bubble Sort	Ein einfacher Sortieralgorithmus, der wiederholt durch die Liste geht, benachbarte Elemente vergleicht und sie vertauscht, wenn sie in der falschen Reihenfolge sind.
Zeitkomplexität	Eine Messung, die angibt, wie die Laufzeit eines Algorithmus mit der Größe der Eingabe wächst. O(n²) bedeutet, dass sich die Laufzeit quadratisch mit der Anzahl der Elemente verdoppelt.
Vertauschung (Swap)	Der Vorgang des Austauschens der Positionen zweier Elemente in einer Liste oder einem Array.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Selection Sort führt immer weniger Vergleiche durch als Bubble Sort.

Was Sie stattdessen lehren sollten

Beide Algorithmen benötigen etwa n(n-1)/2 Vergleiche. Aktive Simulationen mit Karten helfen Schülerinnen und Schülern, dies durch Zählen zu erkennen und den Irrtum durch Peer-Diskussion zu korrigieren.

Häufige Fehlvorstellung

Selection Sort ist generell schneller als Bubble Sort.

Was Sie stattdessen lehren sollten

Bei großen Listen sind beide langsam, doch Selection Sort spart Tauschungen. Praktische Implementierungen in Code zeigen dies durch Messungen, was abstrakte Komplexitätsangaben greifbar macht.

Häufige Fehlvorstellung

Selection Sort tauscht nur benachbarte Elemente.

Was Sie stattdessen lehren sollten

Er sucht das globale Minimum. Physische Nachstellungen mit Gruppenobjekten verdeutlichen den Unterschied und stärken das Verständnis durch visuelle Wiederholung.

Ideen für aktives Lernen

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.

30 Min.·Kleingruppen

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.

45 Min.·Partnerarbeit

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.

40 Min.·Ganze Klasse

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.

20 Min.·Einzelarbeit

Bezüge zur Lebenswelt

• Datenbankadministratoren könnten Selection Sort in Betracht ziehen, wenn sie eine kleine, einmalig zu sortierende Liste von Benutzer-IDs für eine spezielle Abfrage vorbereiten müssen und die Anzahl der Schreiboperationen auf die Festplatte minimieren wollen.
• In der Logistik könnten Lagerverwaltungssysteme Selection Sort nutzen, um eine Liste von Paketen nach Gewicht zu sortieren, falls das Verschieben von Paketen (Tauschoperation) sehr zeitaufwendig ist und die Anzahl der Verschiebungen minimiert werden soll.

Ideen zur Lernstandserhebung

Kurze Überprüfung

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?'

Lernstandskontrolle

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

Diskussionsfrage

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.

Häufig gestellte Fragen

Was ist der Hauptunterschied zwischen Selection Sort und Bubble Sort?

Selection Sort findet pro Durchgang das kleinste Element im unsortierten Teil und tauscht es einmal, was zu n-1 Tauschungen führt. Bubble Sort vergleicht und tauscht benachbarte Elemente mehrmals, oft bis zu n(n-1)/2 Mal. Dieser Vergleich fördert bei Schülerinnen und Schülern das Bewusstsein für operationelle Kosten in Algorithmen.

Wie kann aktives Lernen beim Verständnis von Selection Sort helfen?

Aktive Methoden wie Karten-Sortierungen oder paarweises Programmieren lassen Schülerinnen und Schüler die Schritte selbst ausführen und Effizienzunterschiede messen. Solche hands-on-Aktivitäten machen die O(n²)-Komplexität erlebbar, fördern Diskussionen und korrigieren Missverständnisse schneller als reine Theorie. Die Ergebnisse bleiben langfristig im Gedächtnis.

Wann ist Selection Sort vorteilhaft gegenüber Bubble Sort?

Selection Sort eignet sich, wenn Tauschoperationen teuer sind, da er nur n-1 Tauschungen braucht. Bei fast sortierten Listen oder mit kostspieligen Vergleichen ist er effizienter. Schülerinnen und Schüler lernen dies durch Analyse realer Szenarien wie Datenbankabfragen.

Wie implementiert man Selection Sort in Python?

Verwenden Sie eine doppelte Schleife: Äußere von 0 bis len(liste)-1, innere sucht Minimum-Index ab i+1. Tauschen Sie liste[i] mit dem Minimum. Dieser Code ist einfach und eignet sich für Klasse 9, um Komplexität zu demonstrieren.