Allgemeines
Der Selectionsort ("Sortieren durch Auswählen") ist ein einfaches Sortierverfahren. Der Array besteht 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: siehe Seitenende
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 erste Zahl des noch unsortierten Teils (Index = 1) mit der kleinsten Zahl des unsortierten Teils getauscht. 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 solange wiederholt, bis der gesamte Array sortiert ist. Ein einfaches, selbsterstelltes Video, das den Selectionsort demonstriert, finden Sie hier.
Den Algorithmus des Selectionsort könnte man ganz einfach in Java implementieren, vorausgesetzt, die sondierende Methode getMiniPos() funktioniert fehlerfrei:
public void selectionsort()
{
for (int i=0; i < MAX; i++)
tausche(i,getMiniPos(i));
}
Die Methode getMiniPos() sucht den Index der kleinsten Zahl im Array. Allerdings nicht im gesamten Array, sondern nur im unsortierten Teil. Da die Methode selbst nicht weiß, bei welchem Index der unsortierte Teil des Arrays beginnt, muss man ihr das mit Hilfe eines Parameters mitteilen. Ansonsten würde miniPos() ja immer wieder beim ersten Arrayelement anfangen und nach dem 1. Durchgang immer wieder den Index 0 zurück liefern, denn nach dem 1. Durchgang befindet sich ja die kleinste Zahl des Arrays an der Position 0.
Ü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ück liefert.
Angenommen, der 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 3 befindet sich an der Position 5 des Arrays. - Ergänzen Sie Liste nun um eine manipulierende Methode selectionSort(), welche den Array entsprechend sortiert und dabei getMiniPos() verwendet.
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
Seitenanfang -
Weiter mit dem Insertionsort...