001 package de.hska.java.aufgaben.sortieren;
002
003
004 /**
005 * <p>Natürliches Mischen ist eine Verbesserung der nicht-rekursiven Variante von
006 * {@link Mergesort} bzw. Direktem Mischens.
007 * Bim natürlichen Mischen wird nicht mit stetig grösser werdener Schrittweite
008 * von 2, 4, 8, ..., 2<sup>log<sub>2</sub>(n)</sup> sondern mit variabler Schrittweite:
009 * Es werden immer die nächsten beiden aufsteigend sortierten Folgen verschmolzen.
010 * </p>
011 * <p>In der Folge <code>7 4 6 3 1 2 8 5</p> werden anfangs die ersten beiden enthaltenen
012 * aufsteigend sortierten Folgen 7 und 4 6 verschmolzen, dann 3 mit 1 2 und zuletzt 8 und 5.
013 * Dies wird solange wiederholt, bis das Feld aufsteigend sortiert ist.
014 * Wir demonstrieren das obiger Folge, die aufsteigend sortierten Bereiche sind mit | voneinander
015 * separiert.
016 * <p>
017 * <pre>
018 * 7 | 4 6 | 3 |1 2 | 8 | 5
019 * 4 6 7 | 3 | 1 2 | 8 | 5
020 * 4 6 7 1 2 3 | 8 | 5
021 * 4 6 7 1 2 3 5 8
022 *
023 * 4 6 7 | 1 2 3 | 5 8
024 * 1 2 3 4 6 7 | 5 8
025 *
026 * 1 2 3 4 5 6 7 8
027 * </pre>
028 * <p>
029 * Im besten Fall hat mein ein bereits aufsteigend sortiertes Feld, der
030 * Zeitaufwand beträgt O(n). Im schlimmsten Fall können wir natürlich nicht
031 * besser werden als O(n log<sub>2</sub>n ).
032 * Durch die erhöhte Anzahl von Vergleichen ist dieser Algorithmus aber in der Praxis
033 * vermutlich langsamer als Direktes Mischen.
034 * </p>
035 *
036 * <p>
037 * <a href="http://www.home.hs-karlsruhe.de/~pach0003/informatik_1/aufgaben/sortieren.html#natuerlichesMischen">Zurück zum Aufgabentext</a>
038 * </p>
039 *
040 *
041 * @author Christian Pape
042 *
043 */
044 public class NatuerlichesMischen implements Sortieren {
045
046 private int [] b;
047
048 /**
049 * Sortiert die Zahl in a aufsteigend mit Natürlichem Mischen.
050 */
051 public void sortieren(int[] a) {
052 b = new int[a.length];
053 natuerlichMischen(a);
054 }
055
056
057
058 private void natuerlichMischen(int [] a) {
059 int links = 0;
060 int rechts = a.length - 1;
061 boolean sortiert = false;
062 int l = 0;
063 int r = rechts;
064
065 do {
066 sortiert = true;
067 links = 0;
068 // Komplettes Feld einmal mischen
069 while (links < rechts) {
070 l = links;
071 while (l < rechts && a[l] <= a[l + 1]) {
072 l++;
073 }
074 r = l + 1;
075 while (r == rechts - 1 || r < rechts && a[r] <= a[r + 1]) {
076 r++;
077 }
078 if (r <= rechts) {
079 verschmelzen(a, links, l, r);
080 sortiert = false;
081 }
082 links = r + 1;
083 }
084 } while (! sortiert);
085
086 }
087
088 /**
089 * Verschmelzen der aufsteigend sortierten Breiche
090 * a[links]...a[mitte] mit a[mitte+1]..a[rechts]
091 * zu einer aufsteigend sortierten Folge
092 * a[links] .. a[rechts].
093 */
094 private void verschmelzen(int[] a, int links, int mitte, int rechts) {
095 int l = links;
096 int r = mitte + 1;
097
098 for (int i = links; i <= rechts; i++) {
099 if (r > rechts || (l <= mitte && a[l] <= a[r])) {
100 b[i] = a[l++];
101 } else if (l > mitte || (r <= rechts && a[r] <= a[l])) {
102 b[i] = a[r++];
103 }
104 }
105
106 for (int i = links; i <= rechts; i++) {
107 a[i] = b[i];
108 }
109 }
110
111 }