Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
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 — linear! Klausur-Klassiker für die Frage "Wann geht's schneller als log?"
Klausur-Tipp: Bei Klausur-Fragen "Warum geht Radix Sort schneller als Mergesort?" — die Antwort liegt in der unteren Schranke. Mergesort vergleicht → . Radix Sort vergleicht NICHT, sondern nutzt die Ziffern direkt als Index → bei fester Stellenzahl.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
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?"
Ohne Vergleiche musst du die Werte selbst als Index nutzen — kein binärer Baum, keine Mindestpfadlänge
log n.
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.
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).
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.
O(n) averageVoraussetzung: 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.
| Algorithmus | Best | Avg | Worst | Speicher | Stabil | Vergleichs-basiert |
|---|---|---|---|---|---|---|
| Mergesort | O(nlog n) | O(nlog n) | O(nlog n) | O(n) | ja | ja |
| Quicksort | O(nlog n) | O(nlog n) | O(n²) | O(log n) |
*Stabil je nach Inner-Sort.
| Bedingung | Empfehlung |
|---|---|
| Ganzzahlen mit kleinem Wertebereich | Counting Sort |
| Strings, Integer mit fester Länge | Radix Sort |
Gleichverteilte Floats in [0, 1) | Bucket Sort |
| Beliebige Daten, kein Strukturwissen | Quicksort/Mergesort/Heapsort |
Faustregel: Nicht-vergleichsbasiertes Sortieren ist NICHT immer schneller — der Konstante kann groß sein, und der Speicherbedarf kann wachsen. Bei kleinem n oft Quicksort schneller.
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.
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.
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.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
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.
6 Aufgaben zu Counting Sort, Radix Sort, Bucket Sort, unterer Schranke.
Klausurfragen mit Lösungen (6)
Antwort: Ω(n log n)
Erklärung: Ω(n log n) — bewiesen über Entscheidungsbaum: n! Permutationen → Tiefe ≥ log(n!) = Θ(n log n). Vergleichs-Sortierungen wie Mergesort sind asymptotisch optimal innerhalb dieser Klasse.
Antwort: O(n + k) mit k = Wertebereich
Erklärung: O(n + k) — n für Iteration durch Array, k für Aufbau und Auswertung der Count-Array. Wenn k = O(n): linear. Wenn k riesig: schlechter als Mergesort.
Antwort: Falsch
Erklärung: FALSCH. Radix Sort braucht feste Stellen-Zahl d. Bei sehr großen Zahlen oder sehr unterschiedlichen Wertebereichen kann d groß werden. Konstanten sind oft groß. Quicksort ist in vielen praktischen Szenarien schneller.
Typ: Wahr/Falsch
Antwort: Counting Sort
Erklärung: Counting Sort ist stabil (gleiche Werte behalten ihre relative Reihenfolge). Mergesort auch. Quicksort, Heapsort, Selection Sort sind nicht stabil.
Richtige Antworten: Counting Sort funktioniert nur für ganze Zahlen; Radix Sort nutzt intern eine stabile Sortierung (oft Counting Sort); Untere Schranke O(n log n) gilt nur für Vergleichs-Sortierung; Radix Sort ist stabil
Erklärung: Richtig: Counting Sort nur Integer, Radix nutzt Counting (stable), untere Schranke nur vergleichsbasiert, Radix stabil. Falsch: Bucket Sort Worst O(n²) bei ungünstiger Verteilung; Counting Sort braucht O(n+k) extra Speicher (nicht in-place).
Typ: Multi-Select
Zuordnungen:
Erklärung: Wahl des Sortier-Algorithmus hängt von Datenstruktur ab. Counting für kleine Integer, Radix für Stellen-basierte, Bucket für gleichverteilte, Mergesort als Allzweck-stabile-Sortierung.
Typ: Zuordnung
Klausurfragen mit Lösungen (6)
Antwort: Der maximale Wert k im Array
Erklärung: Counting Sort braucht den Wertebereich [0, k). Daraus baut es die Zähl-Tabelle. Ohne k kann es nicht starten oder muss vorher den Maximum-Wert finden (linearer Scan).
Antwort: Wahr
Erklärung: RICHTIG. Höhere Stellen müssen die Sortier-Reihenfolge der niedrigeren Stellen respektieren. Wenn die Innen-Sortierung nicht stabil ist (z.B. Heapsort statt Counting Sort), zerstört Radix die teilweise sortierte Reihenfolge.
Typ: Wahr/Falsch
Antwort: Wenn k (Wertebereich) viel größer als n ist
Erklärung: Wenn k >> n. Counting Sort ist O(n+k). Mergesort ist O(n log n). Bei k = n² ist O(n+k) = O(n²) >> O(n log n). Counting Sort ist nur effizient bei kleinem Wertebereich.
Antwort: 4
Erklärung: 32-bit = 4 Bytes. Basis 256 = 1 Byte pro 'Stelle'. Also 4 Durchläufe. Bei kleinerer Basis (z.B. 10 dezimal): mehr Durchläufe (z.B. 10 für Zahlen bis 10 Mrd). Basis-Wahl wichtig für Effizienz.
Lösungen pro Lücke:
Erklärung: Vokabular nicht-vergleichsbasiertes Sortieren. Vergleichs-Klasse, Counting (k), Radix (stellenweise), Stelle/Ziffer.
Typ: Lückentext
Richtige Reihenfolge:
Erklärung: Standard-Counting-Sort-Workflow. Max → Zählen → Kumulieren → Output bauen (rückwärts für Stabilität) → Return. Laufzeit O(n+k).
Typ: Reihenfolge
| nein |
| ja |
| Heapsort | O(nlog n) | O(nlog n) | O(nlog n) | O(1) | nein | ja |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(n+k) | ja | nein |
| Radix Sort | O(dn) | O(dn) | O(dn) | O(n+b) | ja | nein |
| Bucket Sort | O(n+k) | O(n+k) | O(n²) | O(n+k) | ja* | nein |