Stabiles Sortieren

Ein weiteres, ganz wichtiges Merkmal des Sortierens ist die sog. Stabilität bzw. Instabilität, die sich zudem, im Gegensatz zu anderen Merkmalen, auch auf das Sortierergebnis auswirkt. Damit ist nicht gemeint, daß ein instabiler Algorithmus wegen einer Inkonsistenz, wegen eines Programmier- oder Logikfehlers fehlerhafte Sortierergebnisse zeigt oder dieser Algorithmus oder gar mit ihm das Programm abbricht und im gegensätzlichen Falle ihm dieses Schicksal erspart bleibt. Eine bekannte Internetenzyklopädie schreibt dazu:

„Stabile Sortierverfahren sind solche, die die relative Reihenfolge von Elementen, die bezüglich der Ordnung äquivalent sind, nicht verändern, während instabile Sortierverfahren dies nicht garantieren.“

und an anderer Stelle:

„Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der die Reihenfolge der Datensätze, deren Sortierschlüssel gleich sind, bewahrt.

Wenn bspw. eine Liste alphabetisch sortierter Personendateien nach dem Geburtsdatum neu sortiert wird, dann bleiben unter einem stabilen Sortierverfahren alle Personen mit gleichem Geburtsdatum alphabetisch sortiert.“

Etwas ausführlicher: Eine Menge Personendatensätze wird nach dem Geburtstag bzw. -datum oder nach dem Vornamen sortiert. Danach wird diese Menge anhand des Nachnamens sortiert, die ursprüngliche Geburtstags- oder Vornamensreihenfolge wird damit aber wieder zerstört. So kommen alle „Meiers“ vor den „Müllers“, und beide bilden einen jeweils zusammenhängenden Bereich oder Block. Doch „innerhalb“ des Bereiches, in dem „Meier“ oder „Müller“ steht, sind alle diese „Meiers“ und „Müllers“, der vorherigen Sortierung sei dank, garantiert nach dem jeweiligen Geburtstag bzw. Vornamen sortiert, wenn das zweite Sortierverfahren ein stabiles ist, ansonsten ist das eher unwahrscheinlich (wenn auch bei wenigen „Meiers“ oder „Müllers“ nicht ausgeschlossen). Beobachten kann man dieses Phänomen auch in Windows in den Explorerfenstern mit Detailansicht, wenn man Windows die Einträge (Dateien mit ihren Daten) anhand verschiedener Merkmale sortieren läßt. Nach meiner Wahrnehmung verwendet Windows ein stabiles Sortierverfahren. Weitere Beispiele, die stabiles Sortieren benötigen, wären Tabellenprogramme wie Excel oder Datenbankprogramme wie Access. Bei instabilen Sortierverfahren sind hingegen beliebige Permutationen innerhalb der Teilmengen mit jeweils gleichem Sortierschhlüssel möglich.

Ein Beispiel: Aus der unsortierten Menge 2_A 1_A 2_B 3_A 1_B 3_B 2_C wird nach instabiler Sortierung z.B. 1_A 1_B 2_B 2_C 2_A 3_A 3_B (die Reihenfolge der Zweien ist gegenüber der Ausgangsreihenfolge verändert, deren Anordnung also permutiert, das kann mit jeder Teilmenge mit jeweils gleichen Elemente(schlüssel)n geschehen), bei stabiler Sortierung hingegen nur 1_A 1_B 2_A 2_B 2_C 3_A 3_B.

Das bedeutet demnach, daß ein Sortieralgorithmus strenggenommen schon dann instabil ist, wenn er das Vertauschen gleich(groß)er Elemente (bzw. solcher mit gleich(groß)en Schlüsseln) nicht sicher ausschließen kann - unabhängig davon, ob das tatsächlich geschieht (i.d.R. jedoch mit sehr großer Wahrscheinlichkeit, außer bei sehr kleinen Elementeanzahlen). In Ausnahmefällen, also bei (sehr) kleinen Elementeanzahlen, kann auch ein instabiler Sortieralgorithmus - scheinbar - praktisch - stabil sein. In der Sortieralgorithmenliste des „Sortierkinos“ steht in jedem Eintrag auch, ob der Algorithmus (in-)stabil ist. Damit ist erstgenannte, strenggenommene Eigenschaft des Algorithmus' gemeint. Zusätzlich kann man sich die (In-)Stabilität zum Ende eines (jeden) Sortiervorganges anzeigen lassen, das ist dann die tatsächliche, „gemessene“ (In-)Stabilität in bezug auf dieses konkrete Sortierergebnis.

Dieses Stabiltitätsmerkmal kann sich über mehrere Sortierungen durchziehen, so daß z.B. alle „Peter Müllers“ einen zusammenhängenden Block bilden und innerhalb dessen die Sortierung nach den Geburtstagen erhalten geblieben ist.

Instabile Sortieralgorithmen sind mithin nur für Erstsortierungen unsortierter „Rohdatenmengen“ oder von Mengen mit Elementen, die nur einen Sortierschlüssel haben (bzw. mit diesem identisch sind), uneingeschränkt geeignet. Mit anderen Worten: Stabile Sortierverfahren sind angebracht für:

• Zweit-/Folgesortierungen von

• Mengen mit komplexen, mehrschlüsseligen Elementen bei

• Wechsel des Sortierschlüssels.

Es gibt - analog zu den parallelisierbaren Sortieralgorithmen, die parallele und nichtparallele Varianten haben - durchaus Sortieralgorithmen, die eine stabile und eine instabile Variante / Version besitzen, z. B. Trippelsort und diverse Mergingalgorithmen. Da die Stabilität das höhere Sortierniveau darstellt und - außer für Erstsortierungen - das bevorzugte Sortiermerkmal darstellt, denn bereits erledigte (Sortier-)Arbeit möchte man nur selten zerstört sehen, wurden die Algorithmen in solchen Fällen möglichst „stabilisiert“. Davon abgesehen, kann die Stabilität auch schnell zerstört werden: Statt eines „<“ ein „<=“ (oder umgekehrt) bzw. statt eines „>“ ein „>=“ (oder andersherum), und schon ist es um die Stabilität geschehen (unwahrscheinlicher sogar um das Sortierergebnis schlechthin). Umgekehrt läßt sich die Stabilität mit dem Wechsel solcher Vergleichsoperationen in manchen Fällen erreichen. Außerdem kann die Stabilität den Sortieralgorithmus etwas oder erheblich verlangsamen.

Als Faustregel läßt sich sagen, daß Sortieralgorithmen ohne Vertauschungen (z. B. die (Natural-)Mergesort(s) mit einfachem Verschmelzen) wie auch solche mit Vertauschungen nur benachbarter Elemente (z. B. Bozosort 3, Bubble-, Insertion-, Oet- und Shakersort) die Stabilität gewährleisten, Elementebewegungen (Vertauschungen, Verschiebungen) über größere „Entfernungen“ in der noch unsortierten Teilmenge jedoch nicht, letztere also demnach instabil sind. Bei Bewegungen innerhalb der schon sortierten Elementemenge hängt es vom Algorithmus ab. Im Gegenzuge können Bewegungen über größere „Entfernungen“ jedoch das Sortieren beschleunigen, s. die im Programm enthaltene instabile Bubble- und Trippelsortvariante.

Die allermeisten stabilen Sortieralgorithmen funktionieren mit bloßem Zugriff auf die Elemente(schlüssel), sie sind also uneingeschränkt stabil. Es gibt in diesem Programm jedoch auch Sortieralgorithmenm, bei denen die Stabilität nur durch zusätzliches Lesen und Auswerten der Startposition der Sortierelemente bei den Vergleichsoperationen „<=“ und „>=“ erreicht werden konnte. Diese Algorithmen sind demnach nur „bedingt stabil“ (oder „semistabil“)und werden so auch tituliert. Werden damit nur einfache Daten, so z.B. Zahlen sortiert, sind diese Algorithmen instabil, allerdings sind gleiche Elemente dann auch nicht zu unterscheiden (gleichen einander wie ein Ei dem anderen), sodaß das nicht in's Gewicht fällt.

Die Stabilität ist keine triviale Eigenschaft: Einen Sortier-, Partitionierungs- oder Verschmelzungsalgorithmus stabil zu halten oder zu „stabilisieren“ ist mindestens genauso anspruchsvoll, wie ihn zu   beschleunigen , zumindest dann, wenn die Laufzeit bestenfalls nur unwesentlich darunter leiden soll..  Eine besondere Herausforderung ist die Stabilität beim In-Situ-Sortieren.