imported>Horst Gräbner: Änderungen von ~2026-15690-88 (Diskussion) auf die letzte Version von 2001:9E8:B326:F000:3943:7460:6659:8E95 zurückgesetzt

2026-03-12T11:38:35Z

Änderungen von ~2026-15690-88 (Diskussion) auf die letzte Version von 2001:9E8:B326:F000:3943:7460:6659:8E95 zurückgesetzt

Neue Seite

'''Selectionsort''' ({{enS|selection}} ‚Auswahl‘ und {{enS|sort}} ‚sortieren‘) ist ein einfacher („naiver“) [[Sortierverfahren|Sortieralgorithmus]], der [[in-place]] arbeitet und in seiner Grundform [[Stabilität (Sortierverfahren)|instabil]] ist, wobei er sich auch [[Stabilität (Sortierverfahren)|stabil]] implementieren lässt. Die [[Komplexität (Informatik)|Komplexität]] von Selectionsort ist <math> \mathcal{O}(n^2) </math> ([[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 [[Feld (Datentyp)|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]]:
<syntaxhighlight lang="basic" line="1">
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
</syntaxhighlight>

== Beispiel ==
[[Datei:Selsort de 0.gif|mini|250px|Der Algorithmus muss jedes Mal den unsortierten Teil des Felds durchlaufen, um das kleinste Element zu finden.]]

Es soll ein [[Feld (Datentyp)|Array]] mit dem Inhalt <math>[4|2|1|6|3|5]</math> sortiert werden. Rot eingefärbte Felder deuten eine Tauschoperation an, blau eingefärbte Felder liegen im bereits sortierten Teil des Arrays.

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

== Komplexität ==
Um ein Array mit <math>n</math> Einträgen mittels SelectionSort zu sortieren, muss <math>n-1</math>-mal das Minimum bestimmt und ebenso oft getauscht werden.

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

Mit der [[Gaußsche Summenformel|gaußschen Summenformel]] erhält man die Anzahl der notwendigen Vergleiche:

: <math>(n-1)+(n-2)+\dotsb+3+2+1 =\frac{(n-1)\cdot n}{2}=\frac{n^2}{2}-\frac{n}{2}</math>

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

SelectionSort liegt somit in der Komplexitätsklasse <math>\mathcal{O}(n^2)</math>.

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

== Weblinks ==
{{Wikibooks|Algorithmensammlung: Sortierverfahren: Selectionsort|Selectionsort|suffix=Implementierungen in der Algorithmensammlung}}
* https://www.sortieralgorithmen.de/selectsort/index.html
* [http://www.danmor.ch/blog/?p=221 Erklärung und Code in C++]
* [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.654.4716&rep=rep1&type=pdf OSSA – Vorstellung und Pseudocode] (PDF)<br /> [http://howtodevelop.eu/question/optimized-selection-sort-algorithm-ossa--how-to-fix-it,27307 OSSA bugfixed]

[[Kategorie:Sortieralgorithmus]]

Selectionsort - Versionsgeschichte

imported>Horst Gräbner: Änderungen von ~2026-15690-88 (Diskussion) auf die letzte Version von 2001:9E8:B326:F000:3943:7460:6659:8E95 zurückgesetzt