Java-Programmieraufgaben - SortierenSchwierigkeit 2 (vorausgesetzt das Verschmelzen ist schon implementiert)
Implementieren Sie Mergesort ohne Rekursion.
Das Verschmelzen zweier sortierter Teilfolgen ist dabei identisch zur rekursiven Lösung. Statt rekursiv zu unterteilen, müssen Sie umgekehrt vorgehen: Es werden zuerst alle Paare benachbarter Zahlen verschmolzen. Danach sind diese Paare aufsteigend sortiert. Dann werden jeweils zwei dieser benachbarten Zahlenpaar zu einer aufsteigenden Folge von vier Zahlen verschmolzen. Dies wird solange wiederholt, bis das ganze Feld sortiert ist. Die Schrittweite verdoppelt sich immer. Aus dieser lassen sich die linke und rechte Grenze für die Verschmelzungen errechnen.
Diese Version von Mergesort wird auch Direktes Mischen genannt.
Schwierigkeit 1
Implementieren Sie Sortieren durch Natürliches Mischen in Java.
Dies ist eine Verbesserte Variante des Direkten Mischens bzw. der nicht-rekursiven Version von Mergesort. Anstatt immer Paare von Folgen der Länge 1, dann 2, dann 4 usw. zu verschmelzen, werden bei dieser Variante benachbarte und bereits aufsteigend sortierte Folgen verschmolzen.
Wir betrachten als Beispiel die Folge 7 4 6 3 1 2 8 5. In dieser Folge sind sortierte Teilfolgen enthalten. Wir markieren diese mit |: 7 | 4 6 | 3 |1 2 | 8 | 5 . Beim Natürlichen Mischen müssen diese Folgen gesucht und benachbarte Folgen verschmolzen werden bis das Feld sortiert ist.
7 | 4 6 | 3 |1 2 | 8 | 5 4 6 7 | 3 | 1 2 | 8 | 5 4 6 7 1 2 3 | 8 | 5 4 6 7 1 2 3 5 8 <-- nach erstem Durchlauf 4 6 7 | 1 2 3 | 5 8 1 2 3 4 6 7 | 5 8 <-- nach zweitem Durchlauf 1 2 3 4 5 6 7 8 <-- nach drittem Durchlauf
Welchen Zeitaufwand hat dieses Verfahren im besten und im schlimmsten Fall?
Schwierigkeit 1
Shellsort basiert auf Sortieren durch direktes Einfügen. Es wurde 1959 von D. L. Shell publiziert. Bei Shellsort wird Sortieren durch direktes Einfügen mehrfach auf ein Feld angewendet, aber mit unterschiedlicher Schrittweite: Zuerst nur auf zum Beispiel jedes 4. Element, dann auf jedes 2. und erst zum Schluss auf jedes. Eine derartigen Durchlauf nennt man k-Sortierung (hier mit k= 4, 2, 1).
Wir betrachten als Beispiel ein Feld mit 8 Zahlen. Beim ersten Durchlauf wird Sortieren durch Direktes Einfügen auf jedes 4. Element durchgeführt , also insgesamt 4 mal: Einmal mit Start beim 1. Element, dann beim 2., beim 3. und beim 4. Es werden also 4 Folgen mit je 2 Elementen sortiert. Diese 4 Folgen sind farblich hervorgehoben. Ziel ist es, Zahlen über weite Strecken auszutauschen, so dass insgesamt weniger Vertauscheoperationen stattfinden, im besten Fall - keine Vertauschungen - hat Sortieren durch direktes Einfügen O(n) Zeitaufwand. Shellsort versucht diesen besten Fall möglichst schnell herbeizuführen.
| 5 | 8 | 3 | 7 | 1 | 6 | 2 | 4 | Ursprungsfolge |
| 1 | 8 | 3 | 7 | 5 | 6 | 2 | 4 | Sortieren der "gelben" Teilfolge |
| 1 | 6 | 3 | 7 | 5 | 8 | 2 | 4 | Sortieren der "cyan" Teilfolge |
| 1 | 6 | 2 | 7 | 5 | 8 | 3 | 4 | Sortieren der "weissen" Teilfolge |
| 1 | 6 | 2 | 4 | 5 | 8 | 3 | 7 | Sortieren der "orangen" Teilfolge |
Wir haben hier bei allen Teilfolgen den schlimmsten Fall erwischt, da das kleinste Element nach vorne gewandert ist. Da im schlimmsten Fall die Vertauschoperationen überwiegen - in diesem Fall je eine - haben wir insgesamt 4 Schritte benötigt. Nun wird 2-sortiert.
| 1 | 6 | 2 | 4 | 5 | 8 | 3 | 7 | Folge nach 1. Durchlauf |
| 1 | 6 | 2 | 4 | 3 | 8 | 5 | 7 | Es "rutscht" lediglich die 3 durch, die restlichen Durchläufe brechen sofort ab. |
| 1 | 4 | 2 | 6 | 3 | 7 | 5 | 8 | Es gibt nur zwei Vertauschungen |
Wir haben hier nicht mehr den schlimmsten Fall. Die Durchläufe haben je 4 Vergleiche oder Vertauschungen benötigt. Nun der letzte Durchlauf (normales Sortieren durch direktes Einfügen). Wir führen jeden Schleifendurchlauf vor und zählen dabei die gemachten Vergleiche. Der bereits sortierte Teil ist weiss.
| 1 | 4 | 2 | 6 | 3 | 7 | 5 | 8 | Start |
| 1 | 4 | 2 | 6 | 3 | 7 | 5 | 8 | Ein Vergleich |
| 1 | 2 | 4 | 6 | 3 | 7 | 5 | 8 | Ein Vergleich und einmal Tauschen (Ein Schritt) |
| 1 | 2 | 4 | 6 | 3 | 7 | 5 | 8 | Ein Vergleich |
| 1 | 2 | 3 | 4 | 6 | 7 | 5 | 8 | Zwei Schritte |
| 1 | 2 | 3 | 4 | 6 | 7 | 5 | 8 | Ein Schritt |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | Zwei Schritte |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | Ein Schritt |
Wie wir am letzten Durchlauf sehen, haben wir nicht mehr den schlechtesten Fall, sondern einen sehr guten: höchsten zwei Schritte wurden im jeden Durchlauf benötigt. Im schlimmsten Fall hätten es auch bis zu 7 sein können. Insgesamt 9 Schritte.
Trotz der mehrfachen Durchläufe, kann man von Shellsort zeigen, dass es besser ist als einmal und sofortiges Sortieren durch direktes Einfügen mit Schrittweite 1. Der Zeitaufwand der Java-Implementierung hängt von der Wahl der Schrittweite in Abhängigkeit von n ab.
Wie Sie vielleicht schon geahnt haben: Implementieren Sie Shellsort in Java. Und zwar für die Schrittweite 1, 3, 7, 15, 31, 63, ..., 2k - 1 mit k = log2(n) (in umgekehrter Reihenfolge). Für diese Folge hat Shellsort einen Zeitaufwand von O(n1,5) im schlimmsten Fall. Sie können den Algorithmus auch von der konkreten Implementierung der Folge unabhängig machen, in dem Sie die Berechnung der Folge in ein seperates Objekt verbergen (dann am besten als Java-Interface).