Sortieralgorithmen: Prüfungsfragen mit Lösungsweg erklärt

In einer Klausur zu Algorithmen und Datenstrukturen fehlt die Sortieraufgabe fast nie, und meistens verlangt sie keinen Code: Sie bekommen ein Array und sollen „den Zustand nach jedem Durchlauf angeben“. In diesem Beitrag vergleiche ich die fünf klassischen Verfahren in einer Tabelle und löse danach die Aufgabentypen, die tatsächlich gestellt werden, von Hand und Schritt für Schritt. Punkte gehen selten verloren, weil der Algorithmus unbekannt ist, sondern weil die Ablaufverfolgung unvollständig oder im falschen Format notiert wird; deshalb zeigen die Lösungen auch das Format.

Falls Ihnen die Komplexitätsangaben nicht geläufig sind, lesen Sie zuerst den Leitfaden zu Big-O-Notation und Laufzeitkomplexität; die folgende Tabelle baut darauf auf.

Vergleichstabelle der fünf Algorithmen

Algorithmus	Best Case	Average Case	Worst Case	Zusatzspeicher	Stabil?	In-place?
Bubble Sort (mit Abbruch)	O(n)	O(n²)	O(n²)	O(1)	Ja	Ja
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	Nein	Ja
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Ja	Ja
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Ja	Nein
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n) Stack im Mittel	Nein	Ja

Zwei Begriffe müssen sitzen. Ein stabiles Sortierverfahren erhält die Eingabereihenfolge von Elementen mit gleichem Schlüssel. Ein Verfahren arbeitet in-place, wenn es kein zur Eingabe proportionales Hilfsarray braucht. Die Bubble-Sort-Zeile gilt für die Variante mit der Prüfung „kein Tausch, also fertig“; ohne sie ist auch der Best Case O(n²). Prüfen Sie immer, welche Variante in Ihrer Klausur gemeint ist.

Code: die drei einfachen Verfahren

Die Vergleichs- und Tauschzahlen in den Lösungen beziehen sich genau auf diesen Code.

static void BubbleSort(int[] a)
{
    for (int i = 0; i < a.Length - 1; i++)
    {
        bool swapped = false;
        for (int j = 0; j < a.Length - 1 - i; j++)
        {
            if (a[j] > a[j + 1])
            {
                (a[j], a[j + 1]) = (a[j + 1], a[j]);
                swapped = true;
            }
        }
        if (!swapped) break; // kein Tausch in diesem Durchlauf: Array ist sortiert
    }
}

static void SelectionSort(int[] a)
{
    for (int i = 0; i < a.Length - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < a.Length; j++)
            if (a[j] < a[min]) min = j;
        if (min != i) (a[i], a[min]) = (a[min], a[i]);
    }
}

static void InsertionSort(int[] a)
{
    for (int i = 1; i < a.Length; i++)
    {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key)
        {
            a[j + 1] = a[j]; // größeres Element um eine Stelle nach rechts schieben
            j--;
        }
        a[j + 1] = key;
    }
}

Code: Merge Sort und Quick Sort

static void MergeSort(int[] a, int left, int right)
{
    if (left >= right) return;
    int mid = (left + right) / 2;
    MergeSort(a, left, mid);
    MergeSort(a, mid + 1, right);
    Merge(a, left, mid, right);
}

static void Merge(int[] a, int left, int mid, int right)
{
    int[] l = a[left..(mid + 1)];
    int[] r = a[(mid + 1)..(right + 1)];
    int i = 0, j = 0, k = left;
    while (i < l.Length && j < r.Length)
        a[k++] = l[i] <= r[j] ? l[i++] : r[j++]; // <= erhält die Stabilität
    while (i < l.Length) a[k++] = l[i++];
    while (j < r.Length) a[k++] = r[j++];
}

static void QuickSort(int[] a, int low, int high)
{
    if (low >= high) return;
    int p = Partition(a, low, high);
    QuickSort(a, low, p - 1);
    QuickSort(a, p + 1, high);
}

// Lomuto-Partitionierung: Pivot = letztes Element
static int Partition(int[] a, int low, int high)
{
    int pivot = a[high];
    int i = low - 1;
    for (int j = low; j < high; j++)
    {
        if (a[j] < pivot)
        {
            i++;
            (a[i], a[j]) = (a[j], a[i]);
        }
    }
    (a[i + 1], a[high]) = (a[high], a[i + 1]);
    return i + 1;
}

Für Quick Sort gibt es mehrere Partitionierungsschemata (Lomuto, Hoare). Die Zwischenzustände unterscheiden sich; verwenden Sie das Schema aus Ihrem Vorlesungsskript und schreiben Sie an den Anfang der Lösung, welches Sie benutzt haben.

Aufgabe 1: Bubble Sort – das Array nach jedem Durchlauf

Aufgabe: Sortieren Sie [5, 1, 4, 2, 8] mit Bubble Sort (Variante mit Abbruch). Geben Sie das Array nach jedem Durchlauf sowie die Gesamtzahl der Vergleiche und Vertauschungen an.

Lösung: In jedem Durchlauf werden benachbarte Paare von links nach rechts verglichen; das größte Element „steigt“ ans Ende.

Start        : [5, 1, 4, 2, 8]
Durchlauf 1  : [1, 4, 2, 5, 8]   4 Vergleiche, 3 Vertauschungen (5-1, 5-4, 5-2)
Durchlauf 2  : [1, 2, 4, 5, 8]   3 Vergleiche, 1 Vertauschung (4-2)
Durchlauf 3  : [1, 2, 4, 5, 8]   2 Vergleiche, 0 Vertauschungen -> Abbruch

Insgesamt 9 Vergleiche und 4 Vertauschungen. Ohne Abbruch käme ein vierter Durchlauf mit 1 Vergleich hinzu, also n(n−1)/2 = 10. Das Array ist bereits nach Durchlauf 2 sortiert, der Algorithmus merkt es aber erst in Durchlauf 3, dem ersten ohne Tausch; diesen Durchlauf wegzulassen ist der häufigste Fehler.

Aufgabe 2: Ablauf von Selection Sort

Aufgabe: Sortieren Sie [64, 25, 12, 22, 11] mit Selection Sort und zeigen Sie jeden Durchlauf.

Lösung: Jeder Durchlauf sucht das Minimum des unsortierten Teils und tauscht es genau einmal mit dessen erstem Element.

Start        : [64, 25, 12, 22, 11]
Durchlauf 1  : [11, 25, 12, 22, 64]   Minimum 11 <-> 64
Durchlauf 2  : [11, 12, 25, 22, 64]   Minimum 12 <-> 25
Durchlauf 3  : [11, 12, 22, 25, 64]   Minimum 22 <-> 25
Durchlauf 4  : [11, 12, 22, 25, 64]   Minimum 25 steht schon richtig, kein Tausch

Die Zahl der Vergleiche hängt nicht von der Eingabe ab: 4 + 3 + 2 + 1 = 10. Es gibt 3 Vertauschungen. Das ist die eine echte Stärke von Selection Sort: höchstens n−1 Vertauschungen, was zählt, wenn Schreibzugriffe teuer sind.

Aufgabe 3: Insertion Sort und Vergleiche zählen

Aufgabe: Sortieren Sie [7, 3, 5, 1, 9, 2] mit Insertion Sort. Geben Sie für jeden Schritt die Zahl der Vergleiche und Verschiebungen an.

Lösung: Ein „Vergleich“ ist hier eine Auswertung von a[j] > key.

Start        : [7, 3, 5, 1, 9, 2]
i=1, key=3   : [3, 7, 5, 1, 9, 2]   1 Vergleich,  1 Verschiebung
i=2, key=5   : [3, 5, 7, 1, 9, 2]   2 Vergleiche, 1 Verschiebung
i=3, key=1   : [1, 3, 5, 7, 9, 2]   3 Vergleiche, 3 Verschiebungen
i=4, key=9   : [1, 3, 5, 7, 9, 2]   1 Vergleich,  0 Verschiebungen
i=5, key=2   : [1, 2, 3, 5, 7, 9]   5 Vergleiche, 4 Verschiebungen

Insgesamt 12 Vergleiche und 9 Verschiebungen. Zur Kontrolle: Die Zahl der Verschiebungen entspricht der Zahl der Inversionen (Fehlstände) im Array. Die Inversionen sind (7,3), (7,5), (7,1), (7,2), (3,1), (3,2), (5,1), (5,2), (9,2) – genau 9.

Aufgabe 4: Merge Sort – Teilungs- und Mischbaum

Aufgabe: Geben Sie für [38, 27, 43, 3, 9, 82, 10] die Mischschritte von Merge Sort in der Reihenfolge ihrer Ausführung an.

Lösung: Mit mid = (left + right) / 2 wird das Array mit 7 Elementen in 4 + 3 geteilt. Gemischt wird in der Reihenfolge, in der die Rekursion zurückkehrt:

Teilen: [38, 27, 43, 3]                 [9, 82, 10]
        [38, 27]   [43, 3]              [9, 82]   [10]

1) [38] + [27]            -> [27, 38]                      1 Vergleich
2) [43] + [3]             -> [3, 43]                       1 Vergleich
3) [27, 38] + [3, 43]     -> [3, 27, 38, 43]               3 Vergleiche
4) [9] + [82]             -> [9, 82]                       1 Vergleich
5) [9, 82] + [10]         -> [9, 10, 82]                   2 Vergleiche
6) [3, 27, 38, 43] + [9, 10, 82] -> [3, 9, 10, 27, 38, 43, 82]   6 Vergleiche

Zusammen 14 Vergleiche. Beachten Sie: Die linke Hälfte wird vollständig abgearbeitet, bevor die rechte beginnt; wer Schritt 4 vor Schritt 2 notiert, stellt die Rekursionsreihenfolge falsch dar.

Aufgabe 5: Quick Sort – die erste Partitionierung

Aufgabe: Wenden Sie auf [10, 80, 30, 90, 40, 50, 70] die Lomuto-Partitionierung mit dem letzten Element als Pivot an. Wie sieht das Array nach der ersten Partitionierung aus?

Lösung: Pivot = 70, i = -1. j läuft von links nach rechts; für jedes Element kleiner als das Pivot wird i erhöht und das Element mit a[i] getauscht.

j=0 (10 < 70)  i=0  [10, 80, 30, 90, 40, 50, 70]
j=1 (80)       -    [10, 80, 30, 90, 40, 50, 70]
j=2 (30 < 70)  i=1  [10, 30, 80, 90, 40, 50, 70]
j=3 (90)       -    [10, 30, 80, 90, 40, 50, 70]
j=4 (40 < 70)  i=2  [10, 30, 40, 90, 80, 50, 70]
j=5 (50 < 70)  i=3  [10, 30, 40, 50, 80, 90, 70]
Letzter Tausch a[4] <-> a[6]:  [10, 30, 40, 50, 70, 90, 80]

Das Pivot 70 landet auf Index 4, seiner endgültigen Position. Die Rekursion läuft mit [10, 30, 40, 50] und [90, 80] weiter; der rechte Teil wird mit einer Partitionierung zu [80, 90]. Die gesamte Sortierung kostet 6 + 3 + 2 + 1 + 1 = 13 Vergleiche.

Aufgabe 6: Worst Case von Quick Sort und Pivotwahl

Aufgabe: Das Pivot ist immer das letzte Element. Wie viele Vergleiche braucht [1, 2, 3, 4, 5, 6]? Wie lässt sich das vermeiden?

Lösung: Das Array ist sortiert, das Pivot ist also jedes Mal das Maximum; jede Partitionierung liefert einen Teil mit n−1 Elementen und einen leeren Teil. Die Vergleiche summieren sich zu 5 + 4 + 3 + 2 + 1 = 15 = n(n−1)/2, also O(n²). Die Rekursionstiefe wächst auf n, der Zusatzspeicher damit auf O(n). Dasselbe passiert bei einem absteigend sortierten Array und mit dem ersten Element als Pivot.

Abhilfe schafft eine Pivotwahl, die nicht von der Eingabe abhängt: ein zufälliges Pivot oder der Median aus erstem, mittlerem und letztem Element (Median-of-three).

// Am Anfang von Partition ergänzen: zufälliges Element ans Ende tauschen, Rest unverändert
int r = Random.Shared.Next(low, high + 1);
(a[r], a[high]) = (a[high], a[r]);

Ein zufälliges Pivot beseitigt den Worst Case nicht, macht ihn aber unabhängig von einer bestimmten Eingabe; die erwartete Laufzeit ist O(n log n).

Aufgabe 7: Welches Verfahren ist stabil? Ein kleines Szenario

Aufgabe: Nach Namen sortierte Datensätze sollen nach Note sortiert werden: (Ali,85), (Berk,70), (Can,85), (Deniz,70). Vergleichen Sie die Ausgabe von Selection Sort und Insertion Sort.

Lösung:

Selection Sort:
Durchlauf 1 : (Berk,70), (Ali,85), (Can,85), (Deniz,70)
Durchlauf 2 : (Berk,70), (Deniz,70), (Can,85), (Ali,85)   <- Ali steht jetzt hinter Can
Durchlauf 3 : keine Änderung

Insertion Sort:
Ergebnis    : (Berk,70), (Deniz,70), (Ali,85), (Can,85)

Der Tausch über große Distanz hat Ali hinter Can befördert: Zwei Datensätze mit gleicher Note haben die Reihenfolge gewechselt, Selection Sort ist also nicht stabil. Insertion Sort verschiebt nur echt größere Elemente und erhält die Namensreihenfolge. Dieselbe Unterscheidung gilt in echtem Code: In .NET sind Array.Sort und List<T>.Sort instabil, LINQ OrderBy ist stabil.

var students = new[] { ("Ali", 85), ("Berk", 70), ("Can", 85), ("Deniz", 70) };
var byGrade = students.OrderBy(s => s.Item2).ToArray(); // Namensreihenfolge bleibt bei gleicher Note erhalten

Aufgabe 8: Fast sortierte Daten und Schranken für Vergleiche

Aufgabe: (a) Welchen Algorithmus wählen Sie für ein fast sortiertes Array wie [1, 2, 4, 3, 5, 6, 8, 7], und warum? (b) Wie viele Vergleiche sind mindestens und höchstens nötig, wenn zwei sortierte Arrays mit je 4 Elementen gemischt werden?

Lösung (a): Insertion Sort. Die Laufzeit ist O(n + d), wobei d die Zahl der Inversionen ist. Hier ist d = 2, es genügen 9 Vergleiche und 2 Verschiebungen. Selection Sort führt auf demselben Array in jedem Fall 28 Vergleiche aus. Bubble Sort mit Abbruch ist nach 7 + 6 = 13 Vergleichen fertig; steht aber ein kleines Element am Ende (zum Beispiel [2, 3, 4, 5, 1]), wandert es pro Durchlauf nur eine Stelle nach links, und die Zahl der Durchläufe nähert sich n. Merge Sort profitiert von der Vorsortierung gar nicht.

Lösung (b): Mindestens 4: Sind alle Elemente des einen Arrays kleiner als die des anderen ([1,2,3,4] + [5,6,7,8]), ist dieses Array nach vier Vergleichen erschöpft, der Rest wird kopiert. Höchstens n + m − 1 = 7: Wechseln sich die Elemente ab ([1,3,5,7] + [2,4,6,8]), ist bis zum letzten Element in jedem Schritt ein Vergleich nötig.

Wann verwenden – und wann nicht?

• Insertion Sort: kleine Arrays (einige Dutzend Elemente) und fast sortierte Daten. Nicht für große Zufallsdaten.
• Merge Sort: wenn Stabilität und garantierte O(n log n) gefordert sind, außerdem für verkettete Listen oder Daten, die nicht in den Arbeitsspeicher passen. Nicht, wenn O(n) Zusatzspeicher ein Problem ist.
• Quick Sort: Allzweck-Sortierung im Arbeitsspeicher; mit guter Pivotwahl in der Praxis schnell. Wenn Stabilität nötig oder der Worst Case nicht akzeptabel ist, nehmen Sie Merge Sort oder Heap Sort.
• Bubble und Selection Sort: Lehrbeispiele. In produktivem Code verwenden Sie Array.Sort oder OrderBy statt einer eigenen Sortierung; der Wert dieser Algorithmen liegt darin, Verhalten und Kosten der fertigen Methoden zu verstehen.

Wenn Daten bei ständigem Einfügen und Löschen sortiert bleiben sollen, ist eine sortierte Struktur wie ein binärer Suchbaum das bessere Werkzeug, als immer wieder neu zu sortieren.

Häufige Fehler

1. Falsche Grenze der inneren Schleife. Mit j < a.Length greift a[j + 1] über das Array hinaus, und das Programm stürzt mit IndexOutOfRangeException ab. Richtig ist j < a.Length - 1 - i; das vergessene - i führt nicht zum Absturz, sondern nur zu unnötigen Vergleichen.

2. Stabilität mit einem Zeichen zerstören. >= statt a[j] > key bei Insertion Sort oder < statt <= beim Mischen sortiert weiterhin korrekt, vertauscht aber gleiche Elemente. Das Symptom ist tückisch: Tests mit reinen Zahlen laufen durch, Datensätze kommen in falscher Reihenfolge heraus.

while (j >= 0 && a[j] >= key) // FALSCH: verschiebt auch gleiche Elemente, Stabilität geht verloren
while (j >= 0 && a[j] > key)  // RICHTIG

3. Bei Selection Sort bei jedem kleineren Element tauschen. Selection Sort tauscht höchstens einmal pro Durchlauf. Wer beim Durchsuchen sofort tauscht, sobald ein kleineres Element auftaucht, verfolgt einen anderen Algorithmus, und die Zwischenzustände passen nicht zur Musterlösung.

4. „Quick Sort ist O(n log n)“ schreiben und weitergehen. Das ist der Average Case. Fragt die Aufgabe nach dem Worst Case, lautet die Antwort O(n²), und es wird erwartet, dass Sie die auslösende Kombination aus Eingabe und Pivot nennen.

Wenn Sie diese Aufgabentypen an den Altklausuren Ihrer eigenen Vorlesung üben möchten, beschreibt die Seite zur Prüfungsvorbereitung, wie ich dabei vorgehe.

Häufig gestellte Fragen

Welcher Sortieralgorithmus kommt in Klausuren am häufigsten vor?

Bei Ablaufaufgaben dominieren Bubble, Selection und Insertion Sort, bei Analyseaufgaben die Rekursion von Merge Sort und der Worst Case von Quick Sort. Am sichersten ist es, alle fünf von Hand durchspielen zu können.

Warum ist Quick Sort so verbreitet, obwohl der Worst Case O(n²) ist?

Das Verfahren arbeitet in-place, ist cachefreundlich, und mit zufälligem oder Median-of-three-Pivot tritt der Worst Case in der Praxis sehr selten auf. Die konstanten Faktoren im Average Case sind tendenziell kleiner als bei Merge Sort.

Wann ist ein stabiles Sortierverfahren wirklich wichtig?

Wenn dieselben Daten nacheinander nach mehreren Schlüsseln sortiert werden. Wer erst nach Namen und dann nach Note sortiert und innerhalb gleicher Noten die Namensreihenfolge behalten will, braucht für die zweite Sortierung ein stabiles Verfahren.

Was genau zähle ich bei der Frage nach der Anzahl der Vergleiche?

Nur Operationen, die zwei Datenelemente miteinander vergleichen; Indexprüfungen wie j >= 0 zählen nicht. Definiert Ihre Lehrkraft es anders, verwenden Sie deren Definition und schreiben Sie an den Anfang der Lösung, was Sie gezählt haben.