Es sei eine Folge von Datensätzen gegeben, die gemäß einem Schlüssel sortiert werden sollen.
Mehrere Datensätze weisen denselben Schlüssel auf, sind jedoch ansonsten verschieden (z.B. Liste nach Namen sortiert, jedoch haben die Personen trotz gleichen Nachnamens verschiedene Vornamen). Sie sollen einen Algorithmus angeben, nach dem die Daten sortiert werden sollen, jedoch die (zufällige) Reihenfolge der Datensätze mit gleichem Schlüssel erhalten bleiben soll.
Wenn zum Beispiel der Datensatz „Maier, Hans“ der unsortierten Datei ist und der Datensatz „Maier, Alfred“, dann soll auch nach dem Sortieren der Datei „Maier, Hans“ noch vor „Maier, Alfred“ einsortiert bleiben.
Prüfen Sie, ob die Ihnen bekannten Sortieralgorithmen diese Anforderung erfüllen (so genannte „Stabilität“).

Lösungsvorschlag

Bekannte Sortieralgorithmen:

• Selectionsort
• Quicksort
• Bubblesort
• Mergesort

Selection Sort:

Idee: Starte beim ersten Element. Suche ein Element, das kleiner ist als das Startelement und tausche die beiden. Verfahre mit den restlichen ebenso.

Beispiel:

Dieses Verfahren ist allerdings nicht stabil.

Bsp:

Damit sind 13a und 13b in ihrer Reihenfolge vertauscht worden!

Quicksort:

Idee: „Teile und herrsche!“. Partitionieren in zwei Teilmengen mit je n/2 Einträgen anhand eines Pivot-Elements. Diese rekursiv wieder Partitionieren.
Dieses Verfahren ist allerdings auch nicht stabil.

Bsp:

Bubblesort:

Idee: Benachbarte Elemente werden getauscht, wenn z.B. das rechte kleiner ist, als das linke.

Dieses Verfahren ist stabil, da immer nur benachbarte Elemente getauscht werden. Es ist also nicht möglich, dass 13a und 13b vertauscht werden.

Mergesort:

Idee: Ebenfalls „Teile und herrsche!“, allerdings wird je in Listen aufgeteilt, die dann für sich sortiert werden und dann in einem Reißverschlussverfahren wieder zusammengefügt werden.
Damit ist Mergesort ebenfalls stabil, sofern der Merge-Schritt geeignet implementiert wird.