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.

Sortieralgorithmen

Quicksort

Der Quicksort-Algortithmus ist eines der schnellsten und zugleich einfachsten Sortierverfahren. Es arbeitet nach dem Divide-and-Conquer-Prinzip.
Es wird zunächst ein Pivotelement ausgewählt und die Liste in zwei geteilt. Die Elemente, die kleiner als das Pivotelement sind, kommen in die erste Liste und die anderen in die zweite. Mit den entstehenden Listen wird genauso fortgefahren, bis es nur noch Teillisten der Länge 1 gibt. Diese Listen werden nun der Reihe nach wieder zusammengefügt.

Mergesort

Ähnlich wie bei Quicksort beruht das Verfahren auf der Divide-and-Conquer-Strategie. Die zu sortierende Folge wird in zwei gleichgroße Hälften geteilt. Die entstehenden Listen werden weiter und weiter geteilt, bis es wieder nur noch Teillisten der Länge 1 gibt. Zusammengefügt wird, indem die ersten beiden Elemente zweier Teillisten verglichen werden, das kleinere gelöscht und in eine neue Liste eingetragen wird. Die neuen ersten beiden Elemente verglichen, das kleinere gelöscht und in die neue Liste eingetragen wird…

Bubblesort

Bubblesort ist einer der simpelsten Sortieralgorithmen.
Im ersten Durchlauf wird nach dem kleinsten Element gesucht, im zweiten Durchlauf nach dem zweitkleinsten usw.
Man geht den Array immer von hinten nach vorne durch. Zunächst vergleicht man das letzte mit dem vorletzten Element. Ist das hintere kleiner, werden die beiden Elemente vertauscht. Dann wird mit dem vorletzten und dem vorvorletzten weitergemacht. Dadurch bleiben die größeren liegen und die kleineren Elemente werden nach vorne durchgereicht.

Insertionsort

Man hat eine zu sortierende Folge a0, a1, … , an-1, wobei der erste Teil a0, a1, … , ak-1 bereits aufsteigend sortiert ist und der zweite Teil ak, ak+1, … , an-1 noch unsortiert ist. Zu Anfang besteht der sortierte Teil nur aus a0, zum Schluss aus allen Elementen a0, a1, … , an-1.
Das Element ak wird als nächstes in die bereits sortierte Liste eingefügt, indem es der Reihe nach mit ak-1, ak-2 usw. verglichen wird. Sobald ein Element aj mit aj≤ak gefunden wird, wird es hinter dieses eingefügt. Wird kein solches Element gefunden, wird ak an den Anfang der Folge gesetzt.
Damit ist der sortierte Teil um ein Element länger geworden. Im nächsten Schritt wird ak+1 in den sortierten Teil eingefügt…

Vergleich Mergesort und Quicksort

von http://www.gm.fh-koeln.de/~ehses/ap/folien/folien9.pdf

  • Mergesort ist garantiert O(n log n), Quicksort im Mittel
  • Die Anzahl der Vergleich und der Datenbewegungen ist bei Mergesort n log2(n)
  • Quicksort hat im Mittel O(1.4 n log2 n) Vergleiche
  • Quicksort hat im Mittel O(0.7 n log2 n) Datenbewegungen
  • Quicksort ist schneller, wenn die Vergleiche schneller sind als die Datenbewegungen (einfache Datentypen)
  • Mergesort ist schneller, wenn die Vergleiche die Zeit dominieren (Objekte)
  • Es gibt Varianten von Mergesort für Felder und Listen (nicht rekursiv)

Links

zu Laufzeiten s.a.: O-Notation
www.sortieralgorithmen.de – mit klasse Applet
Merkblatt zu topologisches Sortieren von Augustin

Kaynak: http://www.tilman.de/uni/ws03/alp/sortieralgorithmen.php

 

Zaman buldugumda Türkce cevirisini yapacagim!