Algorithmen4Lerneinheiten21minStand30.05.2026

Nicht-vergleichsbasiertes Sortieren.

Fachliche Qualität

Noch nicht klassifiziertNoch nicht geprüft.

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.

Klausur-ÜbersichtKomplette Übersicht: alle Tabs als linearer Text zum Lernen

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).

Teil 1·Erklärung

Erklärung

Zur KategorieAlgorithmen.Mehr Themen entdeckenZum Themen-Hub.

Nicht-vergleichsbasiertes Sortieren, Algorithmen · UniProMax

$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 $\Omega(n \log n)$ Vergleiche.

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

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

Voraussetzung: Elemente sind ganze Zahlen aus $\{0, 1, 2, \ldots, 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^2$ ): $O(n^2)$ — schlechter als Mergesort.

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

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 \cdot (n + b))$ . Bei festem $d$ (z.B. 32-bit-Integer) und konstantem $b$ → $O(n)$ linear.

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^2)$ wenn alle Elemente in einem Bucket landen.

Algorithmus	Best	Avg	Worst	Speicher	Stabil	Vergleichs-basiert
Mergesort	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	ja	ja
Quicksort	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(\log n)$	nein	ja
Heapsort	$O(n\log n)$	$O(n\log n)$	$O(n\log 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^2)$	$O(n+k)$	ja*	nein

*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: $\Omega(n \log n)$ . Argument: Entscheidungsbaum mit $n!$ Blättern → Tiefe $\geq \log(n!) = \Theta(n \log n)$ .

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

3. Radix Sort: $O(d \cdot (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^2)$ . 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^9$ ist $O(n + k)$ = $O(10^9)$ — 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^2)$ . 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.

Lade Visualisierung...

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

Anmelden, um den Fortschritt zu speichern.

Nächster Schritt

Wenn du fertig bist: jetzt üben.

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?"

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

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.

Wann nicht-vergleichsbasiert?

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.

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.

Teil 3·Quiz / Klausurfragen

Praxis-Übung

Nicht-vergleichsbasiertes Sortieren — Praxis-Übung

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

Klausurfragen mit Lösungen (6)

F1.Was ist die untere Schranke für Vergleichs-Sortierung im Worst Case?

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.

F2.Welche Laufzeit hat Counting Sort?

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.

F3.Radix Sort ist asymptotisch immer schneller als Quicksort.

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

F4.Welcher der folgenden Algorithmen ist STABIL?

Antwort: Counting Sort

Erklärung: Counting Sort ist stabil (gleiche Werte behalten ihre relative Reihenfolge). Mergesort auch. Quicksort, Heapsort, Selection Sort sind nicht stabil.

F5.Welche Aussagen sind RICHTIG?

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

F6.Ordne Algorithmus dem Anwendungsfall zu:

Zuordnungen:

Counting Sort → Kleine Integer-Werte (z.B. Noten 1-15)
Radix Sort → Integer mit fester Stellenzahl oder Strings
Bucket Sort → Gleichverteilte Floats in [0, 1)
Mergesort → Beliebige Daten, kein Struktur-Wissen, Stabilität gebraucht

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

Teil 4·Quiz / Klausurfragen

Klausur-Quiz

Klausurfragen mit Lösungen (6)

F1.Welche Information BRAUCHT Counting Sort, um zu funktionieren?

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).

F2.Bei Radix Sort MUSS die Innen-Sortierung pro Stelle stabil sein, sonst funktioniert das Verfahren nicht.

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

F3.Wann ist Counting Sort SCHLECHTER als Mergesort?

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.

F4.Du sortierst 10.000 32-bit-Integer mit Radix Sort in Basis 256. Wie viele Stellen-Durchläufe?

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.

F5.Die untere Schranke für {{1}}-basiertes Sortieren ist Ω(n log n). {{2}} Sort braucht Wertebereich k und ist O(n+k). {{3}} Sort sortiert stellenweise von der niedrigsten zur höchsten {{4}} mit einer stabilen Innen-Sortierung.

Lösungen pro Lücke:

{{1}}: vergleichs / Vergleich
{{2}}: Counting
{{3}}: Radix
{{4}}: Stelle / Ziffer / Digit

Erklärung: Vokabular nicht-vergleichsbasiertes Sortieren. Vergleichs-Klasse, Counting (k), Radix (stellenweise), Stelle/Ziffer.

Typ: Lückentext

F6.Sortiere: Counting Sort.

Richtige Reihenfolge:

Finde max. Wert k im Array
Initialisiere Count-Array der Größe k+1, zähle Häufigkeiten
Kumuliere: count[i] += count[i-1]
Iteriere Eingabe rückwärts, platziere in Output-Array
Output-Array zurückgeben (sortiert + stabil)

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

Nicht-vergleichsbasiertes Sortieren.

Erklärung

Nicht-vergleichsbasiertes Sortieren.

Erklärung

Die Idee in einem Satz

Untere Schranke für Vergleichs-Sortieren

Counting Sort: $O(n + k)$

Radix Sort: $O(d \cdot (n + b))$

Bucket Sort: $O(n)$ average

Vergleich der Sortier-Algorithmen

Wann nicht-vergleichsbasiert?

Klausur-Faustregeln

Häufige Stolpersteine

Radix Sort Stepper

Wenn du fertig bist: jetzt üben.

Die Idee in einem Satz

Untere Schranke für Vergleichs-Sortieren

Counting Sort: `O(n + k)`

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

Bucket Sort: `O(n)` average

Vergleich der Sortier-Algorithmen

Wann nicht-vergleichsbasiert?

Klausur-Faustregeln

Häufige Stolpersteine

Interaktiv verstehen

Radix Sort Stepper

Praxis-Übung

Nicht-vergleichsbasiertes Sortieren — Praxis-Übung

Klausur-Quiz

Erklärung

Erklärung

Die Idee in einem Satz

Untere Schranke für Vergleichs-Sortieren

Counting Sort: O(n+k)O(n + k)O(n+k)

Radix Sort: O(d⋅(n+b))O(d \cdot (n + b))O(d⋅(n+b))

Bucket Sort: O(n)O(n)O(n) average

Vergleich der Sortier-Algorithmen

Wann nicht-vergleichsbasiert?

Klausur-Faustregeln

Häufige Stolpersteine

Radix Sort Stepper

Wenn du fertig bist: jetzt üben.

Die Idee in einem Satz

Untere Schranke für Vergleichs-Sortieren

Counting Sort: O(n + k)

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

Bucket Sort: O(n) average

Vergleich der Sortier-Algorithmen

Wann nicht-vergleichsbasiert?

Klausur-Faustregeln

Häufige Stolpersteine

Interaktiv verstehen

Radix Sort Stepper

Praxis-Übung

Nicht-vergleichsbasiertes Sortieren — Praxis-Übung

Klausur-Quiz

Counting Sort: $O(n + k)$

Radix Sort: $O(d \cdot (n + b))$

Bucket Sort: $O(n)$ average

Counting Sort: `O(n + k)`

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

Bucket Sort: `O(n)` average