Einführung in den Selection-Sort Algorithmus
Selection-Sort Algorithmus
Selectionsort ist ziemlich einfach aufgebaut.
Das Einsortieren von Spielkarten auf die Hand ist eigentlich das klassische Beispiel für Insertionsort.
Selectionsort kann man im Grunde genommen auch mit Spielkarten darstellen.
Hier legt man zunächst alle Karten offen auf den Tisch.
Dann sucht man die kleinste Karte und nimmt sie nach links auf die Hand,
danach die nächst größere und setzt sie rechts daneben, usw. bis zuletzt die größte Karte aufgenommen und ganz rechts einsortierst ist.
Unterschied zu Insertionsort
Bei Insertionsort hatten wir die jeweils nächste unsortierte Karte genommen und dann in den sortierten Karten an der richtigen Stelle eingefügt ("inserted"). Selectionsort funktioniert gewissermaßen anders herum: Wir wählen ("select") die jeweils kleinste Karte aus den unsortierten Karten, um diese dann – eine nach der anderen – an die bereits sortierten Karten anzuhängen.
Dadurch das wir die Elemente direkt in der Liste tauschen, haben wir einen in-place Algorithmus, der die Reihenfolge der Elemente nicht erhält und damit instabil arbeitet.
Lernvideo zum Selectionsort Lernvideo
Die Laufzeitkomplexität beim Selectionsort ist im Best-Case, Worst-Case und Average O(n2), wobei n die Anzahl der zu sortierenden Elemente angibt.
Hinweis: Alle Ergebnisse und Zwischenergebnisse müssen in Moodle abgegeben werden.
Aufgabe: Selection-Sort
Schwierigkeitsgrad: Einfach- Gegeben seien folgende Zahlen: 6, 9, 3, 1, 2, 4, 5, 8, 7
- Sortiere die Zahlenreihe nach dem Selection-Sort-Algorithmus!
- Gib die Anzahl der Vergleiche/Tausche an.
- Gib die Zeitkomplexität im Best-Case, Worst-Case und im Average an.