Auswahl Sortieren

1. Auswahl-Sortieralgorithmus
2. Beispiel für die Auswahlsortierung
3. Implementierung des Auswahlsortieralgorithmus
4. Auswahlsortieralgorithmus Komplexität

Auswahlsortierung ist ein einfacher Sortieralgorithmus. Er funktioniert, indem er das Array in zwei Teile teilt: sortiertes und unsortiertes Subarray. Auswahlsortierung findet das kleinste Element innerhalb des unsortierten Teilarrays und verschiebt es an den letzten Index des sortierten Teilarrays. Sie wird verwendet, wenn Tauschoperationen sehr kostspielig sind, weil maximal nur n Tauschvorgänge erforderlich sind.

Auswahl-Sortieralgorithmus

Nehmen wir an, dass wir ein unsortiertes Array A[] mit n Elementen haben.

Beispiel für die Auswahlsortierung

Angenommen, wir haben das Array: (5,3,4,2,1,6). Wir werden es mit dem Auswahlsortieralgorithmus sortieren.

• Erste Iteration

Minimales Element: A[4] = 1

Vertauschen Sie (A[4], A[0]). Das Array wird zu: (1) (3,4,2,5,6)

• Zweite Iteration

Minimales Element: A[3] = 2

Vertauschen Sie (A[3], A[1]). Das Array wird zu: (1,2) (4,3,5,6)

• Dritte Iteration

Minimales Element: A[3] = 3

Vertauschen Sie (A[3], A[2]). Das Array wird zu: (1,2,3) (4,5,6)

• Vierte Iteration

Minimales Element: A[3] = 4

Vertauschen Sie (A[3], A[3]). Das Array wird zu: (1,2,3,4) (5,6)

• Fünfte Iteration

Minimales Element: A[4] = 5

Vertauschen Sie (A[4], A[4]). Das Array wird zu: (1,2,3,4,5) (6)

Das letzte Element ist bereits sortiert. Wir erhalten das sortierte Array als : (1,2,3,4,5,6)

Implementierung des Auswahlsortieralgorithmus

#include <bits/stdc++.h>
using namespace std;

void selectionSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    // Find the minimum element for index i
    int min = i;
    for (int j = i + 1; j < n; j++)
      if (arr[j] < arr[min]) min = j;
    // Put element in sorted position
    swap(arr[min], arr[i]);
  }
}
int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  selectionSort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Auswahlsortieralgorithmus Komplexität

Zeitkomplexität

• Durchschnittlicher Fall

Im Durchschnitt werden n-i Vergleiche im lten Durchgang der Einfügungssortierung durchgeführt. Wenn es also n Iterationen gibt, dann kann die durchschnittliche Zeitkomplexität unten angegeben werden:

(n-1) + (n-2) + (n-3) + ... + 1 = n*(n-1)/2

Die Zeitkomplexität liegt also in der Größenordnung von [Big Theta]: O(n²). Sie kann auch durch Zählen der Anzahl der Schleifen berechnet werden. Es gibt insgesamt zwei Schleifen mit n Iterationen, die die Komplexität : n*n = n²

• Schlimmster Fall

Die Zeitkomplexität im schlimmsten Fall ist [Big O]: O(n²).

• Bester Fall

Die Zeitkomplexität im besten Fall ist [Big Omega]: O(n²). Sie ist identisch mit der Worst-Case-Zeitkomplexität.

Raumkomplexität

Die Platzkomplexität für den Auswahlsortieralgorithmus ist O(1), da außer einer temporären Variablen kein zusätzlicher Speicher benötigt wird.