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.

    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.

    Scratch: Lottozahlen-Tauschen-Projekt

    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:

    Selectionsort-Beispiel: Durchgang 1

    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

    Struktogramm: Kleinste-Zahl-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!

    Scratch-Aufgabe Kleinste Zahl

    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:

    Selectionsort-Beispiel: Durchgang 2

    Damit haben wir es fast geschafft: Noch ein weiterer Durchgang mit dem Kleinste-Zahl-an-den-Anfang-Algorithmus:

    Selectionsort-Beispiel: Durchgang 3

    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:

    Struktogramm Selectionsort fast fertig

    Der Teil, der wiederholt werden soll, muss also ebenfalls in eine Schleife verschoben werden:

    Struktogramm Selectionsort mit Schleife (fast fertig)

    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:

    Struktogramm Selectionsort FERTIG mit Herleitung

    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

    Tabelle mit zu sortierenden Namen

    (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!

    Scratch Unterprogramm: Lottozahlen sortieren

    (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!

    Scratch Unterprogramm: Verkäufe sortieren

    Arbeitsblatt: Selection Sort

    Arbeitsblatt »Selection Sort« (PDF)

    Übungsblatt: Tabelle »Namen sortieren« (docx)

    Copyright © 2020Powered by Bludit