Stabilität (Sortierverfahren) - LinkFang.de





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:

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.

Beispiele

Stabile Sortierverfahren:

Instabile Sortierverfahren:

Siehe auch


Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Stabilität (Sortierverfahren) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.