Selectionsort 📖 Wikipedia

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 ${\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.

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

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

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

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

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

${\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 ${\displaystyle n-1}$ ist, entspricht die exakte Schrittzahl nicht genau der Darstellung der Gaußformel ${\displaystyle n+(n-1)+\dotsb +2+1={\tfrac {n\cdot (n+1)}{2}}}$.

SelectionSort liegt somit in der Komplexitätsklasse ${\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“ ${\displaystyle {\tfrac {n\cdot (n-1)}{2}}}$ Vergleiche.

Wikibooks: Selectionsort – Implementierungen in der Algorithmensammlung

• https://www.sortieralgorithmen.de/selectsort/index.html
• Erklärung und Code in C++
• OSSA – Vorstellung und Pseudocode (PDF)
  OSSA bugfixed