Selectionsort

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 (Landau-Notation). Alternative Bezeichnungen des Algorithmus sind MinSort (von Minimum) bzw. MaxSort (von Maximum), Selectsort oder ExchangeSort (AustauschSort).

Prinzip[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Analog kann statt dem kleinsten Element 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[Bearbeiten | Quelltext bearbeiten]

Der Algorithmus sieht im Pseudocode so aus:

prozedur SelectionSort( A : Liste sortierbarer Elemente ) 
  n = Länge( A ) - 1
  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[Bearbeiten | Quelltext bearbeiten]

Der Algorithmus muss jedes Mal den unsortierten Teil des Felds durchlaufen, um das kleinste Element zu finden.

Es soll ein Array mit dem Inhalt 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[Bearbeiten | Quelltext bearbeiten]

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

Bei der ersten Bestimmung des Minimums sind Vergleiche notwendig, bei der zweiten Vergleiche usw.

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

Da das erste Element ist, entspricht die exakte Schrittzahl nicht genau der Darstellung der Gaußformel .

SelectionSort liegt somit in der Komplexitätsklasse .

Da zum Ermitteln des Minimums immer der komplette noch nicht sortierte Teil des Arrays durchlaufen werden muss, benötigt SelectionSort auch im „besten Fall“ Vergleiche.

Weblinks[Bearbeiten | Quelltext bearbeiten]

 Wikibooks: Selectionsort – Implementierungen in der Algorithmensammlung