Selectionsort

Der Begriff Selectionsort (englisch selection ‚Auswahl‘ und englisch sort ‚sortieren‘) bezeichnet einen naiven 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, in der Landau-Notation ausgedrückt, ${\mathcal {O}}(n^{2})$. 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 Array. Das Sortieren durch Auswählen funktioniert so:

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 solange wiederholt, bis das gesamte Array abgearbeitet worden ist; S umfasst nun das gesamte Array, aufsteigend sortiert, U ist leer.

Alternativ sucht man das Maximum, also das Element mit dem größten Sortierschlüssel - hierbei ist dann auch U vorne und S hinten. Das Maximum wird dann mit dem letzten Element von U vertauscht und man erhält ebenfalls ein sortiertes Teilarray S, das nun 1 Position früher beginnt, allerdings hinten im Array, und ein unsortiertes Teilarray U, verkürzt um 1 Position, diesmal vorne im Array. Der Algorithmus wird dann wiederholt auf das unsortierte Teilarray U angewendet.

Zudem existieren auch Ansätze, in denen beide Varianten (MinSort und MaxSort) gemeinsam arbeiten, sprich während eines Durchlaufes das größte und das kleinste Element eines Arrays gesucht und dieses dann jeweils an den Anfang sowie an das Ende von U gesetzt werden. Dadurch erreicht man in der Regel eine Beschleunigung um den Faktor 2.

Formaler Algorithmus

Der Algorithmus sieht im Pseudocode so aus:

prozedur SelectionSort( A : Liste sortierbarer Elemente ) 
  n = Länge( A )
  links = 0
  wiederhole
    min = links
    für jedes i von links + 1 bis n wiederhole 
      falls A[ i ] < A[ min ] dann
          min = i
      ende falls
    ende für
    Vertausche A[ min ] und A[ links ]
    links = links + 1
  solange links < n
prozedur ende

Beispiel

Der Algorithmus muss das Feld jedes Mal durchlaufen, um das kleinste Element zu finden.

Es soll ein Array mit dem Inhalt $[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.

Komplexität

Um ein Array mit n-Einträgen mittels SelectionSort zu sortieren, muss n-1 Mal das Minimum bestimmt und ebenso oft getauscht werden.

Bei der ersten Bestimmung des Minimums sind n-1 Vergleiche notwendig, bei der zweiten n-2 Vergleiche usw.

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

$(n-1)+(n-2)+...+3+2+1={\frac {(n-1)\cdot n}{2}}={\frac {n^{2}}{2}}-{\frac {n}{2}}$

Man beachte, dass die exakte Schrittzahl dadurch, dass das erste Element $(n-1)$ ist, nicht genau der Darstellung der Gaußformel $n+(n-1)+...+2+1={\tfrac {n\cdot (n+1)}{2}}$ entspricht.

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

Da zum Ermitteln des Minimums immer der komplette noch nicht sortierte Teil des Arrays durchlaufen werden muss, liegt SelectionSort nicht nur im schlechtesten Fall, sondern sogar in jedem Fall in dieser Komplexitätsklasse.

Weblinks

Wikibooks: Selectionsort – Lern- und Lehrmaterialien

• VisuSort Framework – Visualisierung diverser Sortieralgorithmen (Windows)
• http://www.sortieralgorithmen.de/selectsort/index.html
• Erklärung und Code in C++