Selectionsort (englisch selection ‚Auswahl‘ und englisch sort ‚sortieren‘) ist ein einfacher („naiver“) Sortieralgorithmus, der in-place arbeitet und in seiner Grundform instabil ist, wobei er sich auch stabil implementieren lässt. Die Komplexität von Selectionsort ist (Landau-Notation). Alternative Bezeichnungen des Algorithmus sind MinSort (von Minimum) bzw. MaxSort (von Maximum), Selectsort oder ExchangeSort (AustauschSort).
Prinzip
Sei S der sortierte Teil des Arrays (vorne im Array) und U der unsortierte Teil (dahinter). Am Anfang ist S noch leer, U entspricht dem ganzen (restlichen) Array. Das Sortieren durch Auswählen läuft nun folgendermaßen ab:
Suche das kleinste Element in U und vertausche es mit dem ersten Element von U (= das erste Element nach S).
Danach ist das Array bis zu dieser Position sortiert. Das kleinste Element wird in S verschoben (indem S einfach als ein Element länger betrachtet wird, und U nun ein Element später beginnt). S ist um ein Element gewachsen, U um ein Element kürzer geworden. Anschließend wird das Verfahren so lange wiederholt, bis das gesamte Array abgearbeitet worden ist; S umfasst am Ende das gesamte Array, aufsteigend sortiert, U ist leer.
Alternativen
Analog kann statt des kleinsten Elements das größte in U gesucht werden, was zu einer absteigenden Sortierreihenfolge führt. Auch kann U nach vorne und S nach hinten gelegt werden, was ebenfalls die Sortierreihenfolge umkehrt.
Zudem existieren auch Ansätze, in denen beide Varianten (MinSort und MaxSort) gemeinsam arbeiten; es gibt einen S-Bereich vorne und einen S-Bereich hinten, U liegt dazwischen. Während eines Durchlaufes werden das größte und das kleinste Element in U gesucht und dieses dann jeweils an den Anfang bzw. an das Ende von U gesetzt. Dadurch erreicht man in der Regel eine Beschleunigung, die jedoch meist nicht den Faktor 2 erreicht. Diese Variante wird gelegentlich „Optimized Selection Sort Algorithm“ (OSSA) genannt.
Formaler Algorithmus
Der Algorithmus sieht im Pseudocode so aus:
prozedur SelectionSort( A : Liste sortierbarer Elemente ) hoechsterIndex = Elementanzahl( A ) - 1 einfuegeIndex = 0 wiederhole minPosition = einfuegeIndex für jeden idx von (einfuegeIndex + 1) bis hoechsterIndex wiederhole falls A[ idx ] < A[ minPosition ] dann minPosition = idx ende falls ende für vertausche A[ minPosition ] und A[ einfuegeIndex ] einfuegeIndex = einfuegeIndex + 1 solange einfuegeIndex < hoechsterIndex prozedur ende
Beispiel-Implementierung des Algorithmus in BASIC:
Procedure SelectionSort ( Dim(1) A : Double )
Integer : Elemente, Ia, Small, Ib, MaxIndex
Double : TMP
Elemente = Count( A )
If Elemente < 2 Then Return
MaxIndex = Elemente - 1
For Ia = 0 To (MaxIndex - 1)
Small = Ia
For Ib = (Ia + 1) To MaxIndex
If A(Small) > A(Ib) Then Small = Ib
Next Ib
TMP = A(Ia)
A(Ia) = A(Small)
A(Small) = TMP
Next Ia
Return
Beispiel
Es soll ein Array mit dem Inhalt sortiert werden. Rot eingefärbte Felder deuten eine Tauschoperation an, blau eingefärbte Felder liegen im bereits sortierten Teil des Arrays.
|
Das Minimum ist 1. Vertausche also das 1. und das 3. Element. | ||||||
|
Das Minimum des rechten Teilarrays ist 2. Da es bereits an 2. Position steht, wird es nicht getauscht. | ||||||
|
Wir haben jetzt bereits ein sortiertes Teilarray der Länge 2. Wir vertauschen nun 4 und das Minimum 3. | ||||||
|
Wir vertauschen 6 und 4. | ||||||
|
Wir vertauschen 6 und 5. | ||||||
|
Das Array ist jetzt fertig sortiert. |
Komplexität
Um ein Array mit Einträgen mittels SelectionSort zu sortieren, muss -mal das Minimum bestimmt und ebenso oft getauscht werden.
Bei der ersten Bestimmung des Minimums sind Vergleiche notwendig, bei der zweiten Vergleiche usw.
Mit der gaußschen Summenformel erhält man die Anzahl der notwendigen Vergleiche:
Da das erste Element ist, entspricht die exakte Schrittzahl nicht genau der Darstellung der Gaußformel .
SelectionSort liegt somit in der Komplexitätsklasse .
Da zum Ermitteln des Minimums immer der komplette noch nicht sortierte Teil des Arrays durchlaufen werden muss, benötigt SelectionSort auch im „besten Fall“ Vergleiche.