Stabilität

Ein Sortierer ist stabil, wenn gleiche Schlüssel ihre relative Reihenfolge behalten. Insertion Sort ist stabil; Selection Sort typischerweise nicht (je nach Implementierung).

Stabilität zählt, wenn an Schlüsseln Zusatzdaten hängen.

Wo gebraucht

Mehrstufiges Sortieren (erst Name, dann Note) und UI-Tabellen: stabile Sortierung erhält die vorherige Ordnung. Collections.sort / TimSort sind stabil; klassisches Quicksort typischerweise nicht.

Vertiefung

Eine Sortierung ist stabil, wenn Datensätze mit identischem Sortierschlüssel nachher in derselben gegenseitigen Abfolge erscheinen wie vorher. Das ist relevant, wenn mehrere Sortierschritte kombiniert werden, etwa zuerst nach Vorname und danach nach Nachname.

Stabilität ist eine Eigenschaft der konkreten Implementierung, nicht nur des Algorithmusnamens. Insertion Sort kann durch Verschieben nur strikt grösserer Elemente stabil arbeiten. Selection Sort mit einem weiten Tausch kann dagegen einen gleichwertigen Datensatz über einen anderen hinwegbewegen.

Schwierigkeitsstufen

1. Stabilität an Datensätzen mit Schlüssel und Zusatzkennung prüfen.
2. Eine Vergleichsbedingung stabil oder instabil machen.
3. Mehrstufige Sortierungen in der richtigen Reihenfolge planen.

Fallstricke

An Arrays mit lauter verschiedenen Werten lässt sich Stabilität nicht beobachten. Eine Prüfung braucht gleiche Schlüssel mit unterscheidbaren Begleitdaten, sonst bleibt ein Ordnungsverlust unsichtbar.