Selection Sort

Q: Wie ist die Zeitkomplexität von Selection Sort?

Selection Sort ist in allen Fällen `O(n²)` - bester, durchschnittlicher und schlechtester Fall - weil es stets den gesamten unsortierten Bereich durchsucht, um jedes Minimum zu finden. Es benötigt `O(1)` zusätzlichen Speicher.

Q: Was ist der Unterschied zwischen Selection Sort und Bubble Sort?

Beide sind `O(n²)`-Vergleichssortierungen, aber Selection Sort macht höchstens `n-1` Vertauschungen, während Bubble Sort bis zu `O(n²)` Vertauschungen ausführen kann. Bubble Sort kann außerdem ein bereits sortiertes Array erkennen und früher stoppen, während Selection Sort immer alle Durchläufe ausführt.

Zuletzt aktualisiert 1. Juli 2026

Selection Sort teilt das Array in einen sortierten Bereich links und einen unsortierten Bereich rechts. In jedem Durchlauf durchsucht es den unsortierten Bereich nach dem kleinsten Element und tauscht es dann an die erste unsortierte Position - wodurch der sortierte Bereich um eins wächst. Drücke oben auf Abspielen, um das Durchsuchen und Tauschen zu beobachten, oder gehe Vergleich für Vergleich durch.

Selection Sort führt unabhängig von der Eingabe stets die gleiche Anzahl an Vergleichen aus, aber höchstens n-1 Vertauschungen - weit weniger als Bubble Sort - was zählt, wenn Schreibvorgänge teuer sind.

Zeit- und Speicherkomplexität

Fall	Komplexität	Anmerkungen
Bester Fall	O(n²)	Vergleiche erfolgen selbst bei sortierter Eingabe
Durchschnittsfall	O(n²)	Zufällige Reihenfolge
Schlechtester Fall	O(n²)	Umgekehrt sortiert
Speicher	O(1)	In-place
Stabil	Nein	Vertauschungen können gleiche Elemente umordnen

Schritt für Schritt

Schritt	Was passiert
1	Betrachte das gesamte Array als unsortiert.
2	Durchsuche den unsortierten Bereich nach dem minimalen Element.
3	Tausche dieses Minimum an die erste unsortierte Position.
4	Verschiebe die Grenze um eine Stelle nach rechts (diese Position ist nun sortiert).
5	Wiederhole, bis nur noch ein Element unsortiert ist.

Durchgerechnetes Beispiel

Sortieren von [5, 2, 4, 1]:

Durchlauf	Array	Aktion
Start	`[5, 2, 4, 1]`	Das gesamte Array ist unsortiert.
1	`[1, 2, 4, 5]`	Durchsuche `[5, 2, 4, 1]`, das Minimum ist `1` an Index 3; tausche mit Index 0.
2	`[1, 2, 4, 5]`	Durchsuche `[2, 4, 5]`, das Minimum ist `2` bereits an Index 1; tauscht mit sich selbst.
3	`[1, 2, 4, 5]`	Durchsuche `[4, 5]`, das Minimum ist `4` bereits an Index 2; keine Bewegung nötig.
Fertig	`[1, 2, 4, 5]`	Nur noch `5` übrig, es ist also bereits an seinem Platz.

Wann Selection Sort verwenden

Verwende es, wenn	Vermeide es, wenn
Schreibvorgänge teuer sind - es macht höchstens `n-1` Vertauschungen.	Das Array groß ist - die `O(n²)` Vergleiche dominieren.
Du eine einfache, leicht zu implementierende In-place-Sortierung brauchst.	Du eine stabile Sortierung brauchst, die die Reihenfolge gleicher Schlüssel bewahrt.
Der Speicher knapp ist - es nutzt nur `O(1)` zusätzlichen Speicher.	Die Daten fast sortiert sind - es kann nicht wie Insertion Sort früher enden.
Der Datensatz winzig ist und vorhersagbare Leistung zählt.	Der Durchsatz zählt - `O(n log n)`-Sortierungen wie Quicksort sind weit schneller.

Selection Sort-Code

Eine saubere, lauffähige Selection Sort-Implementierung in Python, JavaScript, Java, C++, C. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.

Selection Sort-Code in PythonPython
1def selection_sort(a):2    n = len(a)3    for i in range(n - 1):4        # Find the smallest element in the unsorted tail5        min_idx = i6        for j in range(i + 1, n):7            if a[j] < a[min_idx]:8                min_idx = j9        a[i], a[min_idx] = a[min_idx], a[i]10    return a11
12
13nums = [64, 25, 12, 22, 11]14print("Before:", nums)15selection_sort(nums)16print("After: ", nums)
Führe diesen Code im Python-Playground aus

Selection Sort-Code in JavaScriptJavaScript
1function selectionSort(a) {2    for (let i = 0; i < a.length - 1; i++) {3        let min = i;4        // Find the smallest element in the unsorted tail5        for (let j = i + 1; j < a.length; j++) {6            if (a[j] < a[min]) min = j;7        }8        if (min !== i) [a[i], a[min]] = [a[min], a[i]];9    }10    return a;11}12
13const data = [5, 2, 9, 1, 7, 3];14console.log("Before:", data);15console.log("Sorted:", selectionSort([...data]));
Führe diesen Code im JavaScript-Playground aus

Selection Sort-Code in JavaJava
1import java.util.Arrays;2
3public class Main {4    static void selectionSort(int[] arr) {5        for (int i = 0; i < arr.length - 1; i++) {6            int minIndex = i;7            // Find the smallest value in the unsorted part8            for (int j = i + 1; j < arr.length; j++) {9                if (arr[j] < arr[minIndex]) minIndex = j;10            }11            int tmp = arr[i];12            arr[i] = arr[minIndex];13            arr[minIndex] = tmp;14        }15    }16
17    public static void main(String[] args) {18        int[] arr = {29, 10, 14, 37, 13, 5};19        System.out.println("Before: " + Arrays.toString(arr));20        selectionSort(arr);21        System.out.println("After:  " + Arrays.toString(arr));22    }23}
Führe diesen Code im Java-Playground aus

Selection Sort-Code in C++C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6    for (int x : a) std::cout << x << " ";7    std::cout << "\n";8}9
10void selectionSort(std::vector<int>& a) {11    for (size_t i = 0; i + 1 < a.size(); ++i) {12        // Find the smallest element in the unsorted suffix13        size_t minIdx = i;14        for (size_t j = i + 1; j < a.size(); ++j) {15            if (a[j] < a[minIdx]) minIdx = j;16        }17        std::swap(a[i], a[minIdx]);18    }19}20
21int main() {22    std::vector<int> data = {29, 10, 14, 37, 13, 5};23    std::cout << "Before: ";24    printVec(data);25    selectionSort(data);26    std::cout << "After:  ";27    printVec(data);28    return 0;29}
Führe diesen Code im C++-Playground aus

Selection Sort-Code in CC
1#include <stdio.h>2
3void printArr(const int a[], int n) {4    for (int i = 0; i < n; i++) printf("%d ", a[i]);5    printf("\n");6}7
8void selectionSort(int a[], int n) {9    for (int i = 0; i < n - 1; i++) {10        // Find the smallest element in the unsorted suffix11        int minIdx = i;12        for (int j = i + 1; j < n; j++) {13            if (a[j] < a[minIdx]) minIdx = j;14        }15        int tmp = a[i];16        a[i] = a[minIdx];17        a[minIdx] = tmp;18    }19}20
21int main(void) {22    int data[] = {29, 10, 14, 37, 13, 5};23    int n = sizeof(data) / sizeof(data[0]);24    printf("Before: ");25    printArr(data, n);26    selectionSort(data, n);27    printf("After:  ");28    printArr(data, n);29    return 0;30}
Führe diesen Code im C-Playground aus

Selection Sort FAQ

Wie ist die Zeitkomplexität von Selection Sort?

Selection Sort ist in allen Fällen O(n²) - bester, durchschnittlicher und schlechtester Fall - weil es stets den gesamten unsortierten Bereich durchsucht, um jedes Minimum zu finden. Es benötigt O(1) zusätzlichen Speicher.

Ist Selection Sort stabil?

Die standardmäßige In-place-Version ist nicht stabil, weil das Tauschen eines entfernten Minimums an seine Position ein gleiches Element an einem anderen vorbeischieben kann. Eine stabile Variante existiert, erfordert aber Verschieben statt Tauschen.

Wann ist Selection Sort nützlich?

Es ist nützlich, wenn die Kosten für das Schreiben in den Speicher hoch sind, da es höchstens n-1 Vertauschungen ausführt - das Minimum, das für eine vergleichsbasierte Sortierung möglich ist, die Elemente bewegt.

Was ist der Unterschied zwischen Selection Sort und Bubble Sort?

Beide sind O(n²)-Vergleichssortierungen, aber Selection Sort macht höchstens n-1 Vertauschungen, während Bubble Sort bis zu O(n²) Vertauschungen ausführen kann. Bubble Sort kann außerdem ein bereits sortiertes Array erkennen und früher stoppen, während Selection Sort immer alle Durchläufe ausführt.

Sollte ich Selection Sort oder Insertion Sort verwenden?

In den meisten Fällen ist Insertion Sort vorzuziehen - es ist stabil, läuft bei fast sortierten Daten in O(n) und ist im Durchschnitt schneller. Wähle Selection Sort nur, wenn das Minimieren der Anzahl an Schreibvorgängen Priorität hat, da es höchstens n-1 Vertauschungen garantiert.

Warum läuft Selection Sort selbst bei einem sortierten Array immer in O(n²)?

Selection Sort kann nicht wissen, dass ein Element bereits das Minimum ist, ohne den Rest des unsortierten Bereichs zu durchsuchen, daher führt es unabhängig von der Eingabereihenfolge in jedem Durchlauf alle Vergleiche aus. Deshalb entspricht der beste Fall dem schlechtesten bei O(n²) - anders als Insertion oder Bubble Sort, die abkürzen können.