DAA - Auswahl sortieren

Diese Art der Sortierung wird aufgerufen Selection Sortwie es funktioniert, indem Elemente wiederholt sortiert werden. Es funktioniert wie folgt: Finden Sie zuerst das kleinste im Array und tauschen Sie es mit dem Element an der ersten Position aus, dann suchen Sie das zweitkleinste Element und tauschen Sie es mit dem Element an der zweiten Position aus und fahren Sie auf diese Weise fort, bis das gesamte Array ist sortiert.

Algorithm: Selection-Sort (A) 
fori ← 1 to n-1 do 
   min j ← i; 
   min x ← A[i] 
   for j ←i + 1 to n do 
      if A[j] < min x then 
         min j ← j 
         min x ← A[j] 
   A[min j] ← A [i] 
   A[i] ← min x

Die Auswahlsortierung gehört zu den einfachsten Sortiertechniken und eignet sich sehr gut für kleine Dateien. Es hat eine sehr wichtige Anwendung, da jedes Element höchstens einmal bewegt wird.

Die Abschnittssortierung ist eine Methode der Wahl zum Sortieren von Dateien mit sehr großen Objekten (Datensätzen) und kleinen Schlüsseln. Der schlimmste Fall tritt auf, wenn das Array bereits in absteigender Reihenfolge sortiert ist und wir sie in aufsteigender Reihenfolge sortieren möchten.

Die Zeit, die der Auswahlsortieralgorithmus benötigt, ist jedoch nicht sehr empfindlich gegenüber der ursprünglichen Reihenfolge des zu sortierenden Arrays: dem Test if A[j] < min x wird in jedem Fall genau gleich oft ausgeführt.

Die Auswahlsortierung verbringt die meiste Zeit damit, das minimale Element im unsortierten Teil des Arrays zu finden. Es zeigt deutlich die Ähnlichkeit zwischen Auswahlsortierung und Blasensortierung.

Die Blasensortierung wählt die maximal verbleibenden Elemente in jeder Stufe aus, verschwendet jedoch einige Mühe, um einem unsortierten Teil des Arrays eine gewisse Ordnung zu verleihen.
Die Auswahlsortierung ist sowohl im schlechtesten als auch im durchschnittlichen Fall quadratisch und erfordert keinen zusätzlichen Speicher.

Für jeden i von 1 zu n - 1gibt es einen Austausch und n - i Vergleiche, also gibt es insgesamt n - 1 Austausch und

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 Vergleiche.

Diese Beobachtungen gelten unabhängig von den Eingabedaten.

Im schlimmsten Fall könnte dies quadratisch sein, im Durchschnitt ist dies jedoch die Größe O(n log n). Es impliziert, dass dierunning time of Selection sort is quite insensitive to the input.

Implementierung

Void Selection-Sort(int numbers[], int array_size) { 
   int i, j; 
   int min, temp;  
   for (i = 0; I < array_size-1; i++) { 
      min = i; 
      for (j = i+1; j < array_size; j++) 
         if (numbers[j] < numbers[min]) 
            min = j; 
      temp = numbers[i]; 
      numbers[i] = numbers[min]; 
      numbers[min] = temp; 
   } 
}