Informatik · Klasse 11 · Algorithmen und Komplexität · 2. Halbjahr

Sortieralgorithmen: Bubble Sort und Selection Sort

Die Schülerinnen und Schüler implementieren und analysieren einfache Sortierverfahren.

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

Über dieses Thema

Sortieralgorithmen wie Bubble Sort und Selection Sort bilden eine Basis für das Verständnis algorithmischer Effizienz in der Informatik. Schülerinnen und Schüler implementieren Bubble Sort, das benachbarte Elemente vergleicht und vertauscht, bis das Array sortiert ist, und Selection Sort, das wiederholt das kleinste Element im unsortierten Teil findet und an die richtige Position schiebt. Sie analysieren Laufzeiten und Iterationen, oft mit kleinen Datenmengen von 5 bis 20 Elementen, um Vergleiche zu ermöglichen.

Dieses Thema entspricht den KMK-Standards für die Sekundarstufe II: Algorithmen entwerfen und implementieren. Es beantwortet zentrale Fragen wie die Bedeutung des Sortierens in der Informatik, den Vergleich der Funktionsweisen und die Effizienz bei kleinen Mengen. Selection Sort benötigt weniger Vertauschungen, Bubble Sort mehr Vergleiche, was Schüler durch Zählung und Messung entdecken.

Aktive Lernansätze machen diese Algorithmen erfahrbar. Wenn Schüler Karten oder Zahlen manuell sortieren, Programme schreiben und Laufzeiten vergleichen, erkennen sie Schwächen intuitiv. Solche Methoden fördern kritisches Denken, Fehleranalyse und den Transfer zu komplexeren Algorithmen wie Quick Sort.

Leitfragen

1. Warum ist Sortieren eine der wichtigsten Operationen in der Informatik?
2. Vergleichen Sie die Funktionsweise und Effizienz von Bubble Sort und Selection Sort.
3. Analysieren Sie, welcher Algorithmus bei sehr kleinen Datenmengen am effizientesten ist.

Lernziele

• Implementieren Sie Bubble Sort und Selection Sort in einer gewählten Programmiersprache.
• Vergleichen Sie die Anzahl der Vergleiche und Vertauschungen, die Bubble Sort und Selection Sort für gegebene Datensätze benötigen.
• Analysieren Sie die Zeitkomplexität von Bubble Sort und Selection Sort für kleine und große Datensätze.
• Erklären Sie die Vorteile und Nachteile beider Algorithmen im Hinblick auf Effizienz und Anwendungsfälle.
• Bewerten Sie, welcher Algorithmus für eine sortierte oder umgekehrt sortierte Eingabe besser geeignet ist.

Bevor es losgeht

Grundlagen der Programmierung: Variablen, Datentypen, Kontrollstrukturen (if, for, while)

Warum: Schüler müssen grundlegende Programmierkonzepte beherrschen, um die Algorithmen implementieren zu können.

Arrays und Listen als Datenstrukturen

Warum: Die Sortieralgorithmen operieren auf Arrays oder Listen, deren Handhabung vorausgesetzt wird.

Schlüsselvokabular

Bubble Sort	Ein einfacher Sortieralgorithmus, der wiederholt durch die Liste geht, benachbarte Elemente vergleicht und sie vertauscht, wenn sie in der falschen Reihenfolge sind.
Selection Sort	Ein Sortieralgorithmus, der die Liste wiederholt durchläuft, das kleinste (oder größte) Element im unsortierten Teil findet und es an den Anfang (oder das Ende) des unsortierten Teils setzt.
Vergleichsoperation	Eine Operation, bei der zwei Elemente einer Datenmenge miteinander verglichen werden, um ihre relative Reihenfolge zu bestimmen.
Vertauschungsoperation	Eine Operation, bei der die Positionen zweier Elemente innerhalb einer Datenmenge getauscht werden.
Laufzeitkomplexität	Ein Maß dafür, wie die Ausführungszeit eines Algorithmus mit der Größe der Eingabe wächst, oft ausgedrückt in Big-O-Notation.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Bubble Sort ist immer langsamer als Selection Sort.

Was Sie stattdessen lehren sollten

Bei kleinen Datenmengen sind beide ähnlich effizient, Selection Sort spart Vertauschungen. Aktive Simulationen mit Karten lassen Schüler zählen und messen, um dies selbst zu entdecken und Vorurteile abzubauen.

Häufige Fehlvorstellung

Algorithmen sortieren immer fehlerfrei, unabhängig von Eingabe.

Was Sie stattdessen lehren sollten

Falsche Annahmen über Edge-Cases wie bereits sortierte Listen. Peer-Programmierung und Testen mit variierten Arrays helfen, Fehler zu finden und Robustheit zu verstehen.

Häufige Fehlvorstellung

Mehr Iterationen bedeuten immer schlechtere Effizienz.

Was Sie stattdessen lehren sollten

Bubble Sort hat mehr Vergleiche, aber bei kleinen n gleichwertig. Gruppenvergleiche von Zählungen klären, dass Komplexität O(n²) für beide gilt und aktive Messung nuanciert.

Ideen für aktives Lernen

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.

30 Min.·Kleingruppen

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.

45 Min.·Partnerarbeit

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.

50 Min.·Ganze Klasse

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.

20 Min.·Einzelarbeit

Bezüge zur Lebenswelt

• Datenbanken: Bei der Indizierung von Datensätzen für schnelle Abfragen werden Sortieralgorithmen verwendet. Ein Sachbearbeiter in einem Archiv nutzt beispielsweise sortierte Listen, um schnell spezifische Dokumente zu finden.
• Betriebssysteme: Die Verwaltung von Prozessen und deren Prioritäten im Arbeitsspeicher erfordert effiziente Sortierverfahren. Ein Systemadministrator kann dies beobachten, wenn er die Auslastung von CPU-Kernen analysiert und die Prozesse entsprechend ihrer Wichtigkeit sortiert werden.
• E-Commerce: Die Anzeige von Produkten nach Preis oder Beliebtheit auf Online-Shopping-Plattformen wie Amazon nutzt Sortieralgorithmen. Ein Kunde, der nach dem günstigsten Flug sucht, profitiert direkt von der Effizienz dieser Algorithmen.

Ideen zur Lernstandserhebung

Kurze Überprüfung

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.

Lernstandskontrolle

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.

Diskussionsfrage

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.

Häufig gestellte Fragen

Was ist der Unterschied zwischen Bubble Sort und Selection Sort?

Bubble Sort vergleicht und vertauscht benachbarte Elemente in mehreren Durchgängen, bis keine Änderungen nötig sind. Selection Sort findet das Minimum im unsortierten Teil und verschiebt es ans Ende dieses Teils. Beide haben O(n²)-Komplexität, doch Selection Sort minimiert Vertauschungen, was bei realen Implementierungen Vorteile bringt. Schüler analysieren dies durch Implementierung und Timing-Tests.

Warum ist Sortieren eine der wichtigsten Operationen in der Informatik?

Sortieren optimiert Suche, ermöglicht Binärsuche und strukturiert Daten für Datenbanken oder Apps. Es demonstriert fundamentale Trade-offs in Zeit und Platz. In der Praxis ersetzt man einfache Sortierer durch effiziente wie Merge Sort, doch Bubble und Selection lehren Kernprinzipien der Algorithmik und Komplexität.

Wie kann aktives Lernen Schülern beim Verständnis von Sortieralgorithmen helfen?

Aktive Methoden wie Karten-Simulationen oder Programm-Duelle machen Iterationen sichtbar und zählbar. Schüler erleben, warum Bubble Sort bei umgekehrt sortierten Listen leidet, und messen Effizienz selbst. Gruppenarbeiten fördern Diskussionen über Optimierungen und bauen intuitives Verständnis auf, das Theorie allein nicht erreicht. Dies stärkt Problemlösungsfähigkeiten nach KMK-Standards.

Welcher Algorithmus ist bei kleinen Datenmengen effizienter?

Bei n<20 sind Bubble und Selection Sort vergleichbar, oft gewinnt Selection durch weniger Schreibvorgänge. Tests in Python mit timeit zeigen minimale Unterschiede. Schüler lernen, dass Konstantenfaktoren bei kleinen n entscheidend sind, und üben Big-O-Analyse durch empirische Messungen.