Theorieteil zu Folge 8
Selectionsort
Sortieren durch Auswählen
erster Sortierschritt
Der sortierte Teil ist leer, der unsortierte enthält alle Elemente. Im unsortierten Teil wird das kleinste Element gesucht und mit dem ersten Element des unsortierten Teils vertauscht. Nach dem 1. Schritt besteht das Feld somit aus einem sortierten Teil der Länge 1 (am linken Ende des Feldes) und einem unsortierten Teil der Länge x-1.
nachfolgende Sortierschritte
Das Feld besteht aus einem sortierten und einem nichtleeren unsortierten Teil. Weiterhin ist jedes Element im sortierten Teil kleiner als jedes Element im unsortierten Teil.
Wie im ersten Sortierschritt wird das kleinste Element des unsortierten Teils mit dem ersten Element des unsortierten Teils vertauscht.
Da das gesuchte Minimum größer ist als alle Elemente des bereits sortierten Teils, befindet es sich nach dem Tausch an der richtigen Stelle, somit erhöht sich die Zahl der sortierten Elemente um 1, während sich die Zahl der unsortierten Elemente um eins verringert.
Beispiel
Betrachten wie dazu mal ein Beispiel. Ein Array soll aus sechs int-Zahlen bestehen:
|
8
|
5
|
9
|
2
|
1
|
3
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Der gesamte Array ist noch unsortiert.
Schritt 1
Wir suchen nun die kleinste Zahl im unsortierten Teil - die 1 - und vertauschen sie mit der ersten Zahl des unsortierten Teils:
|
1
|
5
|
9
|
2
|
8
|
3
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Der sortierte Teil des Array besteht jetzt aus dem ersten Element, der unsortierte Teil ist entsprechend um ein Element kleiner geworden:
|
1
|
5
|
9
|
2
|
8
|
3
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Schritt 2
Wir suchen wieder die kleinste Zahl im unsortierten Teil - die 2 - und vertauschen sie mit der ersten Zahl des unsortierten Teils, der 5:
|
1
|
2
|
9
|
5
|
8
|
3
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Damit ist der sortierte Teil wieder um 1 gewachsen, der unsortierte Teil um 1 geschrumpft:
|
1
|
2
|
9
|
5
|
8
|
3
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Weitere Schritte
Die nächsten Schritte sollen im Schnelldurchgang dargestellt werden; das Verfahren an sich sollte jetzt klar sein.
Situation nach dem 3. Sortierschritt:
|
1
|
2
|
3
|
5
|
8
|
9
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Der Array ist jetzt schon sortiert; allerdings erkennt der Algorithmus dies noch nicht - wie soll er auch? Daher wird ein vierter Sortierschritt angeschlossen.
Nach dem 4. Sortierschritt:
|
1
|
2
|
3
|
5
|
8
|
9
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Theoretisch könnte der Array immer noch unsortiert sein, also folgt ein fünfter Sortierschritt.
Nach dem 5. Sortierschritt:
|
1
|
2
|
3
|
5
|
8
|
9
|
|
0
|
1
|
2
|
3
|
4
|
5
|
Da der unsortierte Teil nur noch aus einem Element besteht, ist der Array sortiert.
Implementationshinweise
Hier ist nur eine einfache for-Schleife notwendig. In jedem Schleifendurchgang wird die erste Zahl des unsortierten Teils mit der kleinsten Zahl des unsortierten Teils vertauscht. Wer beim Bubblesort das Tauschen in eine eigene Methode ausgelagert hat, kann diese Methode nun wieder verwenden. Die Hauptschwierigkeit beim Selectionsort wird es sein, eine Methode zu schreiben, welche die Position der kleinsten Zahl im unsortierten Teil des Arrays liefert. Es darf also nicht der gesamte Array durchsucht werden, sondern nur der unsortierte Teil.
Zurück zu Folge 8
Diese HTML-Seite wurde erstellt von Ulrich Helmich am 27. Februar 2005 und verändert am 1. Oktober 2006.