Stabiles Sortierverfahren

Stabiles Sortierverfahren

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

Wenn beispielsweise 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, ein Array sortieren, dabei aber die Reihenfolge der Datensätze mit gleichem Schlüssel untereinander unverändert lassen, so kann man sich damit behelfen, dass man in einem zusätzlichen Array die ursprüngliche Positionen aller Elemente speichert und im Fall, dass Elemente mit gleichen Schlüsseln vorliegen, darauf zurückgreift. Normalerweise benutzt man aber stattdessen meist ein stabiles Sortierverfahren, z. B. Bucketsort, Insertionsort oder Mergesort.

Stabile und instabile Sortierverfahren sortieren eine Datenmenge gleich, wenn der Sortierschlüssel einen Vergleich über den gesamten Datensatz vornimmt und verschiedene Datensätze auch ungleich bewertet. Eine Menge 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 für stabile Sortierverfahren:

Bubblesort, Countingsort, Cocktailsort, Gnomesort, Insertionsort, Mergesort, Slowsort, Radixsort


Beispiele für instabile Sortierverfahren:

Binary Tree Sort, Heapsort, Introsort, Quicksort, Shellsort, Smoothsort, Stoogesort


Siehe auch: in-place


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Stabil (Sortierverfahren) — Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der die Reihenfolge der Datensätze, deren Sortierschlüssel gleich sind, bewahrt. Wenn beispielsweise eine Liste alphabetisch sortierter Personendateien nach dem Geburtsdatum neu sortiert… …   Deutsch Wikipedia

  • Stabilität (Sortierverfahren) — Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der die Reihenfolge der Datensätze, deren Sortierschlüssel gleich sind, bewahrt. Wenn beispielsweise eine Liste alphabetisch sortierter Personendateien nach dem Geburtsdatum neu sortiert… …   Deutsch Wikipedia

  • Sortieralgorithmen — Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist, z. B. die lexikographische Ordnung von Zeichenketten… …   Deutsch Wikipedia

  • Sortieralgorithmus — Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist, z. B. die lexikographische Ordnung von Zeichenketten… …   Deutsch Wikipedia

  • Stabil — Ein stabiles System kehrt nach Störungen von selbst in seinen Ruhezustand zurück Stabile (1,3) und instabile (2) Zustände Stabilität (von lat. stabilis = standhaft, stabil) ist die Fähigkeit eines …   Deutsch Wikipedia

  • Systemstabilität — Ein stabiles System kehrt nach Störungen von selbst in seinen Ruhezustand zurück Stabile (1,3) und instabile (2) Zustände Stabilität (von lat. stabilis = standhaft, stabil) ist die Fähigkeit eines …   Deutsch Wikipedia

  • Merge-Sort — Mergesort ist ein rekursiver, stabiler Sortieralgorithmus, der ähnlich wie Quicksort nach dem Prinzip Teile und herrsche (lat. Divide et impera, engl. Divide and Conquer) arbeitet. Er wurde erstmals 1945 durch John von Neumann vorgestellt. Der… …   Deutsch Wikipedia

  • MergeSort — ist ein rekursiver, stabiler Sortieralgorithmus, der ähnlich wie Quicksort nach dem Prinzip Teile und herrsche (lat. Divide et impera, engl. Divide and Conquer) arbeitet. Er wurde erstmals 1945 durch John von Neumann vorgestellt. Der zusätzliche… …   Deutsch Wikipedia

  • Merge Sort — Mergesort ist ein rekursiver, stabiler Sortieralgorithmus, der ähnlich wie Quicksort nach dem Prinzip Teile und herrsche (lat. Divide et impera, engl. Divide and Conquer) arbeitet. Er wurde erstmals 1945 durch John von Neumann vorgestellt. Der… …   Deutsch Wikipedia

  • Natural Mergesort — Mergesort ist ein rekursiver, stabiler Sortieralgorithmus, der ähnlich wie Quicksort nach dem Prinzip Teile und herrsche (lat. Divide et impera, engl. Divide and Conquer) arbeitet. Er wurde erstmals 1945 durch John von Neumann vorgestellt. Der… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”