Selection Sort
Dass das Sortieren auf digitalen Geräten etwas Wichtiges ist, wissen wir ja schon. Deshalb suchen Informatiker nach immer besseren Methoden, Werte möglichst schnell zu sortieren und haben sich viele verschiedene Algorithmen ausgedacht, mit denen man das erreichen kann.
Zuletzt hatten wir den Algorithmus BubbleSort kennen gelernt. Heute schauen wir uns einen Algorithmus an, der ganz ähnlich funktioniert: Selection Sort. Hier werden aber (anders als bei BubbleSort) nicht die benachbarten Elemente miteinander verglichen.
Übungen, die wir gleich brauchen:
So funktioniert Selection Sort
Der Algorithmus von Selection Sort basiert darauf, dass man sich zuerst das kleinste Element sucht, dann das zweitkleinste und so weiter.
Vorbereitung: Der Kleinste-Zahl-an-den-Anfang-Algorithmus
- Wir vergleichen nacheinander jedes Element mit dem ersten Element des Arrays.
- Wenn wir ein Element finden, das kleiner ist als das erste, vertauschen wir beide.
- Wenn wir das Array bis zum Ende durchlaufen haben, steht das kleinste Element am Anfang!
Beispiel: Wir haben ein Array mit 4 Zahlen:
Welche Elemente werden verglichen?
Wir haben folgende Elemente des Arrays miteinander verglichen:
1 und 2
1 und 3
1 und 4
Um diese Vergleich durchzuführen, brauchen wir also eine Variable, die nacheinander die Werte 2, 3 und 4 annimmt! Wir verwenden hierfür eine Variable index, die wir in jedem Schleifendurchlauf nach oben zählen.
Die Idee ist also:
- Setze index auf 2
- Wiederhole bis index > 4
…
Weil nicht jedes Array 4 Elemente hat, können wir unsere Idee allgemeiner formulieren:
- Setze index auf 2
- Wiederhole bis index > Länge des Arrays
…
Struktogramm: Kleinste-Zahl-an-den-Anfang-Algorithmus
Aufgabe zum »Kleinste Zahl an den Anfang«-Algorithmus
(1) In Scratch die kleinste Zahl nach vorne bringen
Öffnen Sie das Projekt 7300_KleinstesElementAnDenAnfang-AUFGABE
Entwerfen Sie in Scratch den Programmcode, mit dem Sie das kleinste Element an den Anfang des Arrays verschieben!
Selection Sort: Sortieren in mehreren Durchgängen
Unser Ziel ist es, das komplette Array zu sortieren. Genau das kriegen wir hin, wenn wir den Kleinste-Zahl- an-den-Anfang-Algorithmus in mehreren Durchgängen auf das restliche Array anwenden. Schauen wir uns das im Beispiel an:
Damit haben wir es fast geschafft: Noch ein weiterer Durchgang mit dem Kleinste-Zahl-an-den-Anfang-Algorithmus:
Wie viele Durchgänge brauchen wir?
Sie sehen: Wenn wir unseren Kleinste-Zahl-an-den-Anfang-Algorithmus mehrmals anwenden, haben wir am Schluss ein komplett sortiertes Array!
Die Frage ist jetzt: Wie viele Durchgänge brauchen wir, bis das Array sortiert ist?
Fassen wir unsere Beobachtungen zusammen:
- Unser Array hatte 4 Elemente!
- Wir haben 3 Durchgänge gebraucht!
➡️ Vermutung: Die Anzahl der Durchgänge entspricht Länge des Arrays – 1
Kann das sein? In jedem Durchgang verschieben wir die jeweils kleinste Zahl an den Anfang des übrig gebliebenen Arrays. Dann müssten es doch genauso viele Durchgänge sein, wie Elemente im Array vorhanden sind!
ABER:
Im letzten Durchgang (im Beispiel: Durchgang 3) werden gleich 2 Elemente richtig einsortiert!
➡️ Unsere Vermutung stimmt!
Wir müssen also das Folgende tun, um ein Array mit Selection Sort zu sortieren:
Der Teil, der wiederholt werden soll, muss also ebenfalls in eine Schleife verschoben werden:
Achtung! Hier stimmt etwas nicht!
Irgendwie kann das aber so nicht stimmen! Schauen wir uns nochmal an, welche Elemente wir in den einzelnen Durchgängen verglichen haben - und so kommen wir zum fertigen Selection-Sort-Algorithmus:
Aufgaben: Selection Sort anwenden
(2) Namensliste sortieren
Sie haben eine Namensliste, die sortiert werden soll: Eva Anja Dragan Jasmin Alex
Sortieren Sie diese Liste "von Hand", indem Sie den Selection Sort-Algorithmus verwenden. Verwenden Sie dafür diese Word-Vorlage: 7200_Aufgabe2_NamenSortieren.docx
(3) Lottozahlen mit Selection Sort sortieren
Öffnen Sie das Projekt 7310_SelectionSort-AUFGABE
Ihre Aufgabe ist es, Lottozahlen zu sortieren. Setzen Sie dazu das Selection Sort-Struktogramm um!
(4) Verkäufe sortieren
Öffnen Sie das Projekt 7320_Blumenladen- AUFGABE
In diesem Projekt wurde bereits ein Array mit dem Namen verkaeufe erstellt und gefüllt. Ihre Aufgabe ist es, das Array verkaeufe zu sortieren. Setzen Sie dazu den Selection Sort- Algorithmus ein!
Arbeitsblatt: Selection Sort
Arbeitsblatt »Selection Sort« (PDF)
Übungsblatt: Tabelle »Namen sortieren« (docx)
Übersicht: Ablauf Selection Sort
(Alle Inhalte oben auf dieser Seite)
- Kleinste-Zahl-an-den-Anfang-Algorithmus besprechen
- Übung Scratch dazu (1)
- Erklärung: Mehrere Durchgänge
- Übung: Tabelle Namensliste
Mögliche Aufgaben in Klassenarbeit:
- Sortierschritte eines Arrays ausführen (in Tabelle)
- Selection-Sort-Algorithmus in eigenen Worten beschreiben
- Selection-Sort-Algorithmus erkennen (z.B. gegebenes Struktogramm, gegebene Tabelle mit Sortierschritten)
- Fehlerhaften Selection-Sort-Algorithmus (Struktogramm) berichtigen