Allgemeines
Der Selectionsort ("Sortieren durch Auswählen") ist ein einfaches Sortierverfahren. Das Array besteht dabei aus zwei Teilen, dem bereits sortierten Teil (im folgenden Bild rot gekennzeichnet) und dem noch unsortierten Teil (grün gekennzeichnet).
Im 1. Sortierschritt wird die kleinste Zahl im unsortierten Teil gesucht (gelb markiert) und mit der ersten Zahl des unsortierten Teils vertauscht.
Die ersten drei Sortierschritte des Selectionsort
Autor: Ulrich Helmich, Lizenz: Public Domain
Nach dem 1. Sortierschritt besteht der sortierte Teil aus der ersten Zahl (Index = 0) und der unsortierte Teil aus dem Rest des Arrays, beginnend bei Index = 1.
Im 2. Sortierschritt wird wieder die kleinste Zahl des noch unsortierten Teils gesucht und mit der ersten Zahl dieses Teils (Index = 1) vertauscht. Nach dem 2. Sortierschritt besteht der sortierte Teil des Arrays schon aus zwei Zahlen, und der unsortierte Teil ist wieder um eine Zahl geschrumpft.
Das Ganze wird so lange wiederholt, bis das gesamte Array sortiert ist.
Den Algorithmus des Selectionsort könnte man ganz einfach in Java implementieren, vorausgesetzt, die Methode getMiniPos() funktioniert fehlerfrei:
public void selectionsort()
{
for (int i = 0; i < MAX - 1; i++)
tausche(i, getMiniPos(i));
}
Die Methode getMiniPos() sucht den Index der kleinsten Zahl im Array. Allerdings sucht sie nicht im gesamten Array, sondern nur im noch unsortierten Teil. Da die Methode selbst nicht weiß, bei welchem Index der unsortierte Teil des Arrays beginnt, muss man ihr diesen Index mithilfe eines Parameters mitteilen. Ansonsten würde getMiniPos() immer wieder beim ersten Arrayelement anfangen und nach dem 1. Durchgang immer wieder den Index 0 zurückliefern, denn nach dem 1. Durchgang befindet sich die kleinste Zahl des Arrays an der Position 0.
KI-Aufgabe
Den vorliegenden Text habe ich durch eine KI überprüfen lassen (Rechtschreibung, Grammatik, Schreibstil etc.). Ich hatte die Methode getMiniPos() in dem Text als Getter-Methode bezeichnet, ChatGPT meinte aber, die Bezeichnung "Getter-Methode" wäre nicht korrekt und hat die Bezeichnung durch "Methode" ersetzt.
Was meinen Sie, ist der Einwand der KI berechtigt, und wenn ja - wieso ?
Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu
Übungen
Übung 8.4-1
- Erweitern Sie die Klasse Liste um eine sondierende Methode getMiniPos(int ab), welche den Index der kleinsten Zahl des unsortierten Teils des Arrays zurückliefert.
Angenommen, das Array besteht aus den Zahlen 1 - 2 - 7 - 4 - 5 - 3.
Der sortierte Teil besteht aus den beiden ersten Zahlen, der unsortierte Teil beginnt mit der Zahl 7. Dann würde getMiniPos(2) den Wert 5 liefern, denn die kleinste Zahl des unsortierten Teils, die 3, befindet sich an der Position 5 des Arrays. - Testen Sie dann mithilfe der oben dargestellten Methode selectionsort(), ob Ihre getMiniPos()-Methode funktioniert.
Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu
Übung 8.4-2
Vergleichen Sie die Laufzeit des Bubblesort mit der des Selectionsort. Verwenden Sie dabei wieder die Methode zur Messung der Systemzeit.
Führen Sie die Messungen am PC durch und übertragen Sie die Messdaten in eine Tabelle. Stellen Sie die Ergebnisse anschließend graphisch dar.
Engagierte Schüler(innen) erweitern die Klasse Liste um eine Methode, welche diese Messungen nacheinander automatisch durchführt.
Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu
Aufgabe 8.4-3
Bei meinen eigenen Experimenten habe ich festgestellt, dass der Selectionsort deutlich schneller ausgeführt wird als der Bubblesort, obwohl doch beide Algorithmen ein ähnliches Zeitverhalten O(N2) haben.
Für 100 Zahlen benötigte der Bubblesort bei mir 37.399 Operationen (Vergleiche und Zuweisungen), während der Selectionsort nur 16.415 Operationen benötigte, also deutlich weniger als die Hälfte. Diese Messungen bestätigen die oft zitierte Behauptung, dass der Bubblesort der langsamste der einfachen Sortieralgorithmen ist.
| MAX | Bubblesort | Selectionsort |
| 100 | 37.399 | 16.415 |
| 200 | 148.615 | 62.987 |
| 400 | 595.222 | 246.677 |
| 800 | 2.385.640 | 974.291 |
| 1600 | 9.600.076 | 3.871.203 |
Finden Sie eine logische Begründung für dieses unterschiedliche Zeitverhalten von Bubble- und Selectionsort.
Videos auf YouTube zum Selectionsort
Die folgenden beiden Videos auf YouTube erscheinen mir besonders gut geeignet, wenn man den Selectionsort verstehen will. Vor Beginn oder während der Videos kann Werbung angezeigt werden.
Dieses Video zeigt eine anschauliche Animation des Selectionsort-Vorgangs. Die aktuell kleinste Zahl des unsortierten Arrays wird farbig markiert. Am Ende des Durchgangs wird die kleinste Zahl mit der ersten Zahl des unsortierten Teils getauscht.
Ein englischsprachiges Video, das den Selectionsort anschaulich erklärt und den Algorithmus anhand von Java-Quelltext demonstriert.
Seitenanfang -
Weiter mit dem Insertionsort...