Selectionsort

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 O ( n 2 ) {\displaystyle {\mathcal {O}}(n^{2})} {\displaystyle {\mathcal {O}}(n^{2})} (Landau-Notation). Alternative Bezeichnungen des Algorithmus sind MinSort (von Minimum) bzw. MaxSort (von Maximum), Selectsort oder ExchangeSort (AustauschSort).

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.

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

[Bearbeiten | Quelltext bearbeiten ]

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: 

ProcedureSelectionSort(Dim(1)A:Double)
Integer:Elemente,Ia,Small,Ib,MaxIndex
Double:TMP

Elemente=Count(A)
IfElemente<2ThenReturn
MaxIndex=Elemente-1
ForIa=0To(MaxIndex-1)
Small=Ia
ForIb=(Ia+1)ToMaxIndex
IfA(Small)>A(Ib)ThenSmall=Ib
NextIb
TMP=A(Ia)
A(Ia)=A(Small)
A(Small)=TMP
NextIa
Return
Der Algorithmus muss jedes Mal den unsortierten Teil des Felds durchlaufen, um das kleinste Element zu finden.

Es soll ein Array mit dem Inhalt [ 4 | 2 | 1 | 6 | 3 | 5 ] {\displaystyle [4|2|1|6|3|5]} {\displaystyle [4|2|1|6|3|5]} sortiert werden. Rot eingefärbte Felder deuten eine Tauschoperation an, blau eingefärbte Felder liegen im bereits sortierten Teil des Arrays.

4 2 1 6 3 5
Das Minimum ist 1. Vertausche also das 1. und das 3. Element.
1 2 4 6 3 5
Das Minimum des rechten Teilarrays ist 2. Da es bereits an 2. Position steht, wird es nicht getauscht.
1 2 4 6 3 5
Wir haben jetzt bereits ein sortiertes Teilarray der Länge 2. Wir vertauschen nun 4 und das Minimum 3.
1 2 3 6 4 5
Wir vertauschen 6 und 4.
1 2 3 4 6 5
Wir vertauschen 6 und 5.
1 2 3 4 5 6
Das Array ist jetzt fertig sortiert.

Um ein Array mit n {\displaystyle n} {\displaystyle n} Einträgen mittels SelectionSort zu sortieren, muss n − 1 {\displaystyle n-1} {\displaystyle n-1}-mal das Minimum bestimmt und ebenso oft getauscht werden.

Bei der ersten Bestimmung des Minimums sind n − 1 {\displaystyle n-1} {\displaystyle n-1} Vergleiche notwendig, bei der zweiten n − 2 {\displaystyle n-2} {\displaystyle n-2} Vergleiche usw.

Mit der gaußschen Summenformel erhält man die Anzahl der notwendigen Vergleiche:

( n − 1 ) + ( n − 2 ) + ⋯ + 3 + 2 + 1 = ( n − 1 ) ⋅ n 2 = n 2 2 − n 2 {\displaystyle (n-1)+(n-2)+\dotsb +3+2+1={\frac {(n-1)\cdot n}{2}}={\frac {n^{2}}{2}}-{\frac {n}{2}}} {\displaystyle (n-1)+(n-2)+\dotsb +3+2+1={\frac {(n-1)\cdot n}{2}}={\frac {n^{2}}{2}}-{\frac {n}{2}}}

Da das erste Element n − 1 {\displaystyle n-1} {\displaystyle n-1} ist, entspricht die exakte Schrittzahl nicht genau der Darstellung der Gaußformel n + ( n − 1 ) + ⋯ + 2 + 1 = n ⋅ ( n + 1 ) 2 {\displaystyle n+(n-1)+\dotsb +2+1={\tfrac {n\cdot (n+1)}{2}}} {\displaystyle n+(n-1)+\dotsb +2+1={\tfrac {n\cdot (n+1)}{2}}}.

SelectionSort liegt somit in der Komplexitätsklasse O ( n 2 ) {\displaystyle {\mathcal {O}}(n^{2})} {\displaystyle {\mathcal {O}}(n^{2})}.

Da zum Ermitteln des Minimums immer der komplette noch nicht sortierte Teil des Arrays durchlaufen werden muss, benötigt SelectionSort auch im „besten Fall" n ⋅ ( n − 1 ) 2 {\displaystyle {\tfrac {n\cdot (n-1)}{2}}} {\displaystyle {\tfrac {n\cdot (n-1)}{2}}} Vergleiche.

Wikibooks: Selectionsort  – Implementierungen in der Algorithmensammlung
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Selectionsort&oldid=247602918"