Selection Sort

Einführung

Selection Sort (Auswahlsortierung) ist ein einfacher, vergleichsbasierter Sortieralgorithmus, der ein Array in einen sortierten und einen unsortierten Teil unterteilt. In jeder Iteration wird das kleinste Element aus dem unsortierten Teil ausgewählt und mit dem ersten Element dieses Teils getauscht.

Funktionsweise

1. Initialisierung: Der sortierte Teil ist am Anfang leer.
2. Suche Minimum: Finde das kleinste Element im unsortierten Teil.
3. Tauschen: Vertausche es mit dem ersten Element des unsortierten Teils.
4. Verschieben: Erweitere den sortierten Teil um eine Position.
5. Wiederholung: Wiederhole, bis der gesamte Array sortiert ist.

Hinweis: Der aktuell minimale Wert (Selection) wird direkt an die richtige Stelle getauscht (swapping), nicht Stück-für-Stück wie beim Nachbarvergleich (bubble).

Komplexität

• Zeitkomplexität: O(n²) im besten, durchschnittlichen und schlechtesten Fall.
• Speicherkomplexität: O(1) – arbeitet in-place.
• Stabilität: Instabil (kann die relative Reihenfolge gleicher Elemente ändern).

Java-Implementierung

```java public class SelectionSort { public static void selectionSort(int[] arr) { int n = arr.length;

    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;

        // Finde das kleinste Element im unsortierten Teil
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }

        // Tausche das gefundene Minimum mit dem ersten Element
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

// Beispielaufruf
public static void main(String[] args) {
    int[] data = {64, 25, 12, 22, 11};
    System.out.println("Unsortiert: " + java.util.Arrays.toString(data));
    selectionSort(data);
    System.out.println("Sortiert: " + java.util.Arrays.toString(data));
} }