Nicht-vergleichsbasiertes Sortieren.

O(n log n) ist die untere Schranke fürs Sortieren, aber NUR wenn du vergleichst. Wenn du Annahmen über die Daten machen kannst (z.B. "alle Zahlen sind ≤ 1000"), gehts schneller: Counting Sort, Radix Sort und Bucket Sort schaffen O(n), linear! Klausur-Klassiker für die Frage "Wann geht's schneller als log?"

Die Idee in einem Satz

Ohne Vergleiche musst du die Werte selbst als Index nutzen, kein binärer Baum, keine Mindestpfadlänge log n.

Untere Schranke für Vergleichs-Sortieren

Theorem: Jeder Vergleichs-Sortier-Algorithmus braucht im Worst Case Ω(n log n) Vergleiche.

Beweis-Skizze: Ein Vergleichs-Algorithmus ist ein Entscheidungsbaum. n! mögliche Permutationen → Baum mit n! Blättern → Tiefe ≥ log(n!) = Θ(n log n).

Konsequenz: Mergesort, Heapsort, Quicksort sind optimal innerhalb der Vergleichs-Klasse. Wer schneller will, muss aus dieser Klasse raus.

Counting Sort: O(n + k)

Voraussetzung: Elemente sind ganze Zahlen aus \0, 1, 2, ..., k-1\.

Idee: Zähle für jeden möglichen Wert, wie oft er vorkommt. Daraus rekonstruiere das sortierte Array.

counting_sort(arr, k):
    count = array of zeros, size k
    for x in arr:
        count[x] += 1

    # Cumulative
    for i in 1 to k-1:
        count[i] += count[i-1]

    # Build output (stable)
    output = empty array, size len(arr)
    for x in reversed(arr):
        count[x] -= 1
        output[count[x]] = x

    return output

Laufzeit: O(n + k). Linear in n, wenn k klein ist.

Wenn k = O(n): O(n), schneller als jede Vergleichs-Sortierung! Wenn k riesig (z.B. k = n²): O(n²), schlechter als Mergesort.

Wichtig: Counting Sort ist stabil (gleiche Werte behalten Reihenfolge).

Radix Sort: O(d · (n + b))

Voraussetzung: Elemente haben d Ziffern in Basis b.

Idee: Sortiere stellenweise von der kleinsten zur größten Ziffer. Jede Stellen-Sortierung mit stabilem Algorithmus (typisch Counting Sort).

radix_sort(arr):
    for digit from least to most significant:
        stable_sort arr by digit (e.g. Counting Sort)
    return arr

Beispiel: [170, 45, 75, 90, 802, 24, 2, 66] mit Basis 10.

Ziffer 1 (1er): [170, 90, 802, 2, 24, 45, 75, 66] Ziffer 2 (10er): [802, 2, 24, 45, 66, 170, 75, 90] Ziffer 3 (100er): [2, 24, 45, 66, 75, 90, 170, 802] ✓

Laufzeit: O(d · (n + b)). Bei festem d (z.B. 32-bit-Integer) und konstantem b → O(n) linear.

Bucket Sort: O(n) average

Voraussetzung: Elemente gleichmäßig verteilt in einem bekannten Intervall.

Idee: Teile das Intervall in n Buckets, verteile Elemente, sortiere jeden Bucket separat, konkateniere.

bucket_sort(arr):
    n = len(arr)
    buckets = [empty array for _ in range(n)]
    for x in arr:
        i = floor(n * x)  # assumes x in [0, 1)
        buckets[i].append(x)
    for bucket in buckets:
        insertion_sort(bucket)
    return concatenate(buckets)

Average: O(n). Worst Case: O(n²) wenn alle Elemente in einem Bucket landen.

Vergleich der Sortier-Algorithmen

*Stabil je nach Inner-Sort.

Wann nicht-vergleichsbasiert?

Faustregel: Nicht-vergleichsbasiertes Sortieren ist NICHT immer schneller, der Konstante kann groß sein, und der Speicherbedarf kann wachsen. Bei kleinem n oft Quicksort schneller.

Klausur-Faustregeln

1. Untere Schranke Vergleichs-Sortieren: Ω(n log n). Argument: Entscheidungsbaum mit n! Blättern → Tiefe ≥ log(n!) = Θ(n log n).

2. Counting Sort: O(n+k). Schneller als Mergesort wenn k = O(n).

3. Radix Sort: O(d · (n+b)). Bei festem d → linear in n.

4. Stabilität: Counting + Radix sind stabil. Quicksort + Heapsort sind NICHT stabil.

5. Bucket Sort: average O(n), worst O(n²). Bei gleichverteilten Daten optimal.

Häufige Stolpersteine

1. Glauben, O(n log n) sei IMMER untere Schranke. Nur für VERGLEICHS-Algorithmen. Mit Annahmen über Daten geht's schneller.

2. Counting Sort mit großem k. Bei k = 10⁹ ist O(n + k) = O(10⁹), viel langsamer als Mergesort bei n = 1000. Speicherbedarf auch riesig.

3. Radix Sort instabil-implementieren. Stelle pro Stelle MUSS stabil sortiert werden (sonst falsche Reihenfolge bei höheren Stellen). Counting Sort als Inner-Sort ist Standard.

4. Bucket Sort mit ungleichverteilten Daten. Wenn alle Werte in einem Bucket landen → O(n²). Vorher Verteilung prüfen.

5. Quicksort als optimal-für-alles annehmen. Bei großen Datenmengen mit kleinem Wertebereich ist Counting/Radix oft 10× schneller.

Radix Sort Stepper

Sortiere das Array [170, 45, 75, 90, 802, 24, 2, 66] stellenweise (1er → 10er → 100er). Pro Stelle siehst du die Counting-Sort-Buckets.

Beobachte, wie nach JEDER Stellen-Sortierung das Array "ein bisschen" sortierter wird, und am Ende komplett sortiert ist.

Klausur-Tipp: Bei Klausur-Fragen "Warum geht Radix Sort schneller als Mergesort?", die Antwort liegt in der unteren Schranke. Mergesort vergleicht → Ω(n log n). Radix Sort vergleicht NICHT, sondern nutzt die Ziffern direkt als Index → O(n) bei fester Stellenzahl.

Nicht-vergleichsbasiertes Sortieren, Praxis-Übung

6 Aufgaben zu Counting Sort, Radix Sort, Bucket Sort, unterer Schranke.