Stabilität (Sortierverfahren)

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.

Will man mit einem instabilen Sortierverfahren, etwa Quicksort, sortieren und dabei die Reihenfolge der Datensätze mit gleichem Schlüssel beibehalten, so kann man sich damit behelfen, dass man die Datensätze um eine Reihenfolgenummer erweitert und diesem Feld den niedrigsten Rang im Sortierschlüssel gibt. Weniger aufwändig ist es aber, ein stabiles Sortierverfahren zu benutzen.

Stabile und instabile Sortierverfahren verhalten sich gleich, wenn die Multimenge der Schlüssel in der Eingabe eine Menge ist, es also keine Duplikate unter den Schlüsseln gibt; ebenso, wenn Datensätze mit gleichem Schlüssel in keiner Weise unterscheidbar sind – beispielsweise, weil der Schlüssel den ganzen Datensatz umfasst. Eine Multimenge von Zahlen oder Namen etwa kann man mit einem stabilen oder instabilen Sortierverfahren sortieren, das Ergebnis ist immer gleich:

Beispiele

Stabiles oder instabiles Sortierverfahren (keine Duplikate):

Carla	→	Annette
Annette		Birgit
Birgit		Carla

Stabiles oder instabiles Sortierverfahren (nur Schlüssel):

4	→	1
3		2
5		3
3		3
2		3
1		4
3		5

Kombiniert man jedoch etwa Namen und Zahlen zu je einem Datensatz und sortiert nur nach einem Teilschlüssel, etwa nach Zahlen, dann existieren bei gleichen Schlüsseln verschiedene Möglichkeiten für die Reihenfolge. Ein stabiles Verfahren behält bei gleichen Schlüsseln die Originalreihenfolge der Namen bei, etwa

Stabiles Sortierverfahren nach Zahlen:

1 Anton	→	1 Anton
4 Karl		1 Paul
3 Otto		3 Otto
5 Bernd		3 Helmut
3 Helmut		4 Karl
8 Alfred		5 Bernd
1 Paul		8 Alfred

Instabiles Sortierverfahren nach Zahlen:

1 Anton	→	1 Anton	oder	1 Paul	oder	1 Anton	oder	1 Paul
4 Karl		1 Paul		1 Anton		1 Paul		1 Anton
3 Otto		3 Otto		3 Otto		3 Helmut		3 Helmut
5 Bernd		3 Helmut		3 Helmut		3 Otto		3 Otto
3 Helmut		4 Karl		4 Karl		4 Karl		4 Karl
8 Alfred		5 Bernd		5 Bernd		5 Bernd		5 Bernd
1 Paul		8 Alfred		8 Alfred		8 Alfred		8 Alfred

Bei instabilem Sortieren kann Paul vor Anton oder Helmut vor Otto zu stehen kommen, also 2 × 2 = 4 Möglichkeiten; darunter ist (wie in der zweiten Spalte gezeigt) auch die Reihenfolge möglich, wie sie ein stabiles Sortieren garantiert erbringen würde.

Anwendung in der Datenverarbeitung

In der Informatik kommen sehr häufig sog. Tabellen vor, d. h. Sequenzen (Ansammlungen, Dateien) von in Felder eingeteilten Datensätzen, bei denen jeder Datensatz für ein Individuum und ein Feld für ein Merkmal dieses Individuums steht. Viele Anwendungsprogramme, z. B. von Datenbanken, und Tabellenkalkulationsprogramme unterstützen die Auswahl von einzelnen Merkmalen („Tabellenspalten“) als Sortierbegriff (Schlüssel).

Ein kombinierter Sortierschlüssel aus zwei Spalten bspw. in der Rangfolge (Dateityp, Dateigröße) führt zum selben Ergebnis wie zwei Sortierungen nach jeweils einer Spalte, und zwar zuerst nach Dateigröße und im zweiten Sortierlauf nach Dateityp. Dabei muss der zweite Sortierlauf die durch den ersten Lauf erzeugte Ordnung im oben erläuterten Sinn erhalten, m. a. W.: der zweite Lauf muss stabil sortieren.

Beispiel: Dateimanager (ähnlich dem Windows-Explorer):

Dateiname	Dateityp	Änderungsdatum	Dateigröße
a	doc	1999	20
u	doc	2018	70
k	txt	2013	25
c	doc	2013	15
r	txt	1800	20

Bei den Einzelsortierungen ist nach den niedrigrangigen Schlüsseln (Feldern) zuerst zu sortieren. Eine solche Einzelsortierung kann durch einen Klick für aufsteigend (nach dem Sortierlauf angezeigt als ▴) resp. zwei Klicks für absteigend (▾) auf den Merkmal-Namen in der Titelzeile veranlasst werden.

Bemerkung: Wenn der Browser des Benutzers stabil sortiert, dann ist nach einem Klick auf die Spalte Dateityp die Reihenfolge in der Spalte Dateiname: a,u,c,k,r.

Wie viele verschiedene Sortierungen gibt es maximal (bei 4 Spalten und stabilem Sortieren)?

Wenn der Explorer immer stabil sortiert, dann ist eine (einzige) Sortierung nach jeder der

{\binom {4}{4}}\cdot 4!+{\binom {4}{3}}\cdot 3!+{\binom {4}{2}}\cdot 2!+{\binom {4}{1}}\cdot 1!=24+24+12+4=64

(

!

= Fakultät)

Kombinationen und Reihenfolgen der 4 Felder gleichwertig zu einer passend ausgewählten Abfolge von maximal 4 Sortierungen nach einem einzelnen Feld. Wenn es noch auf die Sortierrichtungen aufsteigend/absteigend ankommt, dann kommen

{\binom {4}{4}}\cdot 2^{4}\cdot 4!+{\binom {4}{3}}\cdot 2^{3}\cdot 3!+{\binom {4}{2}}\cdot 2^{2}\cdot 2!+{\binom {4}{1}}\cdot 2^{1}\cdot 1!=384+192+48+8=632

Kombinationen zusammen.

Beispiele

Stabile Sortierverfahren:

Instabile Sortierverfahren:

Siehe auch

in-place