Stabilität (Sortierverfahren)

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Stabiles Sortierverfahren)
Wechseln zu: Navigation, Suche

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:

Stabiles oder instabiles Sortierverfahren:

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

Stabiles oder instabiles Sortierverfahren (alphabetisch):

  Carla        Annette
  Annette  →   Birgit
  Birgit       Carla

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 wählt diejenige Reihenfolge, die bei gleichen Schlüsseln die Originalreihenfolge der Namen beibehält, etwa

Stabiles Sortierverfahren nach Zahlen:

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

Instabiles Sortierverfahren nach Zahlen:

  1 Anton        1 Paul         1 Anton        1 Paul            1 Anton
  4 Karl         1 Anton        1 Paul         1 Anton           1 Paul
  3 Otto         3 Otto         3 Herbert      3 Herbert         3 Otto
  5 Bernd   →    3 Herbert oder 3 Otto    oder 3 Otto       oder 3 Herbert
  3 Herbert      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 instabiler Sortierung kann Paul vor Anton oder Herbert vor Otto stehen.

Anwendung in der Datenverarbeitung[Bearbeiten | Quelltext bearbeiten]

In der Informatik kommen sehr häufig Sequenzen (Ansammlungen, Dateien) von in Felder eingeteilten Datensätzen vor, bei denen jeder Datensatz für ein Individuum irgendwelcher Kategorie und ein Feld für ein Merkmal dieses Individuums steht.

Viele Anwendungsprogramme, z. B. von Datenbanken, und Tabellenkalkulationsprogramme unterstützen die Auswahl eines jeden Merkmals als Sortierbegriff (Schlüssel). Als Beispiel sei ein Beispiel zu einem Dateimanager wie dem Windows-Explorer gebracht:

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

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

        ( = 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

Kombinationen zusammen.

Bei den Einzelsortierungen ist nach den niedrigrangigen Schlüsseln (Feldern) zuerst zu sortieren. Eine solche Sortierung kann im Windows-Explorer durch den Klick auf den Merkmal-Namen in der Titelzeile veranlasst werden, und zwar bedeutet ▴ aufsteigend sortiert und ▾ absteigend.

Beispiele[Bearbeiten | Quelltext bearbeiten]

Stabile Sortierverfahren:

Instabile Sortierverfahren:

Siehe auch[Bearbeiten | Quelltext bearbeiten]