Selection sort ist ein einfacher Sortieralgorithmus. Dieser Sortieralgorithmus ist ein In-Place-Vergleichsalgorithmus, bei dem die Liste in zwei Teile unterteilt ist, den sortierten Teil am linken Ende und den unsortierten Teil am rechten Ende. Anfangs ist der sortierte Teil leer und der unsortierte Teil ist die gesamte Liste.
Das kleinste Element wird aus dem unsortierten Array ausgewählt und mit dem Element ganz links ausgetauscht, und dieses Element wird Teil des sortierten Arrays. Dieser Prozess setzt unsortierte Arraygrenzen um ein Element nach rechts fort.
Dieser Algorithmus eignet sich nicht für große Datensätze, da seine durchschnittliche und Worst-Case-Komplexität von Null (n2) ist, wobei n die Anzahl der Elemente ist.
Wie funktioniert die Auswahlsortierung?
Betrachten Sie das folgende dargestellte Array als Beispiel.
Für die erste Position in der sortierten Liste wird die gesamte Liste nacheinander gescannt. Die erste Position, an der 14 derzeit gespeichert ist, durchsuchen wir die gesamte Liste und stellen fest, dass 10 der niedrigste Wert ist.
Also ersetzen wir 14 durch 10. Nach einer Iteration erscheint 10, was zufällig der Minimalwert in der Liste ist, an der ersten Position der sortierten Liste.
Für die zweite Position, an der sich 33 befindet, beginnen wir, den Rest der Liste linear zu scannen.
Wir finden, dass 14 der zweitniedrigste Wert in der Liste ist und an zweiter Stelle erscheinen sollte. Wir tauschen diese Werte aus.
Nach zwei Iterationen werden zwei kleinste Werte sortiert am Anfang positioniert.
Der gleiche Vorgang wird auf den Rest der Elemente im Array angewendet.
Es folgt eine bildliche Darstellung des gesamten Sortierprozesses –
Lassen Sie uns nun einige Programmieraspekte der Auswahlsortierung lernen.
Algorithmus
Step 1 − Set MIN to location 0Step 2 − Search the minimum element in the listStep 3 − Swap with value at location MINStep 4 − Increment MIN to point to next elementStep 5 − Repeat until list is sorted
Pseudocode
procedure selection sort list : array of items n : size of list for i = 1 to n - 1 /* set current element as minimum*/ min = i /* check the element to be minimum */ for j = i+1 to n if list < list then min = j; end if end for /* swap the minimum element with the current element*/ if indexMin != i then swap list and list end if end forend procedure
Um mehr über die Implementierung der Auswahlsortierung in der Programmiersprache C zu erfahren, klicken Sie bitte hier.