Selectionsort

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 ${\mathcal {O}}(n^{2})$ (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 $[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.

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 $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)+\dotsb +3+2+1={\frac {(n-1)\cdot n}{2}}={\frac {n^{2}}{2}}-{\frac {n}{2}}

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

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, benötigt SelectionSort auch im „besten Fall“ ${\tfrac {n\cdot (n-1)}{2}}$ Vergleiche.