Stabiles Sortieren und die eingebaute Sortierung

Kurz gesagt: Eine stabile Sortierung lässt Elemente mit gleichem Schlüssel in ihrer ursprünglichen Reihenfolge; in C# sind List.Sort und Array.Sort nicht stabil, LINQ OrderBy dagegen schon.

Problem

Die Daten, die durcheinandergeraten

Im Admin-Bereich des Shops liegen die Bestellungen nach Datum vor: die älteste oben. Ein Mitarbeiter klickt auf die Überschrift „Kunde“, um die Bestellungen jedes Kunden zusammen zu sehen. Er erwartet, dass die Bestellungen von Jonas untereinander stehen, und weiterhin nach Datum.

Das ergibt eine Sortierung nach Kunde mit Selectionsort:

record Order(string Date, string Customer, decimal Amount);

static bool Before(Order x, Order y)
{
    return string.CompareOrdinal(x.Customer, y.Customer) < 0;
}

static void SelectionSort(Order[] orders)
{
    for (int i = 0; i < orders.Length - 1; i++)
    {
        int smallest = i;
        for (int j = i + 1; j < orders.Length; j++)
        {
            if (Before(orders[j], orders[smallest]))
            {
                smallest = j;
            }
        }
        (orders[i], orders[smallest]) = (orders[smallest], orders[i]);
    }
}

Order[] orders =
[
    new("2026-10-03", "Jonas", 42.50m),
    new("2026-10-05", "Maria", 18.00m),
    new("2026-10-07", "Jonas", 120.00m),
    new("2026-10-09", "Peter", 64.90m),
    new("2026-10-12", "Maria", 35.20m),
    new("2026-10-15", "Jonas", 9.99m),
];
SelectionSort(orders);
foreach (Order o in orders)
{
    Console.WriteLine($"{o.Customer} {o.Date}");
}

Jonas 2026-10-03
Jonas 2026-10-07
Jonas 2026-10-15
Maria 2026-10-12
Maria 2026-10-05
Peter 2026-10-09

Die Kunden sind sortiert. Aber bei Maria steht die Bestellung vom 12. Oktober vor der vom 5. Oktober. Der Mitarbeiter sieht Marias letzte Bestellung als erste und ruft sie wegen der falschen an.

Die Idee

Stabilität: Gleiche Schlüssel behalten ihre Reihenfolge

Eine Sortierung ist stabil, wenn Elemente mit gleichem Schlüssel in der Reihenfolge bleiben, in der sie waren. Marias zwei Bestellungen haben einen gleichen Schlüssel (den Kunden). Eine stabile Sortierung lässt sie, wie sie kamen: zuerst der 5. Oktober, dann der 12.

Welche Algorithmen stabil sind:

Insertionsort: Er bewegt ein Element nur an echt größeren vorbei, springt also nie über ein gleiches;
Mergesort: Bei Gleichstand nimmt er aus der linken Hälfte (Mergesort);
Countingsort: Er sortiert von links nach rechts ein (Countingsort).

Welche nicht:

Selectionsort, Quicksort und Heapsort. Alle drei tauschen Elemente über Entfernung. Der Tausch trägt ein Element über alles zwischen den zwei Plätzen, und die gleichen dazwischen bleiben hinter ihm zurück.

Stabilität zählt nur, wenn das Element mehr als den Schlüssel trägt. Zwei gleiche Zahlen 5 lassen sich nicht unterscheiden. Zwei Bestellungen von Maria schon.

Sieh es dir an

Selectionsort gegen Insertionsort

Dieselbe Liste mit Insertionsort:

static void InsertionSort(Order[] orders)
{
    for (int i = 1; i < orders.Length; i++)
    {
        Order current = orders[i];
        int j = i - 1;
        while (j >= 0 && Before(current, orders[j]))
        {
            orders[j + 1] = orders[j];
            j--;
        }
        orders[j + 1] = current;
    }
}

Order[] orders =
[
    new("2026-10-03", "Jonas", 42.50m),
    new("2026-10-05", "Maria", 18.00m),
    new("2026-10-07", "Jonas", 120.00m),
    new("2026-10-09", "Peter", 64.90m),
    new("2026-10-12", "Maria", 35.20m),
    new("2026-10-15", "Jonas", 9.99m),
];
InsertionSort(orders);
foreach (Order o in orders)
{
    Console.WriteLine($"{o.Customer} {o.Date}");
}

Jonas 2026-10-03
Jonas 2026-10-07
Jonas 2026-10-15
Maria 2026-10-05
Maria 2026-10-12
Peter 2026-10-09

static void SelectionSort(Order[] orders)
{
    for (int i = 0; i < orders.Length - 1; i++)
    {
        int smallest = i;
        for (int j = i + 1; j < orders.Length; j++)
        {
            if (Before(orders[j], orders[smallest]))
            {
                smallest = j;
            }
        }
        (orders[i], orders[smallest]) = (orders[smallest], orders[i]);
    }
}

static void InsertionSort(Order[] orders)
{
    for (int i = 1; i < orders.Length; i++)
    {
        Order current = orders[i];
        int j = i - 1;
        while (j >= 0 && Before(current, orders[j]))
        {
            orders[j + 1] = orders[j];
            j--;
        }
        orders[j + 1] = current;
    }
}

Schritt für Schritt, in Worten

Sechs Bestellungen, nach Datum sortiert. Jetzt nach Kunde, mit Selectionsort.
Platz 0: Der kleinste Kunde ab hier ist Jonas 03.10., steht schon an seinem Platz.
Platz 1: Jonas 07.10. tauscht mit Maria 05.10.
Platz 2: Jonas 15.10. tauscht mit Maria 05.10.. Der weite Tausch wirft Maria 05.10. nach hinten, hinter Maria 12.10..
Zwei weitere Tausche: Maria kommt vor Peter.
Nach Kunde sortiert, aber Maria 12.10. steht vor Maria 05.10.. Selectionsort ist nicht stabil: Gleiche Schlüssel können ihre Reihenfolge verlieren.
Dieselbe Liste mit Insertionsort. Eine Bestellung rückt nur an echt größeren vorbei, also bleibt Maria 05.10. vor Maria 12.10.. Stabil.

Die Bestellung, die Insertionsort nach links bewegt, hält vor der ersten an, die nicht größer ist. Über eine gleiche wird nicht gesprungen, und Marias Daten bleiben 05, dann 12.

Probier es aus

Finde den Fehler

Jemand hat einen Vergleich im Insertionsort geändert. Die Sortierung ist weiterhin nach Kunde, aber die Daten innerhalb jedes Kunden kommen umgekehrt heraus:

static void InsertionSort(Order[] orders)
{
    for (int i = 1; i < orders.Length; i++)
    {
        Order current = orders[i];
        int j = i - 1;
        while (j >= 0 && !Before(orders[j], current))
        {
            orders[j + 1] = orders[j];
            j--;
        }
        orders[j + 1] = current;
    }
}

Order[] orders =
[
    new("2026-10-03", "Jonas", 42.50m),
    new("2026-10-05", "Maria", 18.00m),
    new("2026-10-07", "Jonas", 120.00m),
    new("2026-10-09", "Peter", 64.90m),
    new("2026-10-12", "Maria", 35.20m),
    new("2026-10-15", "Jonas", 9.99m),
];
InsertionSort(orders);
foreach (Order o in orders)
{
    Console.WriteLine($"{o.Customer} {o.Date}");
}

Jonas 2026-10-15
Jonas 2026-10-07
Jonas 2026-10-03
Maria 2026-10-12
Maria 2026-10-05
Peter 2026-10-09

In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Die Bedingung lautet jetzt „die vorige liegt nicht vor der aktuellen“, das heißt, die vorige ist größer oder gleich. Die aktuelle rückt auch vor die gleichen, und die Bestellungen eines Kunden kommen in umgekehrter Reihenfolge heraus. Setze den strengen Vergleich wieder ein: Before(current, orders[j]).

Sieh es dir an

Die eingebaute Sortierung

In der Praxis schreibst du keine eigene Sortierung, du benutzt die eingebaute. Zwanzig Bestellungen, nach Datum, nach Kunde sortiert. Ausgegeben werden die Daten jedes Kunden:

In C# sind Array.Sort und List.Sort nicht stabil: Die Dokumentation sagt es ausdrücklich. LINQ OrderBy ist stabil. Hier beide mit derselben Liste:

Order[] copy = (Order[])orders.Clone();
Array.Sort(copy, (x, y) => string.CompareOrdinal(x.Customer, y.Customer));
Show(copy);

Show(orders.OrderBy(o => o.Customer, StringComparer.Ordinal));

Jonas: 01 18 04 06 09 12 15
Maria: 02 05 08 19 11 13 16
Peter: 17 10 07 03 14 20
Jonas: 01 04 06 09 12 15 18
Maria: 02 05 08 11 13 16 19
Peter: 03 07 10 14 17 20

Die ersten drei Zeilen stammen von Array.Sort: Bei Jonas kommt der 18. Oktober gleich nach dem 1., und bei Peter sind die Daten fast umgekehrt. Die nächsten drei stammen von OrderBy: Die Daten sind in Ordnung. Die Ausgabe von Array.Sort stammt aus einem Lauf unter .NET 10. Sie ist bei jedem Lauf gleich, aber niemand verspricht sie: Eine andere Version oder eine andere Eingabe ergibt eine andere Reihenfolge. Bei 16 Elementen oder weniger nutzt Array.Sort Insertionsort und behält die Reihenfolge zufällig. Verlass dich nicht darauf.

Die Idee

Was die eingebaute Sortierung jeder Sprache benutzt

Java. Arrays.sort für ein Array von Primitiven (int[], double[]) ist Dual-Pivot-Quicksort: nicht stabil, aber bei Zahlen spielt das keine Rolle. Für Objekte (Arrays.sort(Object[]), List.sort, Collections.sort) ist es TimSort: stabil.
C#. Array.Sort und List<T>.Sort sind Introsort: ein Quicksort, der auf Heapsort umschaltet, wenn die Partitionierung zu tief wird, und auf Insertionsort bei kleinen Teilen. Nicht stabil. LINQ OrderBy und ThenBy sind stabil.
Python. list.sort und sorted sind TimSort: stabil.
JavaScript. Array.prototype.sort muss seit ES2019 stabil sein. V8 (Chrome, Node.js) nutzt TimSort ab Version 7.0.

TimSort ist ein Mergesort, der in der Eingabe nach schon sortierten Stücken sucht und sie zusammenfügt. Echte Daten sind oft fast sortiert, und dann liegt er nahe bei O(n).

Genauer, für Neugierige

Python: Ab Version 3.11 ist die Regel, nach der TimSort wählt, welche Stücke er zusammenfügt, Powersort (von Munro und Wild). Die Sortierung ist weiterhin stabil, die Merges sind besser geordnet.
Java: Bei Primitiven spielt Stabilität wirklich keine Rolle, weil sich zwei gleiche int nicht unterscheiden lassen. Deshalb wurde dort der schnellere Quicksort gewählt.
C#: Introsort behält im schlechtesten Fall O(n log n) dank Heapsort (Heapsort). Der Preis ist die Stabilität.
JavaScript: Vor ES2019 nutzte V8 für lange Arrays Quicksort, und die Sortierung war nicht stabil. Code von damals hat manchmal „Korrekturen“ dafür, die heute nicht nötig sind.
In allen vier: Der Vergleich muss konsistent sein. Sagt er, dass A vor B liegt und B vor A, ist das Ergebnis unvorhersehbar, und in Java kann List.sort IllegalArgumentException: Comparison method violates its general contract! werfen.

Sieh es dir an

Nach mehreren Schlüsseln sortieren

Oft ist der Schlüssel mehr als ein Feld: nach Kunde, und innerhalb jedes Kunden der größte Betrag zuerst.

OrderBy gibt den ersten Schlüssel, ThenBy und ThenByDescending die nächsten. Das Ergebnis ist eine Abfrage: Das Sortieren geschieht, wenn du sie durchläufst.

var sorted = orders
    .OrderBy(o => o.Customer, StringComparer.Ordinal)
    .ThenByDescending(o => o.Amount);

Jonas 2026-10-07 120.00 €
Jonas 2026-10-03 42.50 €
Jonas 2026-10-15 9.99 €
Maria 2026-10-12 35.20 €
Maria 2026-10-05 18.00 €
Peter 2026-10-09 64.90 €

Es gibt einen zweiten Weg, der nur mit einer stabilen Sortierung funktioniert: Sortiere zuerst nach dem zweiten Schlüssel, dann nach dem ersten. Die zweite Sortierung bewahrt die Reihenfolge gleicher Schlüssel, und diese Reihenfolge ist schon nach dem zweiten Schlüssel. Die letzte Sortierung ist die Hauptsortierung.

Genauer, für Neugierige

Wann der zweite Weg nützlich ist: wenn die Schlüssel nicht in einen Vergleich passen. In Python zum Beispiel funktioniert -o.amount nicht für Text: Für „nach Kunde, und innerhalb jedes Kunden nach Produktname in umgekehrter Reihenfolge“ sortierst du zweimal, zuerst key=lambda o: o.product, reverse=True, dann key=lambda o: o.customer.

Probier es aus

Sage die Ausgabe voraus

Zwei stabile Sortierungen nacheinander: zuerst nach Betrag, der größte zuerst, dann nach Kunde. Was gibt das Programm aus?

Order[] orders =
[
    new("2026-10-05", "Maria", 35.20m),
    new("2026-10-06", "Jonas", 9.99m),
    new("2026-10-07", "Maria", 18.00m),
    new("2026-10-08", "Jonas", 42.50m),
];
orders = orders.OrderByDescending(o => o.Amount).ToArray();
orders = orders.OrderBy(o => o.Customer, StringComparer.Ordinal).ToArray();
foreach (Order o in orders)
{
    Console.WriteLine($"{o.Customer} {o.Amount}");
}

Antwort

Jonas 42.50 / Maria 35.20 / Maria 18.00 / Jonas 9.99

Jonas 42.50 / Jonas 9.99 / Maria 35.20 / Maria 18.00

Jonas 9.99 / Jonas 42.50 / Maria 18.00 / Maria 35.20

Übung

Lieferungen nach Stadt

Löse die Aufgabe in deinem Editor.

Nach Stadt, dann nach Betrag. Sechs Lieferungen haben eine Stadt und einen Betrag. Sortiere sie nach Stadt, und innerhalb einer Stadt der größte Betrag zuerst, mit der eingebauten Sortierung deiner Sprache.

Plovdiv 24.00 €
Plovdiv 15.30 €
Sofia 80.00 €
Sofia 12.50 €
Varna 40.00 €
Varna 9.90 €

Weitere Aufgaben

Zweimal. Mach dasselbe mit zwei stabilen Sortierungen, ohne zwei Schlüssel in einen Vergleich zu packen. Welche Sortierung kommt zuerst?
Instabil von Hand. Sortiere die Lieferungen nach Stadt mit Heapsort aus der Lektion zu Heaps. Bleiben die Beträge innerhalb einer Stadt in der Reihenfolge, in der sie waren?
Ein stabiler Selectionsort. Kann Selectionsort stabil werden, wenn er statt zu tauschen das kleinste an seinen Platz bringt und den Rest nach rechts schiebt? Was kostet das?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·

Stabiles Sortieren und die eingebaute Sortierung

Cookies