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 und U der unsortierte Teil. 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.

Danach ist das Array bis zu dieser Position sortiert. Das kleinste Element wird in S verschoben. 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.

Alternativ sucht man das Maximum, also das Element mit dem größten Sortierschlüssel. Das Maximum wird dann mit dem letzten Element des Arrays vertauscht und man erhält ebenfalls ein sortiertes Teilarray der Länge 1, allerdings rechts, und ein unsortiertes Array der Länge n-1, diesmal links. Der Algorithmus wird dann auch auf das unsortierte Teilarray 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, bzw. an das Ende des Arrays, gesetzt werden. Dadurch hat 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 =\frac{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 – Implementierungen in der Algorithmensammlung

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