Selection Sort

7.1 Definition von Selection Sort

Selection Sort ist ein Sortieralgorithmus, der das kleinste Element im unsortierten Teil des Arrays findet und es mit dem ersten Element dieses Teils vertauscht. Der Prozess wird für die verbleibenden Elemente wiederholt, bis das gesamte Array sortiert ist.

Funktionsweise:

1. Wir beginnen mit dem ersten Element des Arrays.
2. Wir finden das kleinste Element im verbleibenden unsortierten Teil des Arrays.
3. Wir tauschen das kleinste Element mit dem ersten Element des unsortierten Teils.
4. Wir wiederholen den Prozess für das nächste Element, bis das gesamte Array sortiert ist.

Schritt-für-Schritt-Prozess

1. Wir finden das kleinste Element im Array und tauschen es mit dem ersten Element.
2. Wir wiederholen den Prozess für das verbleibende Array (beginnend mit dem zweiten Element).
3. Wir setzen den Prozess fort, bis das gesamte Array sortiert ist.

Zeit- und Platzkomplexität von Selection Sort

Zeitkomplexität:

• Im schlimmsten Fall: O(n^2) — tritt auf, wenn die Elemente ursprünglich in umgekehrter Reihenfolge oder zufällig angeordnet sind.
• Im durchschnittlichen Fall: O(n^2) — tritt bei zufälliger Anordnung der Elemente auf.
• Im besten Fall: O(n^2) — selbst wenn das Array bereits sortiert ist, führt der Algorithmus dennoch dieselben Vergleiche durch.

Platzkomplexität:

O(1) — weil der Algorithmus eine konstante Menge an zusätzlichem Speicher verwendet (nur ein paar Variablen zum Speichern temporärer Werte).

7.2 Implementierung des Selection Sort-Algorithmus

Die Implementierung des Algorithmus ist sehr einfach:

Schritt 1: Wir finden das minimale Element unter allen Elementen und tauschen es mit dem ersten.

Schritt 2: Wir finden das minimale Element unter allen Elementen außer dem ersten und tauschen es mit dem zweiten.

Schritt 3: Wir finden das minimale Element unter allen Elementen außer dem ersten und zweiten und tauschen es mit dem dritten.

Implementierung in Python:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Finden des minimalen Elements im verbleibenden unsortierten Teil des Arrays min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j
        # Tauschen des gefundenen minimalen Elements mit dem ersten Element des unsortierten Teils arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr  # Rückgabe des sortierten Arrays

# Beispielverwendung:
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Sortiertes Array:", sorted_arr)
# Ausgabe: Sortiertes Array: [11, 12, 22, 25, 64]

Beispiel für die Funktionsweise des Algorithmus:

1. Erster Durchgang (i = 0):
   1. Wir finden das minimale Element (11) im unsortierten Teil des Arrays [64, 25, 12, 22, 11].
   2. Wir tauschen 11 mit 64.
   3. Array: [11, 25, 12, 22, 64]
2. Zweiter Durchgang (i = 1):
   1. Wir finden das minimale Element (12) im unsortierten Teil des Arrays [25, 12, 22, 64].
   2. Wir tauschen 12 mit 25.
   3. Array: [11, 12, 25, 22, 64]
3. Dritter Durchgang (i = 2):
   1. Wir finden das minimale Element (22) im unsortierten Teil des Arrays [25, 22, 64].
   2. Wir tauschen 22 mit 25.
   3. Array: [11, 12, 22, 25, 64]
4. Vierter Durchgang (i = 3):
   1. Wir finden das minimale Element (25) im unsortierten Teil des Arrays [25, 64].
   2. 25 ist bereits an der richtigen Stelle, kein Tausch erforderlich.
   3. Array: [11, 12, 22, 25, 64]

Der Algorithmus endet, da alle Elemente sortiert sind.