Datenstruktur und Algorithmen Auswahl Sortieren

Die Auswahlsortierung ist ein einfacher Sortieralgorithmus. Dieser Sortieralgorithmus ist ein 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 gegen das Element ganz links ausgetauscht, und dieses Element wird Teil des sortierten Arrays. Bei diesem Vorgang wird die unsortierte Array-Grenze um ein Element nach rechts verschoben.

Dieser Algorithmus ist nicht für große Datenmengen geeignet, da seine durchschnittliche und Worst-Case-Komplexität Ο (n 2 ) beträgt , wobein ist die Anzahl der Elemente.

Wie funktioniert die Auswahlsortierung?

Betrachten Sie das folgende abgebildete Array als Beispiel.

Für die erste Position in der sortierten Liste wird die gesamte Liste nacheinander gescannt. An der ersten Stelle, an der derzeit 14 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 Mindestwert in der Liste ist, an der ersten Position der sortierten Liste.

Für die zweite Position, an der sich 33 befindet, scannen wir den Rest der Liste linear.

Wir finden, dass 14 der zweitniedrigste Wert in der Liste ist und an zweiter Stelle stehen sollte. Wir tauschen diese Werte aus.

Nach zwei Iterationen werden zwei kleinste Werte sortiert am Anfang positioniert.

Der gleiche Vorgang wird auf die übrigen Elemente im Array angewendet.

Es folgt eine bildliche Darstellung des gesamten Sortiervorgangs -

Lassen Sie uns nun einige Programmieraspekte der Auswahlsortierung lernen.

Algorithmus

Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 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[j] < list[min] then
            min = j;
         end if
      end for

      /* swap the minimum element with the current element*/
      if indexMin != i  then
         swap list[min] and list[i]
      end if
   end for
	
end procedure

Klicken Sie hier , um Informationen zur Implementierung der Auswahlsortierung in der Programmiersprache C zu erhalten .