Sortier-Algorithmen

Sortieren ist das Hallo-Welt der Algorithmik. Du wirst es in der Praxis selten selbst schreiben (dafuer gibt es fertige Funktionen), aber die Prinzipien sind fundamental.

Warum mehrere Algorithmen?

Warum nicht einfach der schnellste? Weil “schnellste” von der Situation abhaengt:

Kleine Listen: einfache Algorithmen sind konstanten-arm
Fast-sortiert: Insertion-Sort ist schneller als Quicksort
Stabile Sortierung: Merge-Sort, nicht Quicksort
In-place: Heap-Sort, nicht Merge-Sort
Parallel: Merge-Sort skaliert besser

Jeder Algorithmus hat Staerken und Schwaechen.

Bubble Sort - der Einsteiger

Idee: Gehe die Liste durch, tausche benachbarte Elemente, wenn sie in falscher Reihenfolge sind. Wiederhole, bis keine Vertauschung mehr noetig.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

Komplexitaet

Best: O(n) (mit Optimierung - wenn nichts getauscht wurde, ist fertig)
Average: O(n²)
Worst: O(n²)
Platz: O(1) - in-place

Wann nutzen?

Nie in Produktion. Zum Lernen und fuer sehr kleine Listen OK.

Selection Sort

Idee: Finde das kleinste Element und tausche es nach vorne. Wiederhole fuer den Rest.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Komplexitaet

Alles: O(n²) - immer gleich
Platz: O(1)

Wann nutzen?

Wenn Vertauschungen teuer sind (z.B. grosse Objekte) - Selection-Sort macht maximal n Swaps.

Insertion Sort

Idee: Baue eine sortierte Liste auf, indem du jedes Element in seine richtige Position einfuegst. Wie Karten im Fach sortieren.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

Komplexitaet

Best: O(n) - schon sortiert
Average: O(n²)
Worst: O(n²)
Platz: O(1)

Wann nutzen?

Kleine Listen (< 20 Elemente) - schneller als Quicksort in der Praxis
Fast-sortierte Listen
Als Base-Case von Hybrid-Sortieralgorithmen (Timsort, Introsort)

Merge Sort

Idee: Teile die Liste in zwei Haelften, sortiere beide rekursiv, dann merge zusammen.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mitte = len(arr) // 2
    links = merge_sort(arr[:mitte])
    rechts = merge_sort(arr[mitte:])

    return merge(links, rechts)

def merge(links, rechts):
    ergebnis = []
    i = j = 0
    while i < len(links) and j < len(rechts):
        if links[i] <= rechts[j]:
            ergebnis.append(links[i])
            i += 1
        else:
            ergebnis.append(rechts[j])
            j += 1
    ergebnis.extend(links[i:])
    ergebnis.extend(rechts[j:])
    return ergebnis

Komplexitaet

Alles: O(n log n) - konsistent schnell
Platz: O(n) - braucht Hilfsspeicher

Eigenschaften

Stabil: gleiche Werte behalten ihre Reihenfolge
Vorhersehbar: immer O(n log n)
Parallelisierbar: beide Haelften koennen parallel sortiert werden

Wann nutzen?

Wenn Stabilitaet wichtig ist
Wenn Worst-Case wichtig ist (bei Real-Time-Anwendungen)
Fuer Linked Lists (einfach implementierbar)

Quicksort

Idee: Waehle einen Pivot, partitioniere die Liste in “kleiner als Pivot” und “groesser”, sortiere beide rekursiv.

def quicksort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    links = [x for x in arr if x < pivot]
    mitte = [x for x in arr if x == pivot]
    rechts = [x for x in arr if x > pivot]

    return quicksort(links) + mitte + quicksort(rechts)

Komplexitaet

Best/Average: O(n log n)
Worst: O(n²) - wenn der Pivot immer schlecht ist (sortierte Liste, naiver Pivot)
Platz: O(log n) fuer den Rekursions-Stack

Vorteile in der Praxis

Schnellste Konstanten - in der Praxis oft schneller als Merge-Sort
In-place moeglich (mit clevererer Implementation)
Gute Cache-Lokalitaet

Nachteile

Nicht stabil
Worst-Case O(n²) - in boesen Faellen langsam

In-Place-Variante

def quicksort_inplace(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        p = partition(arr, low, high)
        quicksort_inplace(arr, low, p - 1)
        quicksort_inplace(arr, p + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

Heap Sort

Idee: Baue aus den Elementen einen Max-Heap, dann nimm immer das Maximum ans Ende.

import heapq

def heap_sort(arr):
    heap = arr.copy()
    heapq.heapify(heap)   # O(n)
    return [heapq.heappop(heap) for _ in range(len(heap))]

Komplexitaet

Alles: O(n log n) - wie Merge-Sort
Platz: O(1) - in-place moeglich

Wann nutzen?

Wenn du garantiertes O(n log n) und O(1) Platz brauchst
Nicht stabil - deshalb seltener genutzt als Merge oder Quick

Counting Sort

Fuer kleine Zahlenbereiche (z.B. Alter, Noten) - extrem schnell:

def counting_sort(arr, max_val):
    counts = [0] * (max_val + 1)
    for x in arr:
        counts[x] += 1

    ergebnis = []
    for wert, anzahl in enumerate(counts):
        ergebnis.extend([wert] * anzahl)
    return ergebnis

print(counting_sort([3, 1, 4, 1, 5, 9, 2, 6], 10))
# [1, 1, 2, 3, 4, 5, 6, 9]

Komplexitaet

Zeit: O(n + k) - k = max_val
Platz: O(k)

Wann nutzen?

Wenn k klein ist (z.B. Noten 1-6, Alter 0-120). Bei grossen k-Werten ineffizient.

Radix Sort

Sortiert Zahlen digit-by-digit - O(nk) wobei k = Anzahl Ziffern. Fuer Integer oft schneller als Vergleichs-basierte Algorithmen.

Pythons Timsort

Pythons sorted() und list.sort() nutzen Timsort - einen Hybrid aus Merge-Sort und Insertion-Sort, optimiert fuer real-world data (oft schon teilweise sortiert).

sorted(arr)        # O(n log n), stabil
arr.sort()          # gleiche, aber in-place

Immer, wenn du in Python sortierst: nutze die eingebaute Funktion, nicht deine eigene. Sie ist optimiert und korrekt.

Key-Funktion

woerter = ["Anna", "max", "Leo"]

sorted(woerter, key=str.lower)     # case-insensitive
sorted(woerter, key=len)           # nach Laenge
sorted(objekte, key=lambda x: x.alter)  # nach Attribut
sorted(data, key=lambda x: (x.alter, x.name))  # nach mehreren

Vergleich

Algorithmus	Best	Average	Worst	Platz	Stabil
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Ja
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	Nein
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Ja
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Ja
Quicksort	O(n log n)	O(n log n)	O(n²)	O(log n)	Nein
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	Nein
Timsort	O(n)	O(n log n)	O(n log n)	O(n)	Ja

Welcher wann?

In Python/JS/allem Modernen: eingebaute Funktion (Timsort, Dual-Pivot-Quicksort, …)
Selbst schreiben?: Merge-Sort zum Lernen, Quicksort fuer Performance
Sehr klein (< 20): Insertion-Sort
Kleine Integer-Bereiche: Counting/Radix

Praktisches Beispiel

Sortiere Personen nach mehreren Kriterien:

leute = [
    {"name": "Anna", "alter": 28, "stadt": "Berlin"},
    {"name": "Max",  "alter": 34, "stadt": "Muenchen"},
    {"name": "Leo",  "alter": 28, "stadt": "Koeln"},
    {"name": "Mia",  "alter": 28, "stadt": "Berlin"},
]

# Primaer nach Alter, sekundaer nach Stadt
sortiert = sorted(leute, key=lambda p: (p["alter"], p["stadt"]))

for p in sortiert:
    print(p["name"], p["alter"], p["stadt"])

Das nutzt Timsort + Tupel-Vergleich. Elegant.

Zusammenfassung

Quadratische Algorithmen (Bubble, Selection, Insertion) fuer Lernen und kleine Listen
O(n log n): Merge-Sort (stabil, braucht Platz), Quicksort (schnell, nicht stabil)
Heap-Sort fuer garantiertes O(n log n) mit O(1) Platz
Counting/Radix fuer spezielle Faelle mit kleinen Zahlen
Immer eingebaute Sortierung nutzen - Timsort/dual-pivot sind sehr gut

Im naechsten Kapitel: Such-Algorithmen - linear, binaer und mit Hash.