www.wikidata.de-de.nina.az

Selectionsort englisch selection Auswahl und englisch sort sortieren ist ein einfacher naiver Sortieralgorithmus der in

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

Prinzip 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

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 Bearbeiten

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 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

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

Wikibooks: Selectionsort – Implementierungen in der Algorithmensammlung
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 lasst Die Komplexitat von Selectionsort ist O n 2 displaystyle mathcal O n 2 Landau Notation Alternative Bezeichnungen des Algorithmus sind MinSort von Minimum bzw MaxSort von Maximum Selectsort oder ExchangeSort AustauschSort Inhaltsverzeichnis 1 Prinzip 1 1 Alternativen 2 Formaler Algorithmus 3 Beispiel 4 Komplexitat 5 WeblinksPrinzip BearbeitenSei 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 Auswahlen lauft nun folgendermassen 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 langer betrachtet wird und U nun ein Element spater beginnt S ist um ein Element gewachsen U um ein Element kurzer geworden Anschliessend 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 Analog kann statt des kleinsten Elements das grosste in U gesucht werden was zu einer absteigenden Sortierreihenfolge fuhrt Auch kann U nach vorne und S nach hinten gelegt werden was ebenfalls die Sortierreihenfolge umkehrt Zudem existieren auch Ansatze in denen beide Varianten MinSort und MaxSort gemeinsam arbeiten es gibt einen S Bereich vorne und einen S Bereich hinten U liegt dazwischen Wahrend eines Durchlaufes werden das grosste 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 BearbeitenDer Algorithmus sieht im Pseudocode so aus prozedur SelectionSort A Liste sortierbarer Elemente hoechsterIndex Elementanzahl A 1 einfuegeIndex 0 wiederhole minPosition einfuegeIndex fur jeden idx von einfuegeIndex 1 bis hoechsterIndex wiederhole falls A idx lt A minPosition dann minPosition idx ende falls ende fur vertausche A minPosition und A einfuegeIndex einfuegeIndex einfuegeIndex 1 solange einfuegeIndex lt 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 lt 2 Then Return MaxIndex Elemente 1 For Ia 0 To MaxIndex 1 Small Ia For Ib Ia 1 To MaxIndex If A Small gt A Ib Then Small Ib Next Ib TMP A Ia A Ia A Small A Small TMP Next Ia ReturnBeispiel Bearbeiten nbsp Der Algorithmus muss jedes Mal den unsortierten Teil des Felds durchlaufen um das kleinste Element zu finden Es soll ein Array mit dem Inhalt 4 2 1 6 3 5 displaystyle 4 2 1 6 3 5 nbsp sortiert werden Rot eingefarbte Felder deuten eine Tauschoperation an blau eingefarbte 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 Lange 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 Komplexitat BearbeitenUm ein Array mit n displaystyle n nbsp Eintragen mittels SelectionSort zu sortieren muss n 1 displaystyle n 1 nbsp mal das Minimum bestimmt und ebenso oft getauscht werden Bei der ersten Bestimmung des Minimums sind n 1 displaystyle n 1 nbsp Vergleiche notwendig bei der zweiten n 2 displaystyle n 2 nbsp Vergleiche usw Mit der gaussschen Summenformel erhalt man die Anzahl der notwendigen Vergleiche n 1 n 2 3 2 1 n 1 n 2 n 2 2 n 2 displaystyle n 1 n 2 dotsb 3 2 1 frac n 1 cdot n 2 frac n 2 2 frac n 2 nbsp Da das erste Element n 1 displaystyle n 1 nbsp ist entspricht die exakte Schrittzahl nicht genau der Darstellung der Gaussformel n n 1 2 1 n n 1 2 displaystyle n n 1 dotsb 2 1 tfrac n cdot n 1 2 nbsp SelectionSort liegt somit in der Komplexitatsklasse O n 2 displaystyle mathcal O n 2 nbsp Da zum Ermitteln des Minimums immer der komplette noch nicht sortierte Teil des Arrays durchlaufen werden muss benotigt SelectionSort auch im besten Fall n n 1 2 displaystyle tfrac n cdot n 1 2 nbsp Vergleiche Weblinks Bearbeiten nbsp Wikibooks Selectionsort Implementierungen in der Algorithmensammlung http www sortieralgorithmen de selectsort index html Erklarung und Code in C OSSA Vorstellung und Pseudocode PDF OSSA bugfixed Abgerufen von https de wikipedia org w index php title Selectionsort amp oldid 230489279