Selection-Sort

Einführung

Stell dir vor, du hast eine unsortierte Liste mit Telefonnummern und suchst eine bestimmte Nummer. Ohne Ordnung musst du jeden Eintrag mühsam durchgehen – das kostet Zeit.

Eine der einfachsten Methoden, eine Liste zu sortieren, ist Selection Sort.

Auch wenn er nicht der schnellste Algorithmus ist, zeigt er dir Schritt für Schritt, wie du ein großes Problem – das Sortieren vieler Elemente – in einfache, wiederholbare Schritte zerlegen kannst. Damit eignet er sich besonders gut, um die Grundlagen des algorithmischen Denkens zu verstehen.

In dieser Lerneinheit erfährst du, wie Selection Sort funktioniert, wie er in Python umgesetzt wird und welche Eigenschaften ihn auszeichnen.

Lernziele

Nach dieser Einheit kannst du:

Das Prinzip von Selection Sort erklären Du kannst beschreiben, wie der Algorithmus funktioniert, indem er das kleinste Element im unsortierten Bereich sucht und in den sortierten Bereich verschiebt.
Den Ablauf Schritt für Schritt nachvollziehen Du kannst anhand eines Beispiels den Prozess mit sortiertem und unsortiertem Bereich darstellen und die Veränderungen im Array erläutern.
Selection Sort in Python implementieren Du kannst den Algorithmus mit verschachtelten Schleifen und einer Tauschoperation programmieren und erklären, was der Code bewirkt.
Die Eigenschaften und Einsatzgebiete beurteilen Du kannst Vor- und Nachteile von Selection Sort benennen, seine Komplexität erklären und geeignete sowie ungeeignete Anwendungsfälle unterscheiden.

Überleitung

Selection Sort ist ein einfacher Sortieralgorithmus. Er ist leicht verständlich und eignet sich sehr gut, um grundlegende Prinzipien der Algorithmik zu erlernen.

Lass uns mit den Grundlagen beginnen.

Was ist Selection Sort und warum ist er wichtig?

Selection Sort ist ein Sortieralgorithmus, der Elemente nach und nach in die richtige Reihenfolge bringt.

Die Grundidee: Du suchst immer das kleinste Element aus dem unsortierten Bereich und setzt es an die nächste freie Position im sortierten Bereich.

Wichtig ist Selection Sort, weil er dir hilft, den Umgang mit systematischem Vorgehen zu üben. Du lernst, wie man ein größeres Problem in einfache Schritte zerlegt, wie Vergleiche und Tauschoperationen funktionieren und wie man Strukturen wie Schleifen einsetzt.

So funktioniert Selection Sort Schritt für Schritt

Selection Sort arbeitet, indem es ein Array in zwei Bereiche teilt: links der sortierte Bereich, rechts der unsortierte Bereich.

Zu Beginn ist der sortierte Bereich leer und der unsortierte Bereich enthält alle Elemente. Mit jedem Schritt wächst der sortierte Bereich um ein Element, das wir an die richtige Position setzen.

Beispiel: Array [64, 25, 12, 22, 11]

Schritt 1: Minimum = 11 → Tausche mit 64. Ergebnis: [11, 25, 12, 22, 64].
- (Sortiert: [11] | Unsortiert: [25, 12, 22, 64])
Schritt 2: Minimum = 12 → Tausche mit 25. Ergebnis: [11, 12, 25, 22, 64].
- (Sortiert: [11, 12] | Unsortiert: [25, 22, 64])
Schritt 3: Minimum = 22 → Tausche mit 25. Ergebnis: [11, 12, 22, 25, 64].
- (Sortiert: [11, 12, 22] | Unsortiert: [25, 64])
Schritt 4: Minimum = 25, kein Tausch nötig. Ergebnis: [11, 12, 22, 25, 64].
- (Sortiert: [11, 12, 22, 25] | Unsortiert: [64])
Schritt 5: Letztes Element ist automatisch korrekt.

Hier siehst du: Mit jedem Durchgang wächst der linke (sortierte) Teil, während der rechte (unsortierte) Teil schrumpft. So wird das Array Schritt für Schritt geordnet.

Algorithmus in Worten

Bevor wir den Ablauf auflisten, wichtig: Der Algorithmus funktioniert, indem er systematisch immer das kleinste Element aus dem Rest sucht.

Starte ganz links im Array.
Suche im restlichen unsortierten Teil das kleinste Element.
Tausche dieses Element mit dem aktuellen Platz.
Gehe einen Schritt nach rechts und wiederhole den Vorgang.

Nach einigen Durchläufen ist der linke Teil vollständig sortiert, der rechte leer.

Lass uns das mal in Python anschauen

Selection-Sort-Code

Schritt 1: Array anlegen und Länge bestimmen

arr = [64, 25, 12, 22, 11]  # unsere unsortierte Liste
n = len(arr)                # Anzahl der Elemente bestimmen

Erklärung:

arr ist eine Liste mit Zahlen, die wir sortieren wollen.
len(arr) zählt, wie viele Elemente in der Liste sind. Das Ergebnis wird in n gespeichert.

Damit haben wir die Daten vorbereitet.

Selection-Sort-Code

Schritt 2: Erste Schleife hinzufügen

arr = [64, 25, 12, 22, 11]
n = len(arr)
 
for i in range(n - 1):      # äußere Schleife
    min_index = i           # wir nehmen an: Position i ist das kleinste Element

Erklärung:

for i in range(n - 1) bedeutet: wir gehen nacheinander jede Position von links durch (außer die letzte, die ist am Ende automatisch korrekt).
i ist die aktuelle Zielposition, an die das kleinste Element gehört.
min_index merkt sich, wo das bisher kleinste gefundene Element steht. Anfangs nehmen wir einfach i an.

Damit haben wir den Rahmen: Wir bauen den sortierten Bereich Stück für Stück von links nach rechts auf.

Selection-Sort-Code

Schritt 3: Innere Schleife hinzufügen

arr = [64, 25, 12, 22, 11]
n = len(arr)
 
for i in range(n - 1):
    min_index = i
    for j in range(i + 1, n):             # innere Schleife
        if arr[j] < arr[min_index]:       # ist ein kleineres Element gefunden?
            min_index = j

Erklärung:

for j in range(i + 1, n): wir durchsuchen nur den rechten Bereich (unsortiert).
if arr[j] < arr[min_index]: wir vergleichen den Wert an Position j mit dem aktuellen Minimum.
Falls der Wert kleiner ist, speichern wir j als neuen min_index.

Damit finden wir das kleinste Element im Rest.

Schritt 4: Tausch einfügen

arr = [64, 25, 12, 22, 11]
n = len(arr)
 
for i in range(n - 1):
    min_index = i
    for j in range(i + 1, n):
        if arr[j] < arr[min_index]:
            min_index = j
    arr[i], arr[min_index] = arr[min_index], arr[i]   # Tausch

Erklärung:

Mit arr[i], arr[min_index] = arr[min_index], arr[i] tauschen wir die beiden Werte.
Dadurch wandert das kleinste gefundene Element nach vorne an Position i.

Jetzt wächst der sortierte Bereich links nach jedem Durchgang um ein Element.

Schritt 5: Ausgabe hinzufügen

arr = [64, 25, 12, 22, 11]
n = len(arr)
 
for i in range(n - 1):
    min_index = i
    for j in range(i + 1, n):
        if arr[j] < arr[min_index]:
            min_index = j
    arr[i], arr[min_index] = arr[min_index], arr[i]
 
print(arr)  # Ausgabe der sortierten Liste

Erklärung:

print(arr) zeigt die fertige, sortierte Liste auf dem Bildschirm.

Damit ist unser Algorithmus vollständig.

Zusammenfassung

Wir haben eine Liste mit Zahlen angelegt.
Mit einer äußeren Schleife gehen wir von links nach rechts durch.
Mit einer inneren Schleife suchen wir im Rest das kleinste Element.
Wir tauschen das gefundene Minimum nach vorne.
Am Ende ist die gesamte Liste sortiert.

Merksatz: Selection Sort teilt das Array in einen sortierten und einen unsortierten Teil. Mit jedem Schritt wächst der sortierte Bereich.

⏳ Lädt Dataview-Inhalt...

Eigenschaften von Selection Sort

Selection Sort ist ein einfacher Sortieralgorithmus. Er arbeitet deterministisch, das bedeutet: seine Laufzeit ist immer gleich – unabhängig davon, wie die Eingabe aussieht.

Zeitkomplexität

Selection Sort hat in jeder Situation eine quadratische Laufzeit. Das bedeutet, du benötigst immer etwa O(n²) Vergleiche.

In der ersten Runde vergleichst du (n-1) Elemente.
In der zweiten Runde vergleichst du (n-2) Elemente.
Das setzt sich fort bis 1 Vergleich in der letzten Runde.

Die Gesamtsumme lautet: (n-1) + (n-2) + … + 1 = n(n-1)/2 ≈ n²/2 → O(n²).

Die Zeitkomplexität ist also nicht von der Eingabereihenfolge abhängig.

Speicherkomplexität

Selection Sort benötigt nur einen konstanten Speicherbedarf. Das bedeutet: O(1) zusätzlicher Speicher.

Es wird direkt im ursprünglichen Array sortiert („in-place“).
Du brauchst nur wenige Hilfsvariablen, um Elemente zwischenzuspeichern.

Das macht den Algorithmus sehr speichereffizient.

Stabilität

Selection Sort ist nicht stabil. Gleiche Elemente können ihre ursprüngliche Reihenfolge verlieren. Das ist dann problematisch, wenn die relative Reihenfolge wichtig ist, zum Beispiel bei Mehrfachsortierungen.

Besonderheiten

Selection Sort zeichnet sich durch bestimmte Eigenschaften aus:

Es gibt immer maximal (n-1) Tauschvorgänge.
Er ist sehr einfach zu implementieren, wenige Zeilen Code reichen aus.
Die Performance ist vorhersagbar, aber auch immer gleich langsam.

Vor- und Nachteile

Selection Sort hat klare Stärken und Schwächen. Diese lassen sich übersichtlich gegenüberstellen:

Vorteile	Nachteile
Sehr einfach zu verstehen und umzusetzen	Immer langsam: auch bei bereits sortierten Daten
Geringer Speicherverbrauch (O(1))	Instabil: relative Reihenfolge gleicher Elemente geht verloren
Minimale Anzahl von Tauschoperationen	Nicht adaptiv: profitiert nicht von Vorsortierung
Funktioniert in-place, kein zusätzlicher Speicher nötig	Laufzeit immer O(n²)

Der Algorithmus eignet sich also vor allem dort, wo Speicherknappheit wichtiger ist als Geschwindigkeit.

Wann Selection Sort verwenden?

Selection Sort ist kein effizienter Algorithmus für große Datenmengen. Er eignet sich jedoch in speziellen Situationen.

Geeignet für:

Sehr kleine Datenmengen (z. B. < 50 Elemente)
Embedded Systems mit sehr wenig Speicher
Lernzwecke, um Sortieralgorithmen zu verstehen
Situationen, in denen Tauschoperationen besonders teuer sind

Nicht geeignet für:

Große Datenmengen (z. B. > 1000 Elemente)
Performance-kritische Anwendungen
Daten, die bereits teilweise sortiert sind

Alternativen

Es gibt mehrere Algorithmen, die in vielen Fällen besser geeignet sind und Selection Sort ersetzen können.

Insertion Sort: Besser, wenn die Daten schon teilweise sortiert sind.
Bubble Sort: Ebenfalls O(n²), aber adaptiv.
Quick Sort / Merge Sort: Sehr gut für große Datenmengen geeignet, da im Durchschnitt deutlich schneller.

⏳ Lädt Dataview-Inhalt...

Zusammenfassung

Zusammenfassung:

Grundidee von Selection Sort

Selection Sort ist ein einfacher Sortieralgorithmus, der eine Liste in einen sortierten und einen unsortierten Bereich aufteilt. Mit jedem Durchgang wird das kleinste Element im unsortierten Bereich gefunden und an die richtige Position im sortierten Bereich verschoben.

Array wird in zwei Bereiche aufgeteilt: sortiert (links) und unsortiert (rechts).
In jedem Schritt wird das kleinste Element aus dem unsortierten Teil ausgewählt.
Das gefundene Minimum wird mit dem aktuellen Start-Element getauscht.
Der sortierte Bereich wächst schrittweise, bis die gesamte Liste geordnet ist.

Damit übst du den Umgang mit systematischem Vorgehen, Vergleichen und Tauschoperationen.

Ablauf und Funktionsweise

Der Algorithmus arbeitet Schritt für Schritt, bis alle Elemente sortiert sind.

Beginn: sortierter Bereich ist leer, unsortierter Bereich enthält alle Elemente.
In jedem Durchgang wird das Minimum gesucht und an die richtige Stelle gesetzt.
Beispiel: [64, 25, 12, 22, 11] → [11, 12, 22, 25, 64].
Prozess: Starte links, suche das Minimum im Rest, tausche, gehe nach rechts.

So wird das Array deterministisch von links nach rechts sortiert.

Umsetzung in Python

Die Implementierung erfolgt mit zwei Schleifen und einer Tauschoperation.

arr = [64, 25, 12, 22, 11]  # unsortierte Liste
n = len(arr)                 # Anzahl der Elemente
 
for i in range(n - 1):
    min_index = i
    for j in range(i + 1, n):
        if arr[j] < arr[min_index]:  # Suche nach Minimum
            min_index = j
    arr[i], arr[min_index] = arr[min_index], arr[i]  # Tausch
 
print(arr)

Der Code durchsucht den unsortierten Teil nach dem kleinsten Element, tauscht es nach vorne und wiederholt den Vorgang. Am Ende ist das Array vollständig sortiert.

Eigenschaften und Komplexität

Selection Sort hat klare Eigenschaften, die ihn leicht verständlich, aber ineffizient machen.

Laufzeit: O(n²) in allen Fällen (immer gleich viele Vergleiche).
Speicherbedarf: O(1) (in-place, kein zusätzlicher Speicher nötig).
Stabilität: nicht stabil (gleiche Werte können ihre Reihenfolge verlieren).
Maximale Anzahl an Tauschvorgängen: n-1.

Der Algorithmus ist einfach, aber für große Datenmengen ungeeignet.

Vor- und Nachteile

Selection Sort bringt bestimmte Stärken und Schwächen mit sich.

Vorteile	Nachteile
Einfach zu verstehen und umzusetzen	Immer langsam, unabhängig von der Eingabe
Geringer Speicherbedarf (O(1))	Instabil bei gleichen Elementen
Wenige Tauschoperationen	Nicht adaptiv, profitiert nicht von Vorsortierung
Funktioniert in-place	Laufzeit immer O(n²)

Damit eignet er sich eher zum Lernen oder für spezielle Szenarien.

Anwendungsgebiete

Selection Sort wird selten produktiv eingesetzt, ist aber in bestimmten Kontexten sinnvoll.

Geeignet für:
- Sehr kleine Datenmengen (z. B. < 50 Elemente)
- Situationen mit extrem wenig Speicher (z. B. Embedded Systems)
- Lernzwecke, um Sortierprinzipien zu verstehen
- Szenarien, in denen Tauschoperationen teuer sind
Nicht geeignet für:
- Große Datenmengen (> 1000 Elemente)
- Performance-kritische Anwendungen
- Bereits teilweise sortierte Daten

Ausblick:

In der nächsten Lerneinheit beschäftigst du dich mit dem Insertion-Sort-Algorithmus, einem einfachen und gut nachvollziehbaren Verfahren zur Sortierung von Datenelementen. Du lernst, wie Elemente schrittweise an der richtigen Position in eine bereits sortierte Teilliste eingefügt werden und warum dieser Algorithmus besonders für kleine oder nahezu sortierte Datenmengen geeignet ist.

SkillForge | ATLAS

Explorer

Selection-Sort

Selection-Sort

Einführung

Lernziele

Nach dieser Einheit kannst du:

Überleitung

Was ist Selection Sort und warum ist er wichtig?

So funktioniert Selection Sort Schritt für Schritt

Beispiel: Array [64, 25, 12, 22, 11]

Algorithmus in Worten

Selection-Sort-Code

Schritt 1: Array anlegen und Länge bestimmen

Selection-Sort-Code

Schritt 2: Erste Schleife hinzufügen

Selection-Sort-Code

Schritt 3: Innere Schleife hinzufügen

Schritt 4: Tausch einfügen

Schritt 4: Tausch einfügen

Schritt 5: Ausgabe hinzufügen

Schritt 5: Ausgabe hinzufügen

Zusammenfassung

Eigenschaften von Selection Sort

Zeitkomplexität

Speicherkomplexität

Stabilität

Besonderheiten

Vor- und Nachteile

Wann Selection Sort verwenden?

Geeignet für:

Nicht geeignet für:

Alternativen

Zusammenfassung

Zusammenfassung:

Grundidee von Selection Sort

Ablauf und Funktionsweise

Umsetzung in Python

Eigenschaften und Komplexität

Vor- und Nachteile

Anwendungsgebiete

Ausblick:

Graphansicht

Inhaltsverzeichnis

Backlinks