Stabilität (Sortierverfahren)

Definition und Bedeutung

Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der bei Datensätzen mit gleichem Sortierschlüssel deren ursprüngliche Reihenfolge bewahrt. Der Sortierschlüssel ist das Feld oder Merkmal, nach dem sortiert wird.

Beispiel: Wird eine bereits alphabetisch geordnete Liste von Personen nach dem Geburtsdatum sortiert, bleiben bei einer stabilen Sortierung alle Personen mit demselben Geburtsdatum untereinander alphabetisch geordnet. Stabilität ist deshalb besonders wichtig, wenn Datensätze aus mehreren Feldern bestehen und nacheinander nach verschiedenen Merkmalen sortiert werden.

Bei einem instabilen Verfahren wie Quicksort kann die Reihenfolge von Datensätzen mit gleichem Schlüssel verändert werden. Soll sie trotzdem erhalten bleiben, kann jeder Datensatz eine Reihenfolgenummer erhalten. Diese wird als niedrigstrangigster Bestandteil in den Sortierschlüssel aufgenommen. In der Regel ist es weniger aufwändig, direkt ein stabiles Sortierverfahren zu verwenden.

Wann Stabilität keinen Unterschied macht

Stabile und instabile Verfahren liefern dasselbe sichtbare Ergebnis, wenn es unter den Sortierschlüsseln keine Duplikate gibt. Das gilt beispielsweise für die alphabetische Sortierung der drei verschiedenen Namen Carla, Annette und Birgit.

Auch wenn Datensätze mit gleichem Schlüssel nicht voneinander unterscheidbar sind, spielt Stabilität für das Ergebnis keine Rolle. Dies ist etwa der Fall, wenn der Schlüssel den gesamten Datensatz umfasst. Eine reine Zahlenliste wie 4, 3, 5, 3, 2, 1, 3 wird unabhängig von der Stabilität zu 1, 2, 3, 3, 3, 4, 5 sortiert, weil die einzelnen Vorkommen der Zahl 3 nicht unterscheidbar sind.

Gleiche Schlüssel bei unterscheidbaren Datensätzen

Ein Unterschied entsteht, wenn ein Datensatz mehrere Angaben enthält, aber nur nach einem Teilschlüssel sortiert wird. In der Beispielmenge stehen Zahlen zusammen mit Namen: 1 Anton, 4 Karl, 3 Otto, 5 Bernd, 3 Helmut, 8 Alfred und 1 Paul.

Bei stabiler Sortierung nach den Zahlen lautet das Ergebnis: 1 Anton, 1 Paul, 3 Otto, 3 Helmut, 4 Karl, 5 Bernd, 8 Alfred. Innerhalb der Gruppen mit den Schlüsseln 1 und 3 bleibt also die ursprüngliche Namensreihenfolge erhalten.

Bei instabiler Sortierung darf dagegen Paul vor Anton und Helmut vor Otto stehen. Da es für jede der beiden Gruppen zwei mögliche Reihenfolgen gibt, entstehen 2 × 2 = 4 mögliche Gesamtordnungen. Zu diesen Möglichkeiten gehört auch zufällig genau jene Ordnung, die ein stabiles Verfahren garantiert.

Mehrstufiges Sortieren von Tabellen

In der Informatik bestehen Tabellen aus Sequenzen von Datensätzen, die in Felder eingeteilt sind. Jeder Datensatz beschreibt eine Entität, jedes Feld ein Merkmal dieser Entität. Datenbanken, Tabellenkalkulationsprogramme und andere Anwendungen können einzelne Spalten als Sortierschlüssel auswählen.

Ein kombinierter Sortierschlüssel aus zwei Spalten, beispielsweise Dateityp und Dateigröße, kann durch zwei aufeinanderfolgende Sortierungen ersetzt werden. Zuerst wird nach dem niedrigrangigen Schlüssel Dateigröße und danach nach dem höherrangigen Schlüssel Dateityp sortiert. Der zweite Sortierlauf muss stabil sein, damit die innerhalb eines Dateityps bereits hergestellte Reihenfolge nach Dateigröße erhalten bleibt.

Allgemein muss bei mehreren Einzelsortierungen zuerst nach dem Schlüssel mit dem niedrigsten Rang sortiert werden. In einem Dateimanager kann ein Klick auf einen Spaltennamen eine aufsteigende Sortierung (▴) und ein zweiter Klick eine absteigende Sortierung (▾) auslösen. Enthält die Beispieltabelle die Dateien a, u und c vom Typ doc sowie k und r vom Typ txt, ergibt ein stabiler Sortierlauf nach Dateityp in der Spalte Dateiname die Reihenfolge a, u, c, k, r.

Anzahl möglicher Sortierordnungen

Bei vier Spalten kann eine stabile Sortierung nach einer passend gewählten Folge von höchstens vier einzelnen Feldern jede Kombination und Rangfolge der verwendeten Felder darstellen. Ohne Berücksichtigung der Sortierrichtung gibt es maximal

C(4,4) · 4! + C(4,3) · 3! + C(4,2) · 2! + C(4,1) · 1! = 24 + 24 + 12 + 4 = 64

Möglichkeiten. Dabei bezeichnet C(4,k) beziehungsweise der Binomialkoeffizient „4 über k“ die Auswahl von k Feldern aus vier; k! zählt ihre möglichen Rangfolgen.

Wird für jedes Feld zusätzlich zwischen aufsteigender und absteigender Sortierung unterschieden, lautet die Rechnung

C(4,4) · 2⁴ · 4! + C(4,3) · 2³ · 3! + C(4,2) · 2² · 2! + C(4,1) · 2¹ · 1! = 384 + 192 + 48 + 8 = 632.

Damit sind 632 Kombinationen aus Feldauswahl, Rangfolge und Sortierrichtung möglich.

Beispiele für Sortierverfahren

Als stabile Sortierverfahren nennt der Artikel Binary Tree Sort, Bubblesort, Countingsort, Cocktailsort, Gnomesort, Insertionsort, Mergesort, Radixsort und Shakersort.

Als instabile Sortierverfahren werden Bogosort, Combsort, Heapsort, Introsort, Quicksort, Selectionsort, Shellsort, Smoothsort, Slowsort und Stoogesort aufgeführt.