Schlagwort: Sortieralgorithmen

In diesem Artikel lernst du den Sortieralgorithmus „Radix Sort“ kennen. Du erfährst:

• Wie funktioniert Radix Sort? (Schritt für Schritt)
• Wie implementiert man Radix Sort in Java?
• Welche Zeit- und Platzkomplexität hat Radix Sort?
• Welche Varianten gibt es von Radix Sort?
• … und was bedeutet überhaupt der Begriff „Radix“?

Fangen wir mit der letzten Frage an:

Was ist Radix Sort?

„Radix“ ist zwar das lateinische Wort für „Wurzel“ – dennoch hat Radix Sort nichts mit Wurzelziehen zu tun.

Die „Radix“ eines Zahlensystems (auch „Basis“ genannt) bezeichnet vielmehr die Anzahl der Ziffern, die zur Darstellung von Zahlen in diesem Zahlensystem benötigt werden. Die Radix im Dezimalsystem ist 10, die Radix des Binärsystems ist 2, und die Radix des Hexadezimalsystems ist 16.

Bei Radix Sort sortieren wir die Zahlen Ziffer für Ziffer – und nicht, wie bei den meisten anderen Sortierverfahren, indem wir zwei Zahlen miteinander vergleichen. Wie genau das funktioniert, liest du im folgenden Kapitel.

Radix Sort Algorithmus

Den Algorithmus für Radix Sort erkläre ich am besten Schritt für Schritt an einem Beispiel. Folgende Zahlen sollen sortiert werden:

Wir betrachten zu Beginn ausschließlich die letzte Ziffer (es gibt auch Radix-Sort-Varianten, bei denen man bei der ersten Ziffer beginnt, aber dazu kommen wir später):

Wir sortieren die Zahlen in zwei Phasen: einer Partitionierungsphase und einer Sammelphase.

Partitionierungsphase

Für die Partitionierung legen wir zehn sogenannte „Buckets“ an, bezeichnet mit „0“ bis „9“. Auf diese verteilen wir die Zahlen entsprechend ihrer jeweils letzten Ziffer. Die folgende Grafik demonstriert, wie wir die erste Zahl, die 41, in den Bucket „1“ legen:

Die zweite Zahl, die 573, legen wir, entsprechend ihrer letzten Ziffer, in den Bucket „3“:

Die dritte Zahl, die 3, legen wir ebenfalls in den Bucket „3“:

Auf die gleiche Art verteilen wir auch die restlichen Zahlen auf die Buckets:

Die Partitionierungsphase für die letzte Ziffer ist damit abgeschlossen.

Sammelphase

An die Partitionierungsphase schließt sich die Sammelphase an. Wir sammeln die Zahlen, Bucket für Bucket, in aufsteigender Reihenfolge – und innerhalb der Buckets von links nach rechts (also in der gleichen Reihenfolge wie die Zahlen in den jeweiligen Bucket eingetragen wurden) – in eine neue Liste.

Wir beginnen mit dem Buckets mit der kleinsten Ziffer, also Bucket 1:

Danach sammeln wir die Zahlen des nächsthöheren Buckets, also Bucket 3:

Und schließlich die Zahlen aus Bucket 6 und dann Bucket 8:

Alle Buckets sind nun geleert:

In dieser neuen Liste sind die Zahlen nach ihrer letzten Ziffer aufsteigend sortiert: 1, 1, 3, 3, 3, 6, 8

Nach Zehnerstelle sortieren

Wir wiederholen die Partitionierungs- und Sammelphase für die Zehnerstelle. Die zwei Phasen stelle ich dieses Mal mit nur jeweils einer Grafik dar.

In der Partitionierungsphase verteilen wir die Zahlen nach ihrer Zehnerstelle auf die Buckets:

Die Zehnerstelle von einstelligen Zahlen ist die Null. Dementsprechend habe ich die Drei als „03“ dargestellt.

In der Sammelphase entnehmen wir die Zahlen wieder Bucket für Bucket:

Die Zahlen sind nun nach ihren jeweils zwei letzten Ziffern sortiert: 3, 8, 36, 41, 71, 73, 93

Nach Hunderterstelle sortieren

Die gleiche Prozedur wiederholen wir für die Hunderterstelle. Zunächst die Partitionierungsphase:

Und im Anschluss die Sammelphase:

Nach der dritten und letzten Sammelphase sind die Zahlen nun vollständig sortiert.

Hier noch einmal das Endergebnis ohne führende Nullen:

Im nächsten Kapitel kommen wir zur Implementierung von Radix Sort.

Radix Sort in Java

Radix Sort kann auf verschiedene Weisen implementiert werden. Wir beginnen mit einer einfachen Variante, die sich sehr nah am beschriebenen Algorithmus orientiert. Danach zeige ich dir zwei alternative Implementierungen.

Variante 1: Radix Sort mit dynamischen Listen

Wir fangen mit einer leeren sort()-Methode an und füllen diese Schritt für Schritt.

(Das Endergebnis findest du am Ende dieses Abschnitts und in der Klasse RadixSortWithDynamicLists im GitHub-Repository dieser Sortier-Tutorial-Serie.)

public class RadixSortWithDynamicLists

  public void sort(int[] elements) {
    // We will implement this method step by step...
  }

}Code-Sprache: Java (java)

Da wir die zwei Phasen (Partitionierungsphase und Sammelphase) für jede Ziffer wiederholen müssen, müssen wir zunächst einmal feststellen, wie viele Ziffern unsere Zahlen überhaupt haben.

Das tun wir, indem wir die größte Zahl aus dem zu sortierenden Array ermitteln und danach zählen, wie oft sich diese Zahl durch 10 teilen lässt:

public class RadixSortWithDynamicLists

  public void sort(int[] elements) {
    int max = getMaximum(elements);
    int numberOfDigits = getNumberOfDigits(max);

    // TODO: Implement the partitioning and collection phases
  }

  private static int getMaximum(int[] elements) {
    int max = 0;
    for (int element : elements) {
      if (element > max) {
        max = element;
      }
    }
    return max;
  }

  private int getNumberOfDigits(int number) {
    int numberOfDigits = 1;
    while (number >= 10) {
      number /= 10;
      numberOfDigits++;
    }
    return numberOfDigits;
  }

}Code-Sprache: Java (java)

Danach sortieren wir Ziffer für Ziffer. Dazu schreiben wir eine for-Schleife mit der Schleifenvariable digitIndex, wobei 0 für die Einerstelle steht, 1 für die Zehnerstelle, 2 für die Hunderterstelle, usw.

(In den folgenden Listings drucke ich die Klasse selbst nicht mehr mit ab, nur noch die Methoden innerhalb der Klasse.)

public void sort(int[] elements) {
  int max = getMaximum(elements);
  int numberOfDigits = getNumberOfDigits(max);

  for (int digitIndex = 0; digitIndex < numberOfDigits; digitIndex++) {
    // TODO: Sort elements by digit at 'digitIndex'
  }
}Code-Sprache: Java (java)

Für den nächsten Schritt benötigen wir die Buckets, auf die wir die Zahlen verteilen können. Wir könnten hierfür zehn ArrayLists verwenden.

Eleganter ist es jedoch diese in eine Bucket-Klasse zu wrappen. Das macht zum einen den Code lesbarer; zum anderen ermöglicht es uns später die Implementierung der Buckets zu ändern, ohne den restlichen Code anpassen zu müssen.

Die Bucket-Klasse können wir als innere Klasse innerhalb der Klasse RadixSortWithDynamicLists anlegen:

private static class Bucket {
  private final List<Integer> elements = new ArrayList<>();

  private void add(int element) {
    elements.add(element);
  }

  private List<Integer> getElements() {
    return elements;
  }
}Code-Sprache: Java (java)

Das war die Vorbereitung.

Kommen wir zur Partitionierungsphase. Wir benötigen zehn Buckets, auf die wir die Zahlen verteilen können; diese generieren wir mit einer createBuckets()-Methode:

private Bucket[] createBuckets() {
  Bucket[] buckets = new Bucket[10];
  for (int i = 0; i < 10; i++) {
    buckets[i] = new Bucket();
  }
  return buckets;
}Code-Sprache: Java (java)

Danach verteilen wir unsere Zahlen anhand der aktuell betrachteten Stelle digitIndex auf die Buckets:

private void distributeToBuckets(int[] elements, int digitIndex, Bucket[] buckets) {
  int divisor = calculateDivisor(digitIndex);

  for (int element : elements) {
    int digit = element / divisor % 10;
    buckets[digit].add(element);
  }
}

private int calculateDivisor(int digitIndex) {
  int divisor = 1;
  for (int i = 0; i < digitIndex; i++) {
    divisor *= 10;
  }
  return divisor;
}Code-Sprache: Java (java)

Der divisor ist dabei diejenige Zahl, durch die wir ein Element teilen müssen, so dass an der hintersten Stelle die aktuell zu betrachtende Ziffer steht – also 1 für die Einerstelle, 10 für die Zehnerstelle, 100 für die Hunderterstelle, usw.

Die Methoden der Partitionierungsphase fassen wir in einer partition()-Methode zusammen:

private Bucket[] partition(int[] elements, int digitIndex) {
  Bucket[] buckets = createBuckets();
  distributeToBuckets(elements, digitIndex, buckets);
  return buckets;
}Code-Sprache: Java (java)

In der Sammelphase müssen wir nun lediglich die Zahlen der einzelnen Buckets aneinanderreihen:

private void collect(Bucket[] buckets, int[] elements) {
  int targetIndex = 0;
  for (Bucket bucket : buckets) {
    for (int element : bucket.getElements()) {
      elements[targetIndex] = element;
      targetIndex++;
    }
  }
}Code-Sprache: Java (java)

Die partition()– und collect()-Methoden fassen wir in einer sortByDigit()-Methode zusammen:

private void sortByDigit(int[] elements, int digitIndex) {
  Bucket[] buckets = partition(elements, digitIndex);
  collect(buckets, elements);
}Code-Sprache: Java (java)

Und jetzt schließen wir den Kreis, indem wir die sortByDigit()-Methode aus der digitIndex-Schleife der zu Beginn gezeigten sort()-Methode heraus aufrufen:

public void sort(int[] elements) {
  int max = getMaximum(elements);
  int numberOfDigits = getNumberOfDigits(max);

  for (int digitIndex = 0; digitIndex < numberOfDigits; digitIndex++) {
    sortByDigit(elements, digitIndex);
  }
}Code-Sprache: Java (java)

Damit ist unserer Radix-Sort-Implementierung abgeschlossen.

Hier siehst du noch einmal den vollständigen Quellcode:

public class RadixSortWithDynamicLists {

  public void sort(int[] elements) {
    int max = getMaximum(elements);
    int numberOfDigits = getNumberOfDigits(max);

    for (int digitIndex = 0; digitIndex < numberOfDigits; digitIndex++) {
      sortByDigit(elements, digitIndex);
    }
  }

  private static int getMaximum(int[] elements) {
    int max = 0;
    for (int element : elements) {
      if (element > max) {
        max = element;
      }
    }
    return max;
  }

  private int getNumberOfDigits(int number) {
    int numberOfDigits = 1;
    while (number >= 10) {
      number /= 10;
      numberOfDigits++;
    }
    return numberOfDigits;
  }

  private void sortByDigit(int[] elements, int digitIndex) {
    Bucket[] buckets = partition(elements, digitIndex);
    collect(buckets, elements);
  }

  private Bucket[] partition(int[] elements, int digitIndex) {
    Bucket[] buckets = createBuckets();
    distributeToBuckets(elements, digitIndex, buckets);
    return buckets;
  }

  private Bucket[] createBuckets() {
    Bucket[] buckets = new Bucket[10];
    for (int i = 0; i < 10; i++) {
      buckets[i] = new Bucket();
    }
    return buckets;
  }

  private void distributeToBuckets(int[] elements, int digitIndex, Bucket[] buckets) {
    int divisor = calculateDivisor(digitIndex);

    for (int element : elements) {
      int digit = element / divisor % 10;
      buckets[digit].add(element);
    }
  }

  private int calculateDivisor(int digitIndex) {
    int divisor = 1;
    for (int i = 0; i < digitIndex; i++) {
      divisor *= 10;
    }
    return divisor;
  }

  private void collect(Bucket[] buckets, int[] elements) {
    int targetIndex = 0;
    for (Bucket bucket : buckets) {
      for (int element : bucket.getElements()) {
        elements[targetIndex] = element;
        targetIndex++;
      }
    }
  }

  private static class Bucket {
    private final List<Integer> elements = new ArrayList<>();

    private void add(int element) {
      elements.add(element);
    }

    private List<Integer> getElements() {
      return elements;
    }
  }
}Code-Sprache: Java (java)

Die RadixSortWithDynamicLists-Klasse im GitHub-Repository unterscheidet sich übrigens leicht von dem hier abgedruckten Quellcode:

• Sie implementiert das Interface SortAlgorithm, das es ermöglicht verschiedene Radix-Sort-Implementierungen miteinander und mit den anderen Algorithmen der Sortieralgorithmen-Serie zu vergleichen.
• Die getMaximum()-Methode ist in die Klasse ArrayUtils ausgelagert.
• Die Methoden getNumberOfDigits() und calculateDivisor() liegen in der Klasse RadixSortHelper und können so auch in anderen Radix-Sort-Implementierungen verwendet werden.

Die gezeigte Implementierung hat ein Manko:

Dynamische Listen (also Listen, deren Größe sich zur Laufzeit ändern kann) sind für leistungskritische Einsatzzwecke wie Sortieralgorithmen nicht optimal, da das Hinzufügen von Elementen mit einem gewissen Performance-Overhead verbunden ist (bei einer verketteten Liste beispielsweise müssen neue Knoten angelegt werden; bei einer ArrayList muss das Array in bestimmten Abständen in ein größeres umkopiert werden).

Im nächsten Abschnitt zeige ich dir daher eine alternativen Variante.

Variante 2: Radix Sort mit Arrays

Wir können die Implementierung deutlich beschleunigen (wir werden die Performance der Implementierungen im Anschluss vergleichen), indem wir für die Buckets statt einer ArrayList ein Array verwenden.

Da Arrays eine feste Größe haben, müssen wir vor der Erstellung eines Buckets wissen, wie viele Elemente der Bucket enthalten soll. Wir ändern unsere Bucket-Klasse wie folgt ab und übergeben die Größe an dessen Konstruktor:

private static class Bucket {
  private final int[] elements;
  private int addIndex;

  private Bucket(int size) {
    elements = new int[size];
  }

  private void add(int element) {
    elements[addIndex] = element;
    addIndex++;
  }

  private int[] getElements() {
    return elements;
  }
}Code-Sprache: Java (java)

Um zu bestimmen, wie viele Elemente ein Bucket enthalten soll, zählen wir vorab die Ziffern an der aktuell betrachteten Stelle digitIndex. Die partition()-Methode sieht dann so aus:

private Bucket[] partition(int[] elements, int digitIndex) {
  int[] counts = countDigits(elements, digitIndex);
  Bucket[] buckets = createBuckets(counts);
  distributeToBuckets(elements, digitIndex, buckets);
  return buckets;
}

private int[] countDigits(int[] elements, int digitIndex) {
  int[] counts = new int[10];
  int divisor = calculateDivisor(digitIndex);
  for (int element : elements) {
    int digit = element / divisor % 10;
    counts[digit]++;
  }
  return counts;
}

private Bucket[] createBuckets(int[] counts) {
  Bucket[] buckets = new Bucket[10];
  for (int i = 0; i < 10; i++) {
    buckets[i] = new Bucket(counts[i]);
  }
  return buckets;
}Code-Sprache: Java (java)

Die distributeToBuckets()-Methode brauchen wir nicht zu ändern, ebensowenig alle anderen in Variante 1 gezeigten Methoden. Gut, dass wir in Variante 1 eine Bucket-Klasse verwendet haben und nicht direkt eine ArrayList :-)

Den vollständigen Code von Variante 2 findest du im GitHub-Repository in der Klasse RadixSortWithArrays.

Kommen wir zu einer dritten Variante.

Variante 3: Radix Sort mit Counting Sort

In Variante 2 haben wir vorab gezählt, wie viele Elemente in jeden Bucket sortiert werden müssen. Mit dieser Information können wir die Buckets auch überspringen und die Elemente direkt an ihre Zielpositionen verschieben. Und zwar indem wir die allgemein Form von Counting Sort anwenden.

Wie Counting Sort funktioniert, werde ich an dieser Stelle nicht noch einmal wiederholen. Ich zeige dir direkt die Implementierung:

public class RadixSortWithCountingSort {

  @Override
  public void sort(int[] elements) {
    int max = getMaximum(elements);
    int numberOfDigits = getNumberOfDigits(max);

    // Remember input array
    int[] inputArray = elements;

    for (int digitIndex = 0; digitIndex < numberOfDigits; digitIndex++) {
      elements = sortByDigit(elements, digitIndex);
    }

    // Copy sorted elements back to input array
    System.arraycopy(elements, 0, inputArray, 0, elements.length);
  }

  // Same as in the other variants:
  // getMaximum(), getNumberOfDigits(), calculateDivisor() 

  private int[] sortByDigit(int[] elements, int digitIndex) {
    int[] counts = countDigits(elements, digitIndex);
    int[] prefixSums = calculatePrefixSums(counts);
    return collectElements(elements, digitIndex, prefixSums);
  }

  private int[] countDigits(int[] elements, int digitIndex) {
    int[] counts = new int[10];
    int divisor = calculateDivisor(digitIndex);
    for (int element : elements) {
      int digit = element / divisor % 10;
      counts[digit]++;
    }
    return counts;
  }

  private int[] calculatePrefixSums(int[] counts) {
    int[] prefixSums = new int[10];
    prefixSums[0] = counts[0];
    for (int i = 1; i < 10; i++) {
      prefixSums[i] = prefixSums[i - 1] + counts[i];
    }
    return prefixSums;
  }

  private int[] collectElements(int[] elements, int digitIndex, int[] prefixSums) {
    int divisor = calculateDivisor(digitIndex);
    int[] target = new int[elements.length];
    for (int i = elements.length - 1; i >= 0; i--) {
      int element = elements[i];
      int digit = element / divisor % 10;
      target[--prefixSums[digit]] = element;
    }
    return target;
  }

}Code-Sprache: Java (java)

Diesen Code findest du ebenfalls im GitHub-Repository, in der Klasse RadixSortWithCountingSort.

Radix Sort Varianten

Es gibt zwei grundlegende Varianten von Radix Sort, die sich durch die Reihenfolge unterscheiden, in der wir die Ziffern der Elemente betrachten.

LSD Radix Sort

Der im ersten Kapitel gezeigte Radix-Sort-Algorithmus nennt sich „LSD Radix Sort“. LSD steht dabei für „least significant digit“, also „niedrigstwertige Stelle“. Wir haben mit dem Sortieren bei der niedrigstwertigen Stelle (den Einern) begonnen und uns Ziffer für Ziffer bis zur höchstwertigen Stelle vorgearbeitet.

MSD Radix Sort

Alternativ können wir auch bei der höchstwertigen Stelle, „most significant digit“ beginnen. Entsprechend heißt die zweite Variante „MSD Radix Sort“.

Dabei müssen wir allerdings anders vorgehen als bei der LSD-Variante. Denn wenn wir in unserem Ausgangsbeispiel die gesamte Eingabeliste zunächst nach Hundertern, dann nach Zehnern und zuletzt nach der Einerstelle sortieren würden, würde folgendes passieren (die Buckets habe ich in der Grafik weggelassen, da es nur um die Ergebnisse nach den drei Collect-Phasen geht):

Die Sortierung nach der Zehner- und Einerstelle hat die jeweiligen vorherigen Sortierungen wieder durcheinander gebracht.

Das Problem ist schnell gelöst:

Nach der Hunderterstelle dürfen wir die Eingabeliste nicht erneut als Ganzes sortieren, sondern die Hunderterstellen-Buckets in sich. Die daraus wiederum resultierenden Zehnerstellen-Buckets sortieren wir dann jeweils nach der Einerstelle. Wir sortieren die Buckets also rekursiv.

MSD Radix Sort – Schritt für Schritt

Die folgenden Grafiken zeigen das rekursive MSD-Radix-Sort-Verfahren Schritt für Schritt am Eingangsbeispiel. Buckets werden durch schwarze Klammern unter den Elementen dargestellt. Leere Buckets werden nicht angezeigt.

Wir beginnen mit der Partitionierung nach Hunderterstellen:

Anstatt nun von der Partitionierungs- in die Sammelphase überzugehen, führen wir auf jedem Bucket eine weitere Partitionierungsphase aus – und zwar auf der nächst niedrigeren Stelle, also den Zehnern.

Leere Buckets und solche, die nur ein Element enthalten (wie die 271 und die 836), brauchen brauchen wir nicht weiter zu partitionieren.

Eigentlich müssten wir die Buckets nun noch nach Einerstellen partitionieren. Da aber keiner der Zehnerstellen-Buckets mehr als ein Element enthält, ist das nicht notwendig.

Wir steigen daher aus der Rekursion wieder aus. Zunächst führen wir eine Sammelphase auf den Zehnerstellen-Buckets aus:

Und zuletzt führen wir die Sammelphase auf den Hunderterstellen-Buckets aus:

Die Sortierung ist damit abgeschlossen.

MSD Radix Sort – Implementierung

Genau wie die LSD-Variante kann auch MSD Radix Sort mit Dynamischen Listen, Arrays und mit Counting Sort implementiert werden.

Ich zeige dir, wie du die oben gezeigte LSD-Array-Implementierung mit wenigen Änderungen in eine MSD-Implementierung ändern kannst.

Hier sind noch einmal die Methoden sort() und sortByDigit() der Klasse RadixSortWithArrays:

public void sort(int[] elements) {
  int max = getMaximum(elements);
  int numberOfDigits = getNumberOfDigits(max);

  for (int digitIndex = 0; digitIndex < numberOfDigits; digitIndex++) {
    sortByDigit(elements, digitIndex);
  }
}

private void sortByDigit(int[] elements, int digitIndex) {
  Bucket[] buckets = partition(elements, digitIndex);
  collect(buckets, elements);
}
Code-Sprache: Java (java)

Alles was wir nun tun müssen, ist die sortByDigit()-Methode für die höchstwertige Stelle aufzurufen und zwischen Partitionierungs- und Sammelphase den rekursiven Aufruf für die nächstniedrigere Stelle einzufügen:

public void sort(int[] elements) {
  int max = getMaximum(elements);
  int numberOfDigits = getNumberOfDigits(max);

  sortByDigit(elements, numberOfDigits - 1);
}

private void sortByDigit(int[] elements, int digitIndex) {
  Bucket[] buckets = partition(elements, digitIndex);

  // If we haven't reached the last digit, 
  // sort the buckets by the next digit, recursively
  if (digitIndex > 0) {
    for (Bucket bucket : buckets) {
      if (bucket.needsToBeSorted()) {
        sortByDigit(bucket.getElements(), digitIndex - 1);
      }
    }
  }

  collect(buckets, elements);
}Code-Sprache: Java (java)

Die Methode Bucket.needsToBeSorted() gibt true zurück, wenn der Bucket wenigstens ein Element enthält.

Den vollständigen Code findest du im GitHub-Repository in der Klasse RecursiveMsdRadixSortWithArrays.

Ich überlasse es dir als Übungsaufgabe auch für die zwei anderen LSD-Implementierungen (dynamische Listen und Counting Sort) je eine MSD-Variante zu schreiben.

Verwendung anderer Basen

Bisher haben wir die Partitionierung nach dem Dezimalsystem, also mit 10 Buckets, durchgeführt. Wir können aber auch mit jeder anderen Basis arbeiten, also beispielsweise mit dem Binärsystem (2 Buckets), dem Hexadezimalsystem (16 Buckets) oder auch mit hundert, tausend oder mehr Buckets.

Je höher die Basis, desto mehr Buckets, desto aufwändiger die Partitionierungsphase. Andererseits haben die zu sortierenden Zahlen dann weniger Stellen (1.000.000 dezimal = F4240 hexadezimal), so dass insgesamt weniger Partitionierungs- und Sammelphasen stattfinden müssen. Was das für die Performance bedeutet, werden wir im Kapitel „Radix Sort Laufzeit“ ermitteln.

Wie implementiert man Radix Sort mit einer anderen Basis?

Im Grunde genommen müssen wir jedes Vorkommen der Zahl 10 im Quellcode durch die neue Basis ersetzen. In der Klasse RadixSortWithDynamicLists kommt die 10 in den folgenden Methoden vor:

private int getNumberOfDigits(int number) {
  int numberOfDigits = 1;
  while (number >= 10) {
    number /= 10;
    numberOfDigits++;
  }
  return numberOfDigits;
}

private Bucket[] createBuckets() {
  Bucket[] buckets = new Bucket[10];
  for (int i = 0; i < 10; i++) {
    buckets[i] = new Bucket();
  }
  return buckets;
}

private void distributeToBuckets(int[] elements, int digitIndex, Bucket[] buckets) {
  int divisor = calculateDivisor(digitIndex);

  for (int element : elements) {
    int digit = element / divisor % 10;
    buckets[digit].add(element);
  }
}

private int calculateDivisor(int digitIndex) {
  int divisor = 1;
  for (int i = 0; i < digitIndex; i++) {
    divisor *= 10;
  }
  return divisor;
}Code-Sprache: Java (java)

Wir können die 10 an all diesen Stellen durch eine andere Basis ersetzen. Besser noch: Wir ersetzen sie durch eine Variable, so dass wir den Sortieralgorithmus mit jeder beliebigen Basis aufrufen können.

In der Klasse RadixSortWithDynamicListsAndCustomBase findest du die entsprechende Anpassung:

public class RadixSortWithDynamicListsAndCustomBase implements SortAlgorithm {

  private final int base;

  public RadixSortWithDynamicListsAndCustomBase(int base) {
    this.base = base;
  }

  // All methods not printed here are the same as in RadixSortWithDynamicLists

  private int getNumberOfDigits(int number) {
    int numberOfDigits = 1;
    while (number >= base) {
      number /= base;
      numberOfDigits++;
    }
    return numberOfDigits;
  }

  private Bucket[] createBuckets() {
    Bucket[] buckets = new Bucket[base];
    for (int i = 0; i < base; i++) {
      buckets[i] = new Bucket();
    }
    return buckets;
  }

  private void distributeToBuckets(int[] elements, int digitIndex, Bucket[] buckets) {
    int divisor = calculateDivisor(digitIndex);

    for (int element : elements) {
      int digit = element / divisor % base;
      buckets[digit].add(element);
    }
  }

  private int calculateDivisor(int digitIndex) {
    int divisor = 1;
    for (int i = 0; i < digitIndex; i++) {
      divisor *= base;
    }
    return divisor;
  }

}Code-Sprache: Java (java)

Beachte bitte, dass im GitHub-Repository die Methoden getNumberOfDigits() und calculateDivisor() in die Klasse RadixSortHelper ausgelagert sind, da sie auch von anderen Radix-Sort-Implementierungen benötigt werden.

Im GitHub-Repository findest du außerdem die angepassten Algorithmen für Arrays, Counting Sort und rekursives MSD Radix Sort:

• Dynamische Listen + variable Basis: RadixSortWithDynamicListsAndCustomBase
• Arrays + variable Basis: RadixSortWithArraysAndCustomBase
• Counting Sort + variable Basis: RadixSortWithCountingSortAndCustomBase
• Rekursives MSD Radix Sort + variable Basis: RecursiveMsdRadixSortWithArraysAndCustomBase

Radix Sort Zeitkomplexität

In diesem Kapitel zeige ich dir, wie du die Zeitkomplexität von Radix Sort bestimmst. Eine Einführung in das Thema Zeitkomplexität findest du im Artikel „Zeitkomplexität“ und „O-Notation„.

Wir verwenden im Folgenden die folgenden Variablen:

• n = die Anzahl der zu sortierenden Elemente
• k = die maximale Schlüssellänge („key length“, Anzahl der Stellen) der zu sortierenden Elemente
• b = die Basis (= die Anzahl der Buckets)

Der Algorithmus iteriert über k Stellen; für jede Stelle betreibt er den folgenden Aufwand:

• Er legt b Buckets an. Der Aufwand dafür ist jeweils konstant.
• Er iteriert über alle n Elemente, um diese in die Buckets einzusortieren. Der Aufwand für die Berechnung der Bucket-Nummer und für das Einfügen in den Bucket ist konstant.
• Er iteriert über b Buckets und entnimmt diesen wieder insgesamt n Elemente. Der Aufwand für jeden dieser Schritte ist wiederum konstant.

Konstante Aufwände vernachlässigen wir bei der Bestimmung der Zeitkomplexität. Somit ergibt sich:

Die Zeitkomplexität für Radix Sort ist: O(k · (b + n))

Der Aufwand ist unabhängig davon, wie die Eingabezahlen angeordnet sind. Ob diese zufällig verteilt oder bereits vorsortiert sind, macht keinen Unterschied für den Algorithmus. Best case, average case und worst case sind also identisch.

Die Formel sieht erstmal kompliziert aus. Doch zwei der drei Variablen sind in den meisten Fällen gar nicht variabel. Wenn wir z. B. Longs mit der Basis 10 sortieren, können wir k durch 19 ersetzen (der maximal mögliche Wert für ein Long ist 9.223.372.036.854.775.807) und b durch 10.

Die Formel wird dann zu O(19 · (10 + n)). Konstanten können wir weglassen, somit ergibt sich:

Die Zeitkomplexität für Radix Sort
bei bekannter maximaler Länge der zu sortierenden Elemente
und mit festgelegter Basis ist: O(n)

Radix Sort hat also für primitive Datentypen wie Integer und Long (bei diesen kennen wir die maximale Länge) eine bessere Zeitkomplexität als Quicksort!

Ob Radix Sort tatsächlich schneller ist, erfährst du im nächsten Kapitel. Dort werden wir die Laufzeit der verschiedenen Radix-Sort-Implementierungen messen und untereinander (und auch mit Quicksort) vergleichen.

Radix Sort Laufzeit

In diesem Kapitel zeige ich dir die Ergebnisse einiger Performance-Tests, die ich mit den Tools UltimateTest und CompareRadixSorts durchgeführt habe, um die Performance der verschiedenen Algorithmen, Implementierungen und Basen zu vergleichen.

Laufzeit verschiedener Radix-Sort-Implementierungen

Das erste Diagramm zeigt den Vergleich der verschiedenen Implementierungen:

Die Implementierung mit dynamischen Listen schneidet, wie vermutet, am schlechtesten ab. Die restlichen drei Varianten liefern sich ein Kopf-an-Kopf-Rennen, das die Implementierung mit Counting Sort knapp gewinnt, dicht gefolgt von der Implementierung mit Arrays.

Sehr schön zu sehen ist auch die jeweils lineare Laufzeit O(n), die wir im vorangegangenen Kapitel vorhergesagt hatten.

Auswirkung der Basis auf die Laufzeit

Das zweite Diagramm zeigt, wie sich die Wahl der Basis auf die Laufzeit der Array-Implementierung auswirkt:

Wir können sehen, dass die Laufzeit bei einer Basis von 100 und 1.000 deutlich besser ist als bei kleineren als auch größeren Basen.

Untersuchen wir das etwas detaillierter… Das dritte Diagramm zeigt feinere Abstufungen der Basen bei gleicher Anzahl Elemente (n = 5,555,555):

Sowohl eine zu kleine als auch eine zu große Basis sind schlecht für die Performance.

Eine sehr kleine Basis führt dazu, dass viele Iterationen durchgeführt werden müssen. Eine zu große Basis führt zwar zu weniger Iterationen, aber deutlich mehr Buckets innerhalb der Iterationen.

Ein Sweetspot zeigt sich bei einer Basis von 256.

Radix Sort vs. Quicksort

In folgendem Diagramm siehst du die Laufzeiten…

• der Radix-Sort-Array-Implementierung mit einer Basis von 256,
• von Dual-Pivot Quicksort kombiniert mit Insertion Sort (die schnellste Variante, die wir im Quicksort-Tutorial ermittelt haben)
• und der JDK-Sortiermethode Arrays.sort(), welche ebenfalls ein optimiertes Dual-Pivot Quicksort implementiert.

Und tatsächlich ist Radix Sort nicht nur in der Theorie schneller – O(n) vs. O(n log n) – sondern auch in der Praxis – und zwar sowohl im Vergleich mit dem selbst implementierten Quicksort als auch mit der noch schnelleren JDK-Quicksort-Implementierung Arrays.sort().

Wenn du also int-Primitive sortieren musst und die Performance kritisch ist, solltest du erwägen statt des Java-Hausmittels Arrays.sort() besser Radix-Sort einzusetzen. Du kannst gerne die Implementierung aus diesem Artikel verwenden.

Für long-Primitive gilt das nicht, hier ist Arrays.sort() etwa 50% schneller als meine Radix-Sort-Implementierung.

Weitere Eigenschaften von Radix Sort

In diesem abschließenden Kapitel betrachten wir die Platzkomplexität, Stabilität und Parallelisierbarkeit von Radix Sort, sowie die Unterschiede zu Counting Sort und Bucket Sort.

Radix Sort Platzkomplexität

Alle hier gezeigten Varianten benötigen zusätzlichen Speicherplatz:

• O(b) für das Zählen der Ziffern (nicht benötigt in der Variante mit dynamischen Listen)
• O(b) für die Referenzen auf die Buckets (nicht benötigt bei der Counting-Sort-Variante)
• O(n) für die Buckets (nicht benötigt bei der Counting-Sort-Variante)
• O(n) für ein zusätzliches Ziel-Array (nur bei der Counting-Sort-Variante)

Jede Variante enthält also mindestens einen O(b)-Anteil und mindestens einen O(n)-Anteil.

Somit gilt:

Die Platzkomplexität von Radix Sort ist: O(b + n)

Es gibt eine Ausnahme: Rekursives MSD Radix Sort mit der Basis 2 kann ohne zusätzlichen Speicher für die Elemente auskommen, indem diese derart partitioniert werden, dass durch jeweiligen Austausch zweier Elemente alle Elemente, deren Bit an der gerade betrachteten Stelle auf 1 steht, an den rechten Rand geschoben werden und alle Elemente, deren Bit auf 0 steht, an den linken Rand (ähnlich wie bei Quicksort).

Ist Radix Sort stabil?

Die Bedeutung von Stabilität bei Sortierverfahren kannst du im verlinkten Einführungsartikel nachlesen. Kurz gesagt: Elemente mit dem gleichen Schlüssel behalten bei der Sortierung ihre ursprüngliche Reihenfolge zueinander bei.

Alle in diesem Artikel gezeigten Implementierungen von Radix Sort sind stabil.

Die im vorherigen Abschnitt angesprochene In-Place-MSD-Radix-Sort-Variante ist hingegen nicht stabil (analog zu Quicksort).

Paralleles Radix Sort

Beide Radix-Sort-Varianten (LSD und MSD) lassen sich parallelisieren.

MSD Radix Sort parallel

Bei MSD Radix Sort können wir nach der ersten Partitionierungsphase alle entstandenen Buckets unabhängig voneinander parallel sortieren. Dank paralleler Streams lässt sich das in Java sehr einfach implementieren:

Hier noch einmal der entsprechende sequentielle Code aus der Klasse RecursiveMsdRadixSortWithArrays:

for (Bucket bucket : buckets) {
  if (bucket.needsToBeSorted()) {
    sortByDigit(bucket.getElements(), digitIndex - 1);
  }
}Code-Sprache: Java (java)

Und hier die parallelisierte Variante (Klasse ParallelRecursiveMsdRadixSortWithArrays im GitHub-Repository):

Arrays.stream(buckets)
    .parallel()
    .forEach(
        bucket -> {
          if (bucket.needsToBeSorted()) {
            sortByDigit(bucket.getElements(), digitIndex - 1);
          }
        });Code-Sprache: Java (java)

LSD Radix Sort parallel

Um LSD Radix Sort zu parallelisieren, müssen wir etwas mehr Aufwand betreiben:

1. Wir teilen das Eingabe-Array in parallel zu bearbeitende Segmente auf (z. B. entsprechend der Anzahl der CPU-Kerne).
2. Wir berechnen parallel pro Segment, wie viele Elemente in welche Buckets sortiert werden müssen.
3. Wenn Schritt 2 für alle Segmente abgeschlossen ist, berechnen wir a) pro Bucket die Gesamtanzahl der Elemente und b) pro Segment die Start-Schreibpositionen für jeden Bucket.
4. Wir verteilen die Elemente der Segmente parallel auf die Buckets. Durch die in Schritt 3 berechneten Start-Schreibpositionen wissen wir, an welchen Positionen innerhalb der Buckets wir aus welchen Segmenten schreiben dürfen.
5. Wenn Schritt 4 für alle Segmente abgeschlossen ist, berechnen wir pro Bucket den Offset im Zielarray (als Präfixsummen über die Anzahl der Elemente der Buckets).
6. Wir sammeln die Elemente der Buckets parallel ein. Durch die in Schritt 5 berechneten Offsets wissen wir, an welcher Position im Zielarray die Elemente eines Buckets starten müssen.

Den Quellcode findest du in der Klasse ParallelRadixSortWithArrays im GitHub-Repo. Die sechs oben aufgezählten Schritte sind im Code mit entsprechend nummerierten Kommentaren markiert.

Radix Sort parallel vs. sequentiell

Das folgende Diagramm zeigt die Laufzeit der parallelen Varianten verglichen mit den sequentiellen Varianten auf einer 6-Kern-i7-CPU:

Die parallelen Varianten sind bei 67 Millionen Elementen nur etwa 2,3 mal schneller. Dass Faktor 6 nicht einmal annähernd erreicht wird, liegt zum einen daran, dass Teile des Codes nicht parallel ausgeführt werden können und zum anderen daran, dass die CPU-Kerne sehr viele Daten mit dem Arbeitsspeicher austauschen müssen (das Eingabearray belegt 1 GB).

Wenn wir uns einen kleineren Ausschnitt des Diagramms anschauen, sieht die Sache anders aus:

Bei einer halben Million Elemente ist das parallele Radix Sort mit Arrays 5,75 mal schneller als die sequentielle Variante. Die CPU-Kerne werden also nahezu komplett ausgenutzt. Das liegt daran, dass das Eingabearray nur noch 2 MB groß ist, und die Sortierung somit komplett im L3-Cache der CPU stattfinden kann.

Radix Sort vs. Counting Sort

Beide Sortierverfahren verwenden Buckets zum Sortieren. Bei Counting Sort benötigen wir einen Bucket für jeden Wert. Wollten wir beispielsweise Integers sortieren, bräuchten wir etwa vier Milliarden Buckets. Bei Radix Sort hingegen entspricht die Anzahl der Buckets der gewählten Basis.

Bei Radix Sort sortieren wir iterativ Ziffer für Ziffer; bei Counting Sort sortieren wir die Elemente in einer einzigen Iteration.

Counting Sort eignet sich daher in erster Linie für kleine Zahlenräume.

Radix Sort vs. Bucket Sort

Bei Bucket Sort werden die Elemente zunächst so auf eine vorgegebene Anzahl Buckets verteilt, dass alle Elemente eines Buckets größer sind als alle Elemente des vorherigen Buckets (z. B. 0-99, 100-199, 200-299, usw.).

Danach wird jeder Bucket in sich sortiert – entweder rekursiv mit Bucket Sort oder mit einem anderen Sortierverfahren – mit welchem genau ist nicht spezifiziert. Abschließend werden die Elemente aus den sortierten Buckets aneinandergereiht.

Falls dir das bekannt vorkommt – eine Form von Bucket Sort hast du in diesem Artikel kennengelernt: das rekursive MSD Radix Sort.

Zusammenfassung

Radix Sort ist ein stabiler Sortieralgorithmus mit einer allgemeinen Zeitkomplexität von O(k · (b + n)), wobei k für die maximale Schlüssellänge („key length“) der zu sortierenden Elemente steht und b für die Basis.

Ist die maximale Länge der zu sortierenden Elemente bekannt und die Basis festgelegt, dann beträgt die Zeitkomplexität O(n).

Für Integers ist Radix Sort schneller als Quicksort (zumindest auf meiner Testumgebung). Solltest du zeitkritische Sortiervorgänge in Java implementieren müssen, empfehle ich dir Arrays.sort() mit einer Implementierung von Radix Sort zu vergleichen.

Weitere Sortieralgorithmen findest du in der Übersicht aller Sortieralgorithmen und ihrer Eigenschaften im ersten Teil der Artikelserie.

Alle bisher in dieser Artikelserie behandelten Sortierverfahren basieren auf dem Vergleich, ob zwei Zahlen kleiner, größer oder gleich sind. Counting Sort basiert auf einer komplett anderen, nicht-vergleichsbasierten Herangehensweise.

Dieser Artikel beantwortet folgende Fragen:

• Wie funktioniert Counting Sort?
• Was unterscheiden sich die vereinfachte Form von Counting Sort und die allgemeine Form?
• Wie sieht der Quellcode von Counting Sort aus?
• Wie bestimmt man die Zeitkomplexität von Counting Sort?
• Warum ist Counting Sort trotz exakt gleicher Anzahl an Operationen für vorsortierte Zahlenfolgen fast zehn Mal schneller als für unsortierte?

Counting Sort Algorithmus (Vereinfachte Form)

Anstatt Elemente zu vergleichen, wird bei Counting Sort gezählt, wie oft welche Elemente in der zu sortierenden Menge vorkommen.

Eine vereinfachte Form von Counting Sort kann angewendet werden, wenn Zahlen (z. B. int-Primitive) sortiert werden sollen – für Objekte, die entsprechend ihrer Keys sortiert werden sollen, wirst du im Anschluss die allgemeine Form von Counting Sort kennenlernen.

Die vereinfachte Form besteht aus zwei Phasen:

Counting Sort Algorithmus – Phase 1: Elemente zählen

Zunächst wird ein zusätzliches Array angelegt, dessen Länge der Größe des Zahlenraums entspricht (z. B. ein Array der Größe 256, um Bytes zu sortieren). Dann iteriert man einmal über die zu sortierenden Elemente und erhöht für jedes Element den Wert im Array an derjenigen Position, die der zu sortierenden Zahl entspricht, um eins.

Hier ein Beispiel mit dem Zahlenraum 0–9 (d. h. in dem zu sortierenden Array kommen nur Zahlen von 0 bis 9 vor).

Folgendes Array soll sortiert werden:

Wir erstellen ein zusätzliches Array der Länge 10, das mit Nullen initialisiert ist. In der Grafik wird unter der Linie der Array-Index mit angezeigt:

Nun iterieren wir über das zu sortierende Array. Das erste Element ist eine 3 – dementsprechend erhöhen wir den Wert im Hilfsarray an der Position 3 um eins:

Das zweite Element ist eine 7. Wir erhöhen im Hilfsarray das Feld an Position 7 um eins:

Es folgen die Elementen 4 und 6 – dementsprechend erhöhen wir auch die Werte an den Positionen 4 und 6 jeweils um eins:

Mit den nächsten zwei Elementen – der 6 und der 3 – folgen zwei Elemente, die schon einmal vorkamen. Entsprechend werden die Felder im Hilfsarray von 1 auf 2 erhöht:

Das Prinzip sollte nun klar sein. Nachdem auch die Hilfsarray-Werte für die restlichen zu sortierenden Elemente entsprechend erhöht wurden, sieht das Hilfsarray am Ende wie folgt aus:

Aus diesem sogenannten Histogramm lässt sich folgendes ablesen:

Die zu sortierenden Elemente enthalten:

• 1 mal die 0,
• 0 mal die 1,
• 1 mal die 2,
• 3 mal die 3,
• 1 mal die 4,
• 0 mal die 5,
• 5 mal die 6,
• 1 mal die 7,
• 2 mal die 8 und
• 1 mal die 9.

Diese Informationen werden wir in Phase 2 verwenden, um das zu sortierende Array neu anzuordnen.

Counting Sort Algorithmus – Phase 2: Elemente neu anordnen

In Phase zwei iterieren wir einmal über das Histogramm-Array. Dabei schreiben wir den jeweiligen Array-Index so oft in das zu sortierende Array, wie es das Histogramm an der entsprechenden Stelle anzeigt.

Im Beispiel starten wir an Position 0 im Hilfsarray. Dort steht die 1, wir schreiben daher die 0 genau ein Mal in das zu sortierende Array.

(Die restlichen Zahlen habe ich ausgegraut, da sie zwar nach wie vor im Array stehen, wir sie aber nicht mehr benötigen, da wir diese Informationen jetzt komplett im Histogramm haben.)

An Position 1 im Histogramm steht eine 0, d. h. wir überspringen dieses Feld – es wird keine 1 in das zu sortierende Array geschrieben.

Position 2 des Histogramms enthält wieder eine 1; wir schreiben also einmal eine 2 in das zu sortierende Array:

Kommen wir zu Position 3, diese enthält eine 3, wir schreiben also drei Mal eine 3 in das Array:

Und so geht es weiter… wir schreiben einmal die 4, fünfmal die 6, einmal die 7, zweimal die 8 und zuletzt einmal die 9 in das zu sortierende Array:

Die Zahlen sind sortiert, der Algorithmus ist beendet.

Counting Sort Java Code Beispiel (Vereinfachte Form)

Im folgenden findest du eine sehr einfache Form des Counting Sort-Quellcodes – diese funktioniert ausschließlich für nicht-negative int-Primitive (z. B. für das Array aus dem Beispiel oben).

Zunächst wird über die findMax()-Methode das größte Element im Array gefunden. Dann wird das Hilfsarray counts der entsprechenden Größe angelegt, wobei die Größe um eins größer ist als das größte Element, um auch die 0 mitzählen zu können.

(Bei kleineren Zahlenräumen wie byte und short kann das Ermitteln des Maximums auch weggelassen werden und direkt ein Array in der Größe des Zahlenraums erstellt werden.)

Im mit „Phase 1“ kommentierten Block werden die Elemente gezählt, so dass das counts-Array schließlich das Histogramm enthält.

Im mit „Phase 2“ kommentierten Block werden die Elemente in aufsteigender Reihenfolge und entsprechend der im Histogramm hinterlegten Häufigkeit zurück in das zu sortierende Array geschrieben.

public class CountingSortSimple {

  public void sort(int[] elements) {
    int maxValue = findMax(elements);
    int[] counts = new int[maxValue + 1];

    // Phase 1: Count
    for (int element : elements) {
      counts[element]++;
    }

    // Phase 2: Write results back
    int targetPos = 0;
    for (int i = 0; i < counts.length; i++) {
      for (int j = 0; j < counts[i]; j++) {
        elements[targetPos++] = i;
      }
    }
  }

  private int findMax(int[] elements) {
    int max = 0;
    for (int element : elements) {
      if (element < 0) {
        throw new IllegalArgumentException("This implementation does not support negative values.");
      }
      if (element > max) {
        max = element;
      }
    }
    return max;
  }

}Code-Sprache: Java (java)

Das Maximum könnte auch mittels Arrays.stream(elements).max().getAsInt() ermittelt werden. Dann müssten wir allerdings die Prüfung auf negative Werte entweder weglassen oder in einem separaten Schritt durchführen.

Den Code findest du im GitHub-Repository in der Klasse CountingSortSimple.

Counting Sort Quellcode auch für negative Zahlen

Sollen auch negative Zahlen erlaubt sein, wird der Code etwas komplizierter, da wir mit einem sogenannten Offset arbeiten müssen, um die zu sortierende Zahl auf die Position im Hilfsarray zu mappen.

Berechnung des Offset

Der Offset ist: null minus die kleinste zu sortierende Zahl.

Ist beispielsweise -5 die kleinste zu sortierende Zahl, dann ist der Offset 5, d. h. der Index im Hilfsarray ist jeweils die zu sortierende Zahl plus 5.

Die -5 wird also beispielsweise an Position -5+5 = 0 gezählt; die 0 wird an Position 0+5 = 5 gezählt; die 11 wird an Position 11+5 = 16 gezählt.

Quellcode

Den folgenden Quellcode findest du in der Klasse CountingSort im GitHub-Repository. Er ähnelt dem oben gezeigte Quellcode bis auf folgende Unterschiede:

• Die Methode findMax() ist ersetzt durch die Methode findBoundaries(), die nicht nur den Maximal-, sondern auch den Minimalwert zurückgibt (bei kleinen Zahlenräumen wie byte und short kann das Ermitteln der Grenzwerte weggelassen werden und direkt ein Array in der Größe des Zahlenraums erstellt werden).
• Beim Zugriff auf das counts-Array in der Zählphase wird dem jeweiligen Index der Offset -boundaries.min hinzuaddiert (bzw. -Byte.MIN_VALUE oder -Short.MIN_VALUE).
• Beim Zurückschreiben der sortierten Zahlen in das Array wird der Offset wieder abgezogen, indem boundaries.min (bzw. Byte.MIN_VALUE oder Short.MIN_VALUE) addiert wird.

public class CountingSort {

  private static final int MAX_VALUE_TO_SORT = Integer.MAX_VALUE / 2;
  private static final int MIN_VALUE_TO_SORT = Integer.MIN_VALUE / 2;

  public void sort(int[] elements) {
    Boundaries boundaries = findBoundaries(elements);
    int[] counts = new int[boundaries.max - boundaries.min + 1];

    // Phase 1: Count
    for (int element : elements) {
      counts[element - boundaries.min]++;
    }

    // Phase 2: Write results back
    int targetPos = 0;
    for (int i = 0; i < counts.length; i++) {
      for (int j = 0; j < counts[i]; j++) {
        elements[targetPos++] = i + boundaries.min;
      }
    }
  }

  private Boundaries findBoundaries(int[] elements) {
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int element : elements) {
      if (element > MAX_VALUE_TO_SORT) {
        throw new IllegalArgumentException("Element " + element +
              " is greater than maximum " + MAX_VALUE_TO_SORT);
      }
      if (element < MIN_VALUE_TO_SORT) {
        throw new IllegalArgumentException("Element " + element +
              " is less than minimum " + MIN_VALUE_TO_SORT);
      }
      if (element > max) {
        max = element;
      }
      if (element < min) {
        min = element;
      }
    }
    return new Boundaries(min, max);
  }

  private static class Boundaries {
    private final int min;
    private final int max;

    public Boundaries(int min, int max) {
      this.min = min;
      this.max = max;
    }
  }

}Code-Sprache: Java (java)

Diese Variante hat nicht nur den Vorteil auch negative Zahlen zählen zu können, sondern belegt auch weniger zusätzlichen Speicher als die erste Variante, falls der Zahlenraum nicht bei 0 beginnt: Für Zahlen von 1.000 bis 2.000 beispielweise würde die erste Variante ein Hilfsarray mit 2.001 Feldern benötigen, Variante 2 hingegen nur 1.001 Felder.

Counting Sort Algorithmus (Allgemeine Form)

Mit Counting Sort können nicht nur Arrays von Primitiven (also bytes, ints, longs, doubles, etc.) sortiert werden, sondern auch Arrays von Objekten. Dazu müssen wir den Algorithmus, wie im folgenden Abschnitt beschrieben, erweitern.

Allgemeiner Algorithmus – Phase 1: Elemente zählen

Phase 1, die Zählphase bleibt quasi unverändert. Statt der Objekte selbst werden nun deren Schlüsselwerte (z. B. ermittelt durch eine getKey()-Methode) gezählt.

Das Array in der folgenden Grafik referenziert Objekte, deren Keys den Zahlen aus dem vorherigen Beispiel entsprechen, also 3, 7, 4, 6, 6, usw:

Entsprechend gleicht das daraus entstandene Histogramm dem aus dem ersten Beispiel:

Allgemeiner Algorithmus – Phase 2: Histogramm aggregieren

Jetzt wird der Unterschied zum vereinfachten Algorithmus deutlich: Wir wissen jetzt zwar, dass das Element mit dem Key 0 ein Mal vorkommt, können aber nicht einfach eine 0 in das zu sortierende Array schreiben – vielmehr benötigen wir das Objekt mit dem Key 0!

Um dies effizient zu finden, aggregieren wir zunächst die Werte im Histogramm. Dazu iterieren wir, beginnend bei Index 1, über das Hilfsarray und addieren zu jedem Feld den Wert des linken Nachbarfeldes.

An Position 1 addieren wir zur 0 den Wert von Feld 0, also die 1. Die Summe ist 1:

An Position 2 addieren wir zur 1 die 1 von Feld 1 und erhalten eine 2:

Zur 3 an Position 3 addieren wir die 2 von Feld 2 – die Summe ist 5:

Und so fahren wir fort, bis wir letztendlich zur 1 in Feld 9 die 14 von Feld 8 addieren und 15 erhalten:

Dieses aggregierte Histogramm sagt uns jetzt nicht mehr, wie oft die Objekte mit bestimmten Keys vorkommen, sondern an welche Position das letzte Element mit dem entsprechenden Key gehört. Die Position ist hierbei 1-basiert, nicht 0-basiert.

Beispielsweise gehört das Objekt mit Key 0 an Position 1 (entspricht Index 0 im Array), das Objekt mit Key 2 an Position 2 (Array-Index 1) und die drei Objekte mit Key 3 an die Positionen 3, 4 und 5 (Array-Indexe 2, 3, 4).

Allgemeiner Algorithmus – Phase 3: Objekte sortiert zurückschreiben

Um die Objekte zu sortieren, benötigen wir ein zusätzliches Array in der Größe des Eingabearrays:

Wir iterieren nun rückwärts über das zu sortierende Array und schreiben jedes Objekt im Zielarray an diejenige Position, die durch das Hilfsarray angezeigt wird. Wir dekrementieren den entsprechenden Wert im Hilfsarray um 1, um ggf. das nächste Objekt mit demselben Key ein Feld weiter links einzusortieren.

Beginnen wir im Eingabearray ganz rechts – mit dem Objekt mit dem Key 8. Im Hilfsarray steht an Position 8 der Wert 14. Wir dekrementieren den Wert auf 13 und kopieren das Objekt mit dem Key 8 in das Zielarray an Position 13 (zur Erinnerung: die Positionsangaben im Hilfsarray sind 1-basiert, deshalb schreiben wir auf Position 13, nicht 14).

Das zweite Objekt von rechts hat den Key 2. Im Hilfsarray steht an Position 2 der Wert 2. Wir dekrementieren den Wert im Hilfsarray auf 1 und kopieren das Objekt an die entsprechende Position im Zielarray:

Das nächste Objekt hat den Key 6. Im Hilfsarray steht an Position 6 die 11. Wir dekrementieren das Feld auf 10 und kopieren das Objekt nach Feld 10 im Zielarray:

Derselben Logik folgend kopieren wir das Objekt mit dem Key 9 an Position 14 des Zielarrays:

Es folgt eine weitere 6. Im Hilfsarray steht an Position 6 jetzt die 10 (nachdem wir zuvor dort die 11 dekrementiert hatten). Wir dekrementieren das Feld erneut auf 9 und kopieren das Objekt nach Position 9 im Zielarray, also links neben das andere Objekt mit dem Key 6:

Wir wiederholen diese Schritte für alle Elemente und kommen als letztes zum Objekt mit dem Key 3. An Feld 3 im Hilfsarray steht nun eine 3. Diese dekrementieren wir auf 2 und kopieren das Objekt auf Position 2, die letzte freie Position, des Zielarrays:

Die Objekte sind sortiert, der Algorithmus ist beendet.

Counting Sort Java Code Beispiel (Allgemeine Form)

Der folgende Code demonstriert die allgemeine Form von Counting Sort der Einfachheit halber an int-Primitiven. Die findMax()-Methode gleicht der im ersten Quellcode-Beispiel, ich habe sie daher hier nicht noch einmal mit abgedruckt.

public class CountingSortGeneral {

  public void sort(int[] elements) {
    int maxValue = findMax(elements);
    int[] counts = new int[maxValue + 1];

    // Phase 1: Count
    for (int element : elements) {
      counts[element]++;
    }

    // Phase 2: Aggregate
    for (int i = 1; i <= maxValue; i++) {
      counts[i] += counts[i - 1];
    }

    // Phase 3: Write to target array
    int[] target = new int[elements.length];
    for (int i = elements.length - 1; i >= 0; i--) {
      int element = elements[i];
      target[--counts[element]] = element;
    }

    // Copy target back to input array
    System.arraycopy(target, 0, elements, 0, elements.length);
  }

  [...]

}Code-Sprache: Java (java)

Du findest den Quellcode in der Klasse CountingSortGeneral im GitHub-Repository.

Counting Sort Zeitkomplexität

Die Zeitkomplexität von Counting Sort ist aufgrund des sehr einfachen Algorithmus leicht bestimmbar.

Sei n die Anzahl der zu sortierenden Elemente und k die Größe des Zahlenraums der Elemente.

Der Algorithmus enthält eine oder mehrere Schleifen, die bis n iterieren und eine Schleife, die bis k iteriert.

Konstante Faktoren sind für die Zeitkomplexität irrelevant; somit gilt:

Die Zeitkomplexität von Counting Sort beträgt: O(n + k)

Laufzeit des Java Counting Sort Beispiels

Das GitHub-Repository enthält das Programm UltimateTest, mit dem wir die Geschwindigkeit von Counting Sort und aller anderen Sortieralgorithmen dieser Artikelserie messen können.

Die folgende Tabelle zeigt die benötigte Zeit zum Sortieren von unsortierten sowie aufsteigend und absteigend vorsortierten Elementen für die jeweils angegebene Anzahl von Elementen n, die in diesen Messungen auch der Größe des Zahlenraums k entspricht:

Das vollständige Ergebnis findest du in der Datei Test_Results_Counting_Sort.log. Das folgende Diagramm stellt die Messwerte grafisch dar:

Es lässt sich folgendes ablesen:

• Vorsortierte Ausgangsfolgen mit einer halben Milliarde Elemente werden etwa neun mal so schnell sortiert wie unsortierte.
• Bei vorsortierten Ausgangsfolgen entsprechen die Messwerte der erwarteten linearen Zeitkomplexität O(n + k).
• Für unsortierte Ausgangsfolgen liegen die Messwerte etwas darüber: Bei einer Verdopplung der Arraygröße nimmt die benötigte Zeit etwa um Faktor 2,1 bis 2,2 zu.
• Absteigend sortierte Ausgangsfolgen werden minimal langsamer sortiert als aufsteigend vorsortierte.

Wenn Elemente nicht umsortiert, sondern gezählt und einmal komplett neu angeordnet werden, dürfte doch die Ausgangsreihenfolge keine Auswirkung auf die zum Sortieren benötigte Zeit haben!?

Mit dem Programm CountOperations können wir messen, wie viele Operationen für das Sortieren benötigt werden. Und tatsächlich bestätigt das Ergebnis (s. Datei CountOperations_Counting_Sort.log):

• Die Anzahl der Operationen ist unabhängig von der Ausgangsreihenfolge der Elemente.
• Die Anzahl der Operationen entspricht der erwarteten Zeitkomplexität O(n + k), steigt also linear mit der Anzahl der zu sortierenden Elememte und der Größe des Zahlenraums.

Wie kommen dann diese abweichenden Messwerte zustande? Erklärungen findest du in den folgenden Abschnitten.

Warum ist Counting Sort für vorsortierte Elemente schneller als für unsortierte Elemente?

Ein Hilfsarray mit einer halben Milliarde Elemente ist 2 GB groß. Wenn dessen Elemente in zufälliger Reihenfolge inkrementiert werden, muss beinahe für jedes Element eine neue Cache-Line (typischerweise 64 Byte groß) zwischen RAM und CPU-Cache ausgetauscht werden. Die Wahrscheinlichkeit, dass die benötigte Cache-Line im CPU-Cache liegt, ist umso niedriger, je größer das Array ist.

Wird das Array hingegen von vorne nach hinten (oder von hinten nach vorne) inkrementiert, können jeweils 16 aufeinanderfolgende int-Werte in einem 64-Byte-Block aus dem RAM geladen und wieder dorthin geschrieben werden.

Es wird nicht ganz eine Beschleunigung um Faktor 16 erreicht, aber zumindest eine um ca. Faktor neun.

Warum erreicht Counting Sort in der Praxis keine lineare Zeitkomplexität für unsortierte Ausgangsfolgen?

Je größer das zu sortierende Array, desto höher wird bei einem unsortierten Ausgangsarray das Verhältnis von Cache Misses zu Cache Hits beim Zugriff auf das Hilfsarray (denn die Größe des CPU-Caches bleibt ja gleich).

Bei einem doppelt so großen Array haben wir also nicht doppelt so viele Cache Misses, sondern etwas mehr als doppelt so viele. Dementsprechend erhöht sich die benötigte Zeit auch um etwas mehr als Faktor zwei.

Warum ist Counting Sort für aufsteigend sortierte Elemente schneller als für absteigend sortierte?

Bei aufsteigend sortierten Elementen werden diese nicht verändert, müssen also nicht zurück in den RAM geschrieben werden. Bei absteigend sortierten Elementen ändert sich jedes Element des Arrays, entsprechend muss das gesamte Array einmal zurück in den RAM geschrieben werden.

Weitere Eigenschaften von Counting Sort

In diesem Kapitel bestimmen wir die Platzkomplexität, die Stabilität und die Parallelisierbarkeit von Counting Sort.

Platzkomplexität von Counting Sort

Der vereinfachte Algorithmus benötigt ein zusätzliches Array der Größe k; es gilt entsprechend:

Die Platzkomplexität des vereinfachten Counting Sort Algorithmus ist: O(k)

Der allgemeine Algorithmus benötigt neben dem Hilfsarray der Größe k ein temporäres Zielarray der Größe n; somit gilt:

Die Platzkomplexität des allgemeinen Counting Sort Algorithmus ist: O(n + k)

Stabilität von Counting Sort

Die allgemeine Form des Counting Sort Algorithmus iteriert in Phase 3 von rechts nach links über das Eingabearray und kopiert dabei Objekte mit demselben Key ebenfalls von rechts nach links in das Ausgabearray. Somit gilt:

Counting Sort ist ein stabiler Sortieralgorithmus.

Parallelisierbarkeit von Counting Sort

Counting Sort kann parallelisiert werden, in dem das Eingabearray in so viele Partitionen geteilt wird, wie Prozessoren zur Verfügung stehen.

In Phase 1 zählt jeder Prozessor die Elemente „seiner“ Partition in einem separatem Hilfsarray.

In Phase 2 werden alle Hilfsarrays zu einem aufaddiert.

In Phase 3 kopiert jeder Prozessor die Elemente „seiner“ Partition ins Zielarray. Das Dekrementieren und Auslesen der Felder im Hilfsarray muss dabei atomar erfolgen.

Durch die Parallelisierung kann nicht mehr garantiert werden, dass Elemente mit gleichem Key in ihrer ursprünglichen Reihenfolge ins Zielarray kopiert werden.

Paralleles Counting Sort ist dementsprechend nicht stabil.

Zusammenfassung

Counting Sort ist ein sehr effizienter, stabiler Sortieralgorithmus mit einer Zeit- und Platzkomplexität von O(n + k).

Counting Sort wird hauptsächlich für kleine Zahlenräume eingesetzt. Im JDK beispielsweise für:

• byte-Arrays mit mehr als 64 Elementen (darunter wird Insertion Sort eingesetzt)
• short– oder char-Arrays mit mehr als 1.750 Elementen (darunter wird Insertion Sort oder Dual-Pivot Quicksort verwendet)

Bei Heapsort denkt jeder Java-Entwickler zunächst an den Java-Heap. Dass Heapsort damit nichts zu tun hat – und wie Heapsort genau funktioniert – zeigt dir dieser Artikel.

Im Detail erfährst du:

• Was ist ein Heap?
• Wie funktioniert der Heapsort-Algorithmus?
• Wie sieht der Quellcode von Heapsort aus?
• Wie bestimmt man die Zeitkomplexität von Heapsort?
• Was ist Bottom-Up-Heapsort und welche Vorteile hat es?
• Wie schlägt sich Heapsort im Vergleich zu Quicksort und Mergesort?

Was ist ein Heap?

Ein „Heap“ (deutsch: „Haufen“ oder „Halde“) bezeichnet einen Binärbaum, in dem jeder Knoten entweder größer/gleich seiner Kinder ist („Max Heap“) – oder kleiner/gleich seiner Kinder („Min Heap“).

Hier ist ein einfaches Beispiel für einen „Max Heap“:

Die 9 ist größer als die 8 und die 5; die 8 ist größer als die 7 und die 2; usw.

Ein Heap wird auf ein Array projiziert, indem dessen Elemente von oben links zeilenweise nach rechts unten in das Array übertragen werden:

Der oben gezeigte Heap sieht als Array also so aus:

Bei einem „Max Heap“ ist das größte Element immer ganz oben – in der Array-Form ist es folglich ganz links. Wie man diese Eigenschaft zum Sortieren verwenden kann, erfährst du im folgenden Abschnitt.

Heapsort-Algorithmus

Der Heapsort-Algorithmus besteht aus zwei Phasen: In der ersten Phase wird das zu sortierende Array in einen Max Heap umgewandelt. Und in der zweiten Phase wird jeweils das größte Element (also das an der Baumwurzel) entnommen und aus den restlichen Elementen erneut ein Max Heap hergestellt.

Die folgenden Abschnitte erklären die zwei Phasen im Detail anhand eines Beispiels:

Phase 1: Heap erstellen

Das zu sortierende Array muss zunächst in einen Heap umgewandelt werden. Dazu wird keine neue Datenstruktur angelegt, sondern die Zahlen werden innerhalb des Arrays so umsortiert, dass die oben beschriebene Heap-Struktur entsteht.

Wie dies geschieht erkläre ich in folgendem Beispiel anhand der aus den vorangegangenen Teilen der Artikelserie bekannten Zahlenfolge [3, 7, 1, 8, 2, 5, 9, 4, 6].

Diese „projizieren“ wir wie oben beschrieben auf einen Binärbaum. Dabei ist der Binärbaum keine separate Datenstruktur, sondern lediglich ein Gedankenkonstrukt – im Speicher liegen die Elemente ausschließlich in dem Array.

Dieser Baum entspricht noch keinem Max Heap. Dessen Definiton lautet ja, dass Eltern immer größer oder gleich ihrer Kinder sind.

Um einen Max Heap herzustellen, besuchen wir nun alle Elternknoten – rückwärts vom letzten bis zum ersten – und sorgen dafür, dass die Heap-Bedingung für den jeweiligen Knoten und die darunter erfüllt ist. Dies machen wir mit der sogenannten heapify()-Funktion.

Aufruf Nr. 1 der heapify-Funktion

Die heapify()-Funktion wird zuerst für den letzten Elternknoten aufgerufen. Elternknoten sind 3, 7, 1 und 8. Der letzte Elternknoten ist die 8. Die heapify()-Funktion prüft, ob die Kinder kleiner sind als der Elternknoten. 4 und 6 sind kleiner als 8. An diesem Elternknoten ist die Heap-Bedingung also erfüllt, und die heapify()-Funktion ist beendet.

Aufruf Nr. 2 der heapify-Funktion

Als zweites wird heapify() für den vorletzten Knoten aufgerufen: die 1. Die Kinder 5 und 9 sind beide größer als die 1, die Heap-Bedingung ist also verletzt. Um die Heap-Bedingung wiederherzustellen, tauschen wir nun das größere Kind mit dem Elternknoten, also die 9 mit der 1. Die heapify()-Funktion ist damit wieder beendet.

Aufruf Nr. 3 der heapify-Funktion

Nun wird heapify() auf der 7 aufgerufen. Kindknoten sind 8 und 2, nur die 8 ist größer als der Elternknoten. Wir tauschen also die 7 mit der 8:

Da der Kindknoten, den wir eben getauscht haben, selbst zwei Kinder hat, muss die heapify()-Funktion nun prüfen, ob die Heap-Bedingung für diesen Kindknoten noch erfüllt ist. In diesem Fall ist die 7 größer als 4 und 6, die Heap-Bedingung ist also erfüllt; die heapify()-Funktion ist damit beendet.

Aufruf Nr. 4 der heapify-Funktion

Jetzt sind wir bereits am Wurzelknoten mit dem Element 3 angekommen. Beide Kindknoten, 8 und 9 sind größer, wobei die 9 das größte Kind ist und daher mit dem Elternknoten vertauscht wird:

Wiederum hat der getauschte Kindknoten selbst Kinder, so dass wir die Heap-Bedingung an diesem Kindknoten überprüfen müssen. Die 5 ist größer als die 3, d. h. die Heap-Bedingung ist nicht erfüllt und muss durch Tauschen der 5 und der 3 wiederhergestellt werden:

Damit ist auch der vierte und letzte Aufruf der heapify()-Funktion beendet. Ein Max Heap ist entstanden:

Damit gehen wir über in Phase zwei des Heapsort-Algorithmus.

Phase 2: Sortieren des Arrays

In Phase 2 machen wir uns die Tatsache zunutze, dass das größte Element des Max Heaps immer an dessen Wurzel (bzw. im Array ganz links) steht.

Phase 2, Schritt 1: Root und letztes Element tauschen

Das Wurzelelement (die 9) tauschen wir nun mit dem letzten Element (der 6), so dass die 9 an ihrer finalen Position am Ende des Arrays steht (im Array blau markiert). Außerdem entfernen wir dieses Element gedanklich aus dem Baum (im Baum grau dargestellt):

Nachdem wir die 6 an die Wurzel des Baumes gesetzt haben, ist dieser kein Max Heap mehr. Im nächsten Schritt „reparieren“ wir den Heap.

Phase 2, Schritt 2: Heap-Bedingung wiederherstellen

Um die Heap-Bedingung wiederherzustellen, rufen wir die aus Phase 1 bekannte heapify()-Funktion auf dem Wurzelknoten auf. Wir vergleichen also die 6 mit ihren Kindern, 8 und 5. Die 8 ist größer, wir tauschen sie daher mit der 6:

Der getauschte Kindknoten hat wiederum zwei Kinder, die 7 und die 2. Die 7 ist größer als die 6, daher tauschen wir auch diese zwei Elemente:

Der getauschte Kindknoten hat auch noch ein Kind, die 4. Die 6 ist größer als die 4, die Heap-Bedingung ist an diesem Knoten also erfüllt, so dass die heapify()-Funktion beendet ist und wir wieder einen Max Heap haben:

Wiederholung der Schritte

Damit steht nun wieder die größte Zahl des verbleibenden Arrays, die 8, an erster Stelle. Diese wird wieder mit dem letzten Element des Baums vertauscht. Da wir den Baum um ein Element gekürzt haben, liegt das letzte Element des Baumes auf dem vorletzten Feld des Arrays:

Damit sind die letzten zwei Felder des Arrays sortiert.

An der Wurzel ist nun wieder die Heap-Bedingung verletzt, und wir reparieren den Baum, indem wir heapify() auf dem Wurzelelement aufrufen (das folgende Bild zeigt alle heapify-Schritte auf einmal).

Wir wiederholen den Prozess solange, bis der Baum nur noch ein Element enthält:

Dieses ist das kleinste und verbleibt am Anfang des Arrays. Der Algorithmus ist beendet, das Array ist sortiert:

Heapsort Java Code Beispiel

Im folgenden findest du den Quellcode von Heapsort.

Die sort()-Methode ruft zunächst buildHeap() auf, um den Heap initial aufzubauen.

In der darauf folgenden Schleife iteriert die Variable swapToPos rückwärts vom Ende des Arrays bis zum zweiten Feld. Im Schleifenkörper wird das erste Element mit demjenigen an der Position swapToPos vertauscht und danach die heapify()-Methode auf dem Sub-Array bis zur (ausschließlichen) Position swapToPos aufgerufen:

public class HeapSort {

  public void sort(int[] elements) {
    buildHeap(elements);

    for (int swapToPos = elements.length - 1; swapToPos > 0; swapToPos--) {
      // Move root to end
      ArrayUtils.swap(elements, 0, swapToPos);

      // Fix remaining heap
      heapify(elements, swapToPos, 0);
    }
  }

  [...]
}Code-Sprache: Java (java)

Die buildHeap()-Methode ruft für jeden Elternknoten – beginnend beim letzten – heapify() auf und übergibt dieser Methode das Array, die Länge des Sub-Arrays, das den Heap darstellt und die Position des Elternknotens, an dem heapify() starten soll:

void buildHeap(int[] elements) {
  // "Find" the last parent node
  int lastParentNode = elements.length / 2 - 1;

  // Now heapify it from here on backwards
  for (int i = lastParentNode; i >= 0; i--) {
    heapify(elements, elements.length, i);
  }
}Code-Sprache: Java (java)

Die heapify()-Methode prüft, ob ein Kindknoten größer ist als der Elternknoten. Wenn das der Fall ist, wird das Elternelement mit dem größeren Kindelement vertauscht, und der Prozess wird auf dem Kindknoten wiederholt.

(Hier könnte man auch mit Rekursion arbeiten, was sich allerdings negativ auf die Platzkomplexität auswirken würde.)

void heapify(int[] heap, int length, int parentPos) {
  while (true) {
    int leftChildPos = parentPos * 2 + 1;
    int rightChildPos = parentPos * 2 + 2;

    // Find the largest element
    int largestPos = parentPos;
    if (leftChildPos < length && heap[leftChildPos] > heap[largestPos]) {
      largestPos = leftChildPos;
    }
    if (rightChildPos < length && heap[rightChildPos] > heap[largestPos]) {
      largestPos = rightChildPos;
    }

    // largestPos is now either parentPos, leftChildPos or rightChildPos.
    // If it's the parent, we're done
    if (largestPos == parentPos) {
      break;
    }

    // If it's not the parent, then switch!
    ArrayUtils.swap(heap, parentPos, largestPos);

    // ... and fix again starting at the child we moved the parent to
    parentPos = largestPos;
  }
}Code-Sprache: Java (java)

Du findest den Quellcode in der Klasse HeapSort im GitHub-Repository. Diese unterscheidet sich leicht von der hier abgedruckten Klasse: Die Klasse im Repository implementiert das Interface SortAlgorithm, um innerhalb des Testframeworks austauschbar zu sein.

Heapsort Zeitkomplexität

Klicke auf den folgenden Link für eine Einführung in „Zeitkomplexität“ und „O-Notation“ (mit Beispielen und Diagrammen).

Zeitkomplexität der heapify()-Methode

Fangen wir mit der heapify()-Funktion an, da diese auch für den initialen Aufbau des Heaps benötigt wird.

In der heapify()-Funktion hangeln wir uns einmal von oben nach unten durch den Baum. Die Höhe eines Binärbaumes (die Wurzel wird nicht mitgezählt) der Größe n ist maximal log₂ n, d. h. bei einer Verdopplung der Anzahl Elemente wird der Baum lediglich eine Ebene tiefer:

Die Komplexität für die heapify()-Funktion ist entsprechend O(log n).

Zeitkomplexität der buildHeap()-Methode

Für den erstmaligen Aufbau des Heaps wird für jeden Elternknoten – rückwärts, beginnend beim letzten Knoten und endend an der Baumwurzel – die heapify()-Methode aufgerufen.

Ein Heap der Größe n hat n/2 (abgerundet) Elternknoten:

Da die Komplexität der heapify()-Methode, wie oben gezeigt, O(log n) ist, ist die Komplexität für die buildHeap()-Methode also maximal* O(n log n).

* Im übernächsten Abschnitt werde ich zeigen, dass die Zeitkomplexität der buildHeap()-Methode sogar O(n) ist. Da dies an der Gesamt-Zeitkomplexität nichts ändert, ist es nicht zwingend erforderlich, diese detailliertere Analyse durchzuführen.

Gesamt-Zeitkomplexität von Heapsort

Die heapify()-Funktion wird n-1 mal aufgerufen. Die Gesamtkomplexität für das Reparieren des Heaps ist also ebenfalls O(n log n).

Beide Teilalgorithmen haben also die gleiche Zeitkomplexität. Es gilt somit:

Die Zeitkomplexität von Heapsort beträgt: O(n log n)

Zeitkomplexität für den Aufbau des Heaps – genauer analysiert

Dieser Abschnitt ist sehr mathematisch und für die Herleitung der Zeitkomplexität des Gesamtalgorithmus (die wir ja bereits abgeschlossen haben) nicht zwingend erforderlich. Du kannst diesen Abschnitt daher auch überspringen.

Wir haben oben festgestellt, dass die buildHeap()-Methode für jeden Elternknoten heapify() aufruft. Was wir bisher nicht berücksichtigt haben ist, dass die Tiefe der Teilbäume, auf denen heapify() aufgerufen wird, unterschiedlich ist. Folgende Grafik soll das verdeutlichen (d steht für die Tiefe der Teilbäume):

Die heapify()-Methode wird also maximal für n/4 Bäume der Tiefe 1 aufgerufen, für n/8 Bäume der Tiefe 2, für n/16 Bäume der Tiefe 3, usw.

Die maximale Anzahl der Tauschoperationen in der heapify()-Methode entspricht der Tiefe des Teilbaums, auf der diese aufgerufen wird.

Die maximale Anzahl der Tauschoperationen S_max (S steht für „Swap“) für den Aufbau des Heaps beträgt somit:

S_max = n/4 · 1 + n/8 · 2 + n/16 · 3 + n/32 · 4 + …

Wenn wir beide Seiten des Terms mit 2 multiplizieren, erhalten wir:

2 · S_max = n/2 · 1 + n/4 · 2 + n/8 · 3 + n/16 · 4 + …

Legen wir einmal beide Terme übereinander:

Beide Terme enthalten n/4, n/8, n/16 usw. mit jeweils einem um die Konstante 1 unterschiedlichen Faktor. Wenn wir die Terme subtrahieren, erhalten wir:

2 · S_max – S_max = n/2 · 1 + n/4 · (2 – 1) + n/8 · (3 – 2) + n/16 · (4 – 3) + …

Das lässt sich vereinfachen zu:

S_max = n/2 + n/4 + n/8 + n/16 + …

Bzw:

S_max = n · (1/2 + 1/4 + 1/8 + 1/16 + …)

Der Term 1/2 + 1/4 + 1/8 + 1/16 + … nähert sich an 1 an, wie folgende Darstellung zeigt:

Somit lässt sich die Formel abschließend vereinfachen auf:

S_max ≤ n

Damit haben wir gezeigt, dass der Aufwand für den Aufbau des Heaps linear ist, die Zeitkomplexität also O(n) beträgt.

Die oben genannte Gesamtkomplexität von O(n log n) ändert sich durch die niedrigere Komplexitätsklasse eines Teilalgorithmus nicht.

Laufzeit des Java Heapsort Beispiels

Mit der Klasse UltimateSort kann die Laufzeit verschiedener Sortieralgorithmen für unterschiedliche Eingabegrößen ermittelt werden.

Die folgende Tabelle zeigt die Mediane der Laufzeiten für das Sortieren von zufällig angeordneten, sowie aufsteigend und absteigend vorsortierten Elementen, nach 50 Wiederholungen (dies ist der Übersicht halber nur ein Auszug; das vollständige Ergebnis findest du hier):

Hier die vollständigen Messwerte als Diagramm:

Es lässt sich gut sehen:

• Bei Verdopplung der Eingabemenge dauert das Sortieren etwas mehr als doppelt so lange; dies entspricht der erwarteten quasi-linearen Laufzeit O(n log n).
• Für vorsortierte Eingabedaten ist Heapsort etwa drei mal so schnell wie für unsortierte.
• Aufsteigend sortierte Eingabedaten werden etwa gleich schnell sortiert wie absteigend sortierte.

Warum ist Heapsort für vorsortierte Eingabedaten schneller?

Um dieser Frage auf den Grund zu gehen, verwende ich das Programm CountOperations, um die Anzahl von Vergleichs-, Lese- und Schreiboperationen von Heapsort für unsortierte, aufsteigend und absteigend sortierte Daten, für die jeweiligen Phasen, zu messen.

Das Ergebnis findest du in der Datei CountOperations_Heapsort.log. Die Erkenntnisse aus dem Test sind:

• Wenn die Eingabedaten absteigend sortiert sind, gibt es in Phase 1 nur etwa halb so viele Vergleiche wie bei unsortierten oder aufsteigend sortierten Daten; außerdem gibt es keine Tauschoperationen. Dies liegt daran, dass ein absteigend sortiertes Array bereits einem Max Heap entspricht.
• Aufsteigend sortierte Eingabedaten hingegeben entsprechen einem Min Heap. Dieser muss in der buildHeap()-Phase komplett umgedreht werden, deshalb haben wir in diesem Fall etwa ein Drittel mehr Tauschoperationen als bei zufällig angeordneten Daten, in denen die Heap-Bedingung bereits an einigen Teilbäumen erfüllt ist.
• In Phase 2 unterscheidet sich die Anzahl der Operationen nur minimal.

Wie lässt sich dann erklären, dass Heapsort sowohl für aufsteigend als auch für absteigend vorsortierte Eingabedaten etwa drei mal so schnell ist?

Die Antwort finden wir in der sogenannten Sprungvorhersage (englisch „branch prediction“).

Bei vorsortierten Eingabedaten führen die Vergleichsoperationen immer wieder zum selben Ergebnis. Wenn die Sprungvorhersage nun davon ausgeht, dass die Vergleiche auch in Zukunft zum selben Ergebnis führen, können die Befehls-Pipelines der CPU voll ausgenutzt werden.

Bei unsortierten Eingabedaten hingegen kann keine zuverlässige Aussage über zukünftige Vergleichsergebnisse getroffen werden. Entsprechend muss die Befehls-Pipeline häufig gelöscht und wieder neu gefüllt werden.

Bottom-Up-Heapsort

Bottom-Up-Heapsort ist eine Variante, bei die heapify()-Methode durch geschickte Optimierung mit weniger Vergleichen auskommt. Dies ist vorteilhaft, wenn nicht beispielsweise int-Primitive verglichen werden, sondern Objekte mit einer aufwändigen compareTo()-Funktion.

Im regulären heapify() führen wir von oben nach unten an jedem Knoten zwei Vergleiche aus, um das größte von drei Elementen zu finden:

1. Elternknoten mit linkem Kind
2. Der größere Knoten aus dem ersten Vergleich mit dem zweiten Kind

Bottom-Up-Heapsort Algorithmus

Bottom-Up-Heapsort hingegen vergleicht nur die zwei Kinder miteinander und folgt dem jeweils größeren Kind bis zum Ende des Baumes („top-down“). Von dort geht der Algorithmus wieder zurück Richtung Baumwurzel („bottom-up“) und sucht das erste Element, das größer als die Wurzel ist. Von hier ab werden alle Elemente jeweils um eine Position Richtung Wurzel verschoben, und das Wurzelelement wird auf das freigewordene Feld gesetzt.

Das folgendes Beispiel soll das Verständnis erleichern.

Bottom-Up-Heapsort Beispiel

In folgendem Beispiel werden die 9 und 4 verglichen, dann die Kinder der 9 – die 8 und die 6, und zuletzt die Kinder der 8 – die 7 und die 3:

Wir erreichen auf diese Weise die 7 und vergleichen diese mit der Baumwurzel, der 5:

Die 5 ist kleiner als die 7. Das bedeutet, dass das Wurzelelement bis ganz nach unten durchgereicht werden muss:

Im Endeffekt führt dies zum gleichen Ergebnis wie das reguläre heapify().

Bottom-Up-Heapsort macht sich zunutze, dass das Wurzelelement in der Regel sehr weit nach unten geschoben wird, da dieses nach jeder Iteration vom Ende des Baumes kommt und daher relativ klein ist.

Somit sind weniger Vergleiche nötig, wenn einmal bis ganz nach unten verglichen wird und dann wieder ein kurzes Stück nach oben, als wenn von oben bis nach ganz unten jeweils zwei Vergleiche durchgeführt werden:

Bottom-Up-Heapsort Quellcode

Die Klasse BottomUpHeapsort erbt von Heapsort und überschreibt lediglich deren heapify()-Methode mit der folgenden:

@Override
void heapify(int[] heap, int length, int rootPos) {
  int leafPos = findLeaf(heap, length, rootPos);
  int nodePos = findTargetNodeBottomUp(heap, rootPos, leafPos);

  if (rootPos == nodePos) return;

  // Move all elements starting at nodePos to parent, move root to nodePos
  int nodeValue = heap[nodePos];
  heap[nodePos] = heap[rootPos];

  while (nodePos > rootPos) {
    int parentPos = getParentPos(nodePos);
    int parentValue = heap[parentPos];
    heap[parentPos] = nodeValue;
    nodePos = getParentPos(nodePos);
    nodeValue = parentValue;
  }
}Code-Sprache: Java (java)

Die findLeaf()-Methode vergleicht jeweils zwei Kinder und folgt dem jeweils größeren, bis das Ende des Baumes erreicht ist (bzw. ein Knoten, der nur noch ein Kind enthält):

int findLeaf(int[] heap, int length, int rootPos) {
  int pos = rootPos;
  int leftChildPos = pos * 2 + 1;
  int rightChildPos = pos * 2 + 2;

  // Two child exist?
  while (rightChildPos < length) {
    if (heap[rightChildPos] > heap[leftChildPos]) {
      pos = rightChildPos;
    } else {
      pos = leftChildPos;
    }
    leftChildPos = pos * 2 + 1;
    rightChildPos = pos * 2 + 2;
  }

  // One child exist?
  if (leftChildPos < length) {
    pos = leftChildPos;
  }

  return pos;
}Code-Sprache: Java (java)

Die Methode findTargetNodeBottomUp() sucht von unten nach oben das erste Element, das nicht kleiner als der Wurzelknoten ist:

int findTargetNodeBottomUp(int[] heap, int rootPos, int leafPos) {
  int parent = heap[rootPos];
  while (leafPos != rootPos && heap[leafPos] < parent) {
    leafPos = getParentPos(leafPos);
  }
  return leafPos;
}Code-Sprache: Java (java)

Und zuletzt die getParentPos()-Methode:

int getParentPos(int pos) {
  return (pos - 1) / 2;
}Code-Sprache: Java (java)

Bottom-Up-Heapsort Performance

Die Performance von Bottom-Up-Heapsort kann ebenfalls mit dem UltimateTest gemessen werden. Die Messwerte findest Du in ebenfalls in UltimateTest_Heapsort.log. Das folgende Diagramm zeigt die Laufzeiten von Bottom-Up-Heapsort im Vergleich mit dem regulären Heapsort:

Wie man sieht benötigt Bottom-Up-Heapsort für unsortierte Daten bis zu doppelt so lange wie das reguläre Heapsort, während es bei sortierten Daten in etwa gleich schnell ist.

Bevor wir der Ursache dafür auf den Grund gehen, schauen wir uns zunächst einen kleineren Ausschnitt des Diagramms an:

Bottom-Up-Heapsort wird also erst ab etwa zwei Millionen Elementen langsamer als das reguläre Heapsort.

Worin liegt die Ursache?

Das Ergebnis des oben erwähnten CountOperations-Programms zeigt, dass Bottom-Up-Heapsort weniger Vergleichs-, Lese und Schreiboperationen benötigt als das reguläre Heapsort – und zwar unabhängig von der Anzahl der zu sortierenden Elemente.

Warum ist es dennoch langsamer?

Bottom-up-Heapsort basiert auf der Annahme, dass das Wurzelelement immer bis zur Blattebene verschoben wird. Diese Annahme kann sich auch die Sprungvorhersage der CPU zunutze machen und damit diesen Vorteil relativieren.

Des weiteren müssen wir bei Bottom-Up-Heapsort zweimal durch den Baum gehen: einmal von oben nach unten und einmal zurück nach oben. Dies wirkt sich zwar nicht negativ auf die Anzahl der Operation aus, wohl aber auf den Zugriff auf den Hauptspeicher!

Denn während beim einmaligen Traversieren des Baumes Speicherseiten nur einmal vom Hauptspeicher in den CPU-Cache geladen werden müssen, sind bei entsprechend großen Bäumen auf dem Rückweg die meisten Speicherseiten bereits wieder aus dem Cache entfernt und müssen erneut gelesen werden.

Daher nähern wir uns bei hinreichend großen Bäumen an den Geschwindigkeitsfaktor zwei an.

Bottom-Up-Heapsort mit teuren Vergleichsoperationen

Bottom-Up-Heapsort optimiert dahingehend, dass weniger Vergleiche ausgeführt werden müssen. Bei int-Primitiven fallen Vergleiche nicht ins Gewicht, daher kann Bottom-Up-Heapsort hier seine Vorteile nicht ausspielen.

Ich habe daher einen weiteren Test ausgeführt, indem ich die Vergleichsoperationen künstlich verteuert habe. Du findest die angepassten Algorithmen in den Klassen HeapsortSlowComparisons und BottomUpHeapsortSlowComparisons im GitHub-Repository.

Bottom-Up-Heapsort schneidet bei diesem Vergleich deutlich besser ab:

Weitere Eigenschaften von Heapsort

Im folgenden werden die Platzkomplexität von Heapsort, dessen Stabilität und Parallelisierbarkeit betrachtet.

Platzkomplexität von Heapsort

Heapsort ist ein In-Place-Sortierverfahren, d. h. außer für Schleifen- und Hilfsvariablen wird kein zusätzlicher Speicherplatz benötigt. Die Anzahl dieser Variablen ist immer gleich, egal ob wir zehn Elemente sortieren oder zehn Millionen. Daher gilt:

Die Platzkomplexität von Heapsort ist: O(1)

Stabilität von Heapsort

Es lassen sich sehr leicht Beispiele konstruieren, die zeigen, dass Elemente mit gleichem Key ihre Position zueinander ändern können:

Beispiel 1

Wenn wir das Array [3, 2a, 2b, 1] mit Heapsort sortieren, sehen die Schritte wie folgt aus (2a und 2b stellen zwei Elemente mit demselben Key dar; hellgelb markiert sind die Elemente, die im nächsten Schritt vertauscht werden; blau markiert sind fertig sortierte Elemente):

An dieser Stelle können wir abbrechen, denn wir sehen bereits jetzt, dass das Ziel-Array auf [2a, 3] enden wird, d. h. die 2a wird rechts neben der 2b im Ziel-Array landen.

Algorithmus anpassen?

Im zweiten Schritt haben wir entsprechend des Algorithmus die 1 mit der 2a vertauscht. Könnten wir den Algorithmus so ändern, dass bei Kindknoten mit gleichem Key, nicht mit dem linken Kind getauscht wird, sondern mit dem rechten?

In dem Fall würde das Array oben stabil sortiert werden, da die 1 nicht mit der 2a, sondern mit der 2b getauscht werden würde, und daraufhin die 2b an der vorletzte Stelle des Arrays landen würde.

Beispiel 2

Versuchen wir das einmal mit einem anderen Eingabearray, mit [4, 3, 2a, 2b, 1]:

Nach Schritt 2 wurde der Stand erreicht, den wir zuvor als Ausgangsarray hatten, wobei jedoch 2a und 2b ihre Positionen getauscht haben. Wenn wir im nächsten Schritt die 1 nun mit dem rechten Kind tauschen, passiert das gleiche wie oben: die 2a landet zuerst im Ziel-Array und damit rechts von der 2b.

Wir haben für beide Algorithmus-Varianten Gegenbeispiele gezeigt und können daher feststellen:

Heapsort ist kein stabiles Sortierverfahren.

Parallelisierbarkeit von Heapsort

Bei Heapsort wird das gesamte Array ständig verändert, so dass es keine naheliegenden Lösungen gibt den Algororithmus zu parallelisieren.

Vergleich von Heapsort mit anderen effizienten Sortierverfahren

Im folgenden Diagramm siehst du die Ergebnisse des UltimateTests von Heapsort im Vergleich zu den Messwerten von Quicksort und Mergesort (im englischen in der Regel „Merge Sort“) aus den jeweiligen Artikeln:

Heapsort ist bei zufällig verteilten Eingabedaten um Faktor 3,6 langsamer als Quicksort und um Faktor 2,4 langsamer als Merge Sort. Bei sortierten Daten ist Heapsort um Faktor 8 bis 9 langsamer als Quicksort und um Faktor 2 langsamer als Merge Sort.

Heapsort vs. Quicksort

Wie im vorangegangenen Abschnitt gezeigt, ist Quicksort in der Regel deutlich schneller als Heapsort.

Aufgrund der worst-case Zeitkomplexität bei Quicksort von O(n²) wird in der Praxis in manchen Fällen Heapsort gegenüber Quicksort vorgezogen.

Wie im Artikel über Quicksort gezeigt, ist bei geeigneter Wahl des Pivot-Elements der Eintritt des worst cases unwahrscheinlich. Dennoch besteht ein gewisses Risiko, welches ein potentieller Angreifer mit ausreichend Kenntnis der verwendeten Quicksort-Implementierung ausnutzen kann, um eine Anwendung mit entsprechend präparierten Eingabedaten in die Knie zu zwingen.

Heapsort vs. Mergesort

Auch Mergesort ist in der Regel schneller als Heapsort. Außerdem ist Mergesort im Gegensatz zu Heapsort stabil.

Heapsort hat gegenüber Mergesort den Vorteil, dass es keinen zusätzlichen Speicherbedarf hat, während Mergesort zusätzlichen Speicher in der Größenordnung O(n) benötigt.

Zusammenfassung

Heapsort ist ein effizienter, nicht stabiler Sortieralgorithmus mit einer Zeitkomplexität von O(n log n) im average, best und worst case.

Heapsort ist deutlich langsamer als Quicksort und Mergesort, weshalb man Heapsort in der Praxis seltener antrifft.

Weitere Sortieralgorithmen findest du in der Übersicht aller Sortieralgorithmen und ihrer Eigenschaften im ersten Teil der Artikelserie.

In diesem Artikel

• lernst Du, wie Mergesort (oft auch „Merge Sort“) funktioniert,
• findest Du den Quellcode von Mergesort
• und du erfährst, wie man die Zeitkomplexität von Mergesort bestimmt, und zwar ohne komplizierte Mathematik.

Dies ist nach Quicksort der zweite effiziente Sortieralgorithmus aus der Artikelserie über Sortieralgorithmen.

Mergesort Algorithmus

Mergesort funktioniert nach dem „Teile-und-herrsche“-Prinzip („divide and conquer“):

Zunächst werden die zu sortierenden Elemente in zwei Hälften geteilt. Die entstandenen Sub-Arrays werden dann wieder geteilt – und wieder, bis Sub-Arrays der Länge 1 entstanden sind:

Nun werden in umgekehrter Richtung jeweils zwei Teil-Arrays so zusammengeführt („gemerged“), dass jeweils ein sortiertes Array entsteht. Im letzten Schritt werden die zwei Hälften des ursprünglichen Arrays gemerged, so dass dieses letztendlich sortiert ist.

Wie genau zwei Teil-Arrays zu einem gemerged werden, wirst du in folgendem Beispiel sehen.

Mergesort Merge Beispiel

Das Mergen an sich funktioniert ganz einfach: Für beide Arrays wird ein Merge-Index festgelegt, der zunächst auf das erste Element des jeweiligen Arrays zeigt. Am einfachsten lässt sich das an einem Beispiel zeigen (die Pfeile stellen den jeweiligen Merge-Index dar):

Die Elemente, auf die die Merge-Zeiger zeigen, werden verglichen. Das kleinere von beiden (im Beispiel die 1) wird an ein neues Arrays angehängt und der Zeiger, der auf dieses Element gezeigt hat, wird um ein Feld nach rechts verschoben:

Jetzt werden erneut die Elemente über den Zeigern verglichen. Dieses mal ist die 2 kleiner als die 4, somit wird die 2 an das neue Array angehängt:

Jetzt liegen die Zeiger auf der 3 und der 4. Die 3 ist kleiner und wird an das Ziel-Array angehängt:

Jetzt ist die 4 am kleinsten:

Jetzt die 5:

Und im letzten Schritt bleibt die 6 übrig und wird an das neue Array angehängt:

Die zwei sortierten Teil-Arrays wurden durch das Mergen zu einem sortierten Gesamt-Array.

Mergesort Beispiel

Hier noch mal ein Beispiel für den Gesamt-Algorithmus. Sortiert werden soll das aus den anderen Teilen der Serie bekannte Array [3, 7, 1, 8, 2, 5, 9, 4, 6].

Dieses wird zunächst solange geteilt, bis Arrays der Länge 1 entstehen. Die Anordnung der Elemente ändert sich dabei nicht:

Jetzt werden die Teil-Arrays in umgekehrter Richtung nach dem oben beschriebenen Prinzip gemerged. Im ersten Schritt werden die 4 und die 6 zum Teil-Array [4, 6] zusammengefasst:

Als nächstes werden die 3 und die 7 zum Teil-Array [3, 7] gemerged, 1 und 8 zum Teil-Array [1, 8], die 2 und die 5 werden zu [2, 5]. Bis hierhin standen die gemergeten Elemente zufällig in der richtigen Reihenfolge zueinander und wurden daher nicht verschoben.

Das ändert sich jetzt: Die 9 wird mit dem Teil-Array [4, 6] gemerged – dabei wandert die 9 ans Ende des neuen Teil-Arrays [4, 6, 9]:

[3, 7] und [1, 8] werden nun zu [1, 3, 7, 8] gemerged. [2, 5] und [4, 6, 9] werden zu [2, 4, 5, 6, 9]:

Und im letzten Schritt werden die zwei Teil-Arrays [1, 3, 7, 8] und [2, 4, 5, 6, 9] zum Endergebnis zusammengeführt:

Am Ende erhalten wir das sortierte Array [1, 2, 3, 4, 5, 6, 7, 8, 9]. Das folgende Diagramm zeigt alle Merge-Schritte zusammengefasst in einer Übersicht:

Mergesort Java Quellcode

Im folgenden findest du die einfachste Implementierung von Mergesort.

Zunächst ruft die Methode sort() die Methode mergeSort() auf und übergibt dieser das Array sowie dessen Start- und Endpositionen.

mergeSort() prüft, ob es für ein Teil-Array der Länge 1 aufgerufen wurde und, wenn ja, gibt eine Kopie dieses Teil-Arrays zurück.

Anderfalls wird das Array geteilt, und mergeSort() wird rekursiv für beide Teile aufgerufen. Die beiden Aufrufe liefern jeweils ein sortiertes Array zurück. Diese werden anschließend durch Aufruf der merge()-Methode zusammengeführt, und mergeSort() gibt dieses zusammengeführte, sortierte Array zurück.

Abschließend kopiert die sort()-Methode das sortierte Array zurück in das Eingabe-Array. Man könnte das sortierte Array auch direkt zurückgeben – das wäre allerdings inkompatibel zum Test-Framework.

public class MergeSort {
  public void sort(int[] elements) {
    int length = elements.length;
    int[] sorted = mergeSort(elements, 0, length - 1);
    System.arraycopy(sorted, 0, elements, 0, length);
  }

  private int[] mergeSort(int[] elements, int left, int right) {
    // End of recursion reached?
    if (left == right) return new int[]{elements[left]};

    int middle = left + (right - left) / 2;
    int[] leftArray = mergeSort(elements, left, middle);
    int[] rightArray = mergeSort(elements, middle + 1, right);
    return merge(leftArray, rightArray);
  }

  int[] merge(int[] leftArray, int[] rightArray) {
    int leftLen = leftArray.length;
    int rightLen = rightArray.length;

    int[] target = new int[leftLen + rightLen];
    int targetPos = 0;
    int leftPos = 0;
    int rightPos = 0;

    // As long as both arrays contain elements...
    while (leftPos < leftLen && rightPos < rightLen) {
      // Which one is smaller?
      int leftValue = leftArray[leftPos];
      int rightValue = rightArray[rightPos];
      if (leftValue <= rightValue) {
        target[targetPos++] = leftValue;
        leftPos++;
      } else {
        target[targetPos++] = rightValue;
        rightPos++;
      }
    }
    // Copy the rest
    while (leftPos < leftLen) {
      target[targetPos++] = leftArray[leftPos++];
    }
    while (rightPos < rightLen) {
      target[targetPos++] = rightArray[rightPos++];
    }
    return target;
  }
}Code-Sprache: Java (java)

Den Quellcode findest Du hier im GitHub-Repository.

Mergesort Zeitkomplexität

(Die Begriffe „Zeitkomplexität“ und „O-Notation“ werden in diesem Artikel anhand von Beispielen und Diagrammen erklärt.)

Wir bezeichnen die Anzahl der Elemente mit n.

Da wir die (Sub-)Arrays immer wieder in zwei gleich große Teile aufteilen, benötigen wir bei einer Verdopplung der Anzahl der Elemente n nur eine einzige zusätzliche Stufe von Teilungen d. Folgendes Diagramm demonstriert, dass bei vier Elementen zwei Teilungsstufen benötigt werden und bei acht Elementen nur eine mehr:

Somit beträgt die Anzahl der Teilungsstufen log₂ n.

Auf jeder Merge-Stufe müssen wir insgesamt n Elemente zusammenführen (auf der ersten n × 1, auf der zweiten Stufe n/2 × 2, auf der dritten Stufe n/4 × 4, usw.):

Der Merge-Vorgang enthält keine verschachtelten Schleifen, erfolgt also mit linearem Aufwand: Bei Verdoppelung der Array-Größe verdoppelt sich auch der Merge-Aufwand. Der Gesamtaufwand ist daher auf allen Merge-Stufen gleich.

Wir haben also n Elemente mal log₂ n Teilungs- und Merge-Stufen. Damit gilt:

Die Zeitkomplexität von Mergesort beträgt: O(n log n)

Und zwar unabhängig davon, ob die Eingabeelemente vorsortiert sind oder nicht. Mergesort ist also für sortierte Eingabeelemente nicht schneller als für zufällig angeordnete.

Laufzeit des Java Mergesort-Beispiels

Genug der Theorie! Das Testprogramm UltimateTest misst die Laufzeit von Mergesort (und aller anderen Sortieralgorithmen dieser Artikelserie). Es geht dazu wie folgt vor:

• Sortiert werden Arrays der Länge 1.024, 2.048, 4.096, usw… bis maximal 536.870.912 (= 2²⁹) oder so lange, bis ein Sortiervorgang länger als 20 Sekunden dauert.
• Sortiert werden mit Zufallszahlen gefüllte Arrays, sowie aufsteigend und absteigend vorsortierte Zahlenfolgen.
• In zwei WarmUp-Runden wird dem HotSpot-Compiler ausreichend Zeit gegeben, den Code zu optimieren.

Die Tests werden solange wiederholt, bis der Prozess abgebrochen wird. Hier ist das Ergebnis für Mergesort nach 50 Wiederholungen (dies ist der Übersicht halber nur ein Auszug; das vollständige Ergebnis findest du hier):

Hier die Messwerte als Diagramm:

Es lässt sich sehr gut sehen:

• Die Laufzeit wächst in allen Fällen etwa linear mit der Anzahl der Elemente, entspricht also dem erwarteten quasi-linearen Aufwand – O(n log n).
• Für vorsortierte Elemente ist Mergesort etwa dreimal schneller als für unsortierte Elemente.
• Für absteigend vorsortierte Elemente benötigt Mergesort etwas mehr Zeit als für aufsteigend sortierte Elemente.

Wie lassen sich diese Unterschiede erklären?

Mit dem Programm CountOperations können wir die Anzahl der Operationen für die verschiedenen Fälle messen lassen. Die Anzahl der Schreiboperationen ist für alle Fälle gleich, da der Merge-Prozess – unabhängig von der Vorsortierung – alle Elemente der Teil-Arrays in ein neues Array kopiert.

Die Anzahl der Vergleiche unterscheidet sich jedoch; du findest sie in der folgenden Tabelle gegenübergestellt (das vollständige Ergebnis findest Du in der Datei CountOperations_Mergesort.log):

Laufzeitunterschied aufsteigend / absteigend sortierte Elemente

Der Unterschied zwischen aufsteigend und absteigend sortierten Elementen entspricht in etwa dem gemessenen Zeitunterschied. Der Grund für den Unterschied liegt in dieser Code-Zeile:

while (leftPos < leftLen && rightPos < rightLen)Code-Sprache: Java (java)

Bei aufsteigend sortierten Elementen werden zuerst alle Elemente des linken Teil-Arrays in das Ziel-Array kopiert, so dass leftPos < leftLen als erstes false ergibt und danach der rechte Term nicht mehr ausgewertet werden muss.

Bei absteigend sortierten Elementen werden zuerst alle Elemente des rechten Teil-Arrays kopiert, so dass rightPos < rightLen zuerst false ergibt. Da dieser Vergleich nach leftPos < leftLen ausgeführt wird, wird bei absteigend sortierten Elementen in jeder Merge-Runde einmal mehr der linke Vergleich leftPos < leftLen durchgeführt.

Würden wir die Zeile ändern in

while (rightPos < rightLen && leftPos < leftLen)Code-Sprache: Java (java)

… dann würde sich das Laufzeitverhältnis das Sortierens von aufsteigend zu absteigend vorsortierten Elementen entsprechend umkehren.

Laufzeitunterschied sortierte / unsortierte Elemente

Mergesort ist für vorsortierte Elemente etwa drei mal schneller als für unsortierte Elemente. Die Anzahl der Vergleichsoperationen unterscheidet sich allerdings nur um etwa ein Drittel.

Warum führt ein Drittel weniger Operationen zu dreimal schnellerer Abarbeitung?

Die Ursache liegt in der Sprungvorhersage (englisch „branch prediction“): Wenn die Elemente sortiert sind, dann sind die Resultate der Vergleiche in den Loop- und Branch-Statements

while (leftPos < leftLen && rightPos < rightLen)

und

if (leftValue <= rightValue)

bis zum Ende eines Merge-Vorgangs immer gleich. Somit kann die Befehls-Pipeline der CPU während des Mergens voll ausgenutzt werden.

Bei unsortierten Eingabedaten hingegen können die Resultate der Vergleiche nicht verlässlich vorhergesagt werden. Die Pipeline muss also ständig gelöscht und neu gefüllt werden.

Weitere Eigenschaften von Mergesort

Dieses Kapitel behandelt die Platzkomplexität von Mergesort, die Stabilität sowie die Parallelisierbarkeit.

Platzkomplexität von Mergesort

In der Merge-Phase werden Elemente aus zwei Teil-Arrays in ein neu erstelltes Ziel-Array kopiert. Im allerletzten Merge-Schritt ist das Ziel-Array genau so groß wie das zu sortierende Array. Wir haben also einen linearem Platzbedarf: Bei einem doppelt so großen Eingabe-Array verdoppelt sich auch der zusätzlich benötigte Speicherplatz. Es gilt also:

Die Platzkomplexität von Mergesort beträgt: O(n)

(Zur Erinnerung: Bei linearem Aufwand kann konstanter Platzbedarf für Hilfs- und Schleifenvariablen vernachlässigt werden.)

Dieser zusätzliche Speicherbedarf kann durch sogenannte In-Place-Verfahren umgangen werden; diese werden im Abschnitt „In-Place Mergesort“ behandelt.

Stabilität von Mergesort

In der Merge-Phase entscheiden wir mittels if (leftValue <= rightValue), ob das nächste Element aus dem linken oder rechten Teil-Array in das Ziel-Array kopiert wird. Wenn linker und rechter Wert gleich sind, wird also zuerst der linke kopiert und dann der rechte. Somit bleibt die Reihenfolge gleicher Elemente zueinander immer unverändert.

Mergesort ist demzufolge ein stabiles Sortierverfahren.

Parallelisierbarkeit von Mergesort

Es gibt grundsätzlich zwei Ansätze, um Mergesort zu parallelisieren:

• Rekursive Aufrufe von mergeSort() können parallel ausgeführt werden; hierbei können allerdings heutige Mehrkern-CPUs in den letzten Merge-Stufen nicht voll ausgenutzt werden.
• Die merge()-Methode selbst kann parallelisiert werden.

Weiterführende Informationen dazu findest du im Mergesort-Artikel von Wikipedia.

In-Place Mergesort

Im Abschnitt „Platzkomplexität“ haben wir festgestellt, dass Mergesort einen zusätzlichen Platzbedarf in der Größenordnung O(n) hat.

Es gibt verschiedene Ansätze, um den Merge-Vorgang ohne zusätzlichen Speicher (also „in place“) auskommen zu lassen.

Ein Ansatz ist folgender:

• Wenn das Element über dem linken Merge-Zeiger kleiner oder gleich dem Element über dem rechten Merge-Zeiger ist, wird der linke Merge-Zeiger um ein Feld nach rechts verschoben.
• Andernfalls werden alle Element vom ersten Zeiger bis zu, aber ausschließlich dem zweiten Zeiger um ein Feld nach rechts geschoben und das rechte Element auf den freigewordenen Platz gesetzt. Danach werden beide Zeiger um ein Feld nach rechts verschoben, ebenso die Endposition des linken Teil-Arrays.

In-Place Mergesort – Beispiel

Das folgende Beispiel zeigt diesen In-Place-Merge-Algorithmus am Beispiel von oben – gemerged werden sollen die Teil-Arrays [2, 3, 5] und [1, 4, 6].

Das linke Teil-Array ist gelb eingefärbt, das rechte orange und die fertig gemergten Elemente blau.

Im ersten Schritt tritt gleich der zweite Fall ein: Das rechte Element (die 1) ist kleiner als das linke. Es werden alle Elemente des linken Teil-Arrays um ein Feld nach rechts geschoben und das rechte Element wird an den Anfang gesetzt:

Im zweiten Schritt ist das linke Element (die 2) kleiner, daher wird lediglich der linke Suchzeiger ein Feld nach rechts verschoben:

Im dritten Schritt ist wieder das linke Element (die 3) kleiner, es wird also wieder der linke Suchzeiger verschoben:

Im vierten Schritt ist das rechte Element (die 4) kleiner als das linke. Der verbleibende Teil des linken Bereichs (nur noch die 5) wird also um ein Feld nach rechts geschoben und das rechte Element auf den freien Platz gesetzt:

Im fünften Schritt ist das linke Element (die 5) kleiner. Der linke Suchzeiger wird um eine Position nach rechts geschoben und hat damit das Ende des linken Bereichs erreicht:

Der In-Place-Merge-Vorgang ist damit abgeschlossen.

In-Place Mergesort – Zeitkomplexität

Wir haben die Merge-Phase jetzt zwar ohne zusätzlichen Speicherbedarf ausgeführt – allerdings haben wir uns dies teuer erkauft: Durch die zwei verschachtelten Schleifen hat die Merge-Phase nun eine Zeitkomplexität im average und worst case von O(n²) – statt vorher O(n).

Die Gesamt-Komplexität des Sortierverfahrens ist damit O(n² log n) – statt O(n log n). Der Algorithmus ist somit nicht mehr effizient.

Lediglich im best case, wenn die Zahlen vorab aufsteigend sortiert sind, bleibt die Zeitkomplexität innerhalb der Merge-Phase O(n) und die des Gesamt-Algorithmus O(n log n). Der Grund dafür ist, dass in diesem Fall die innere Schleife, die die Elemente des linken Teilarrays nach rechts verschiebt, nie ausgeführt wird.

In-Place Mergesort – Quellcode

Hier ist der Quellcode der merge()-Methode von In-Place Mergesort:

void merge(int[] elements, int leftPos, int rightPos, int rightEnd) {
  int leftEnd = rightPos - 1;

  while (leftPos <= leftEnd && rightPos <= rightEnd) {
    // Which one is smaller?
    int leftValue = elements[leftPos];
    int rightValue = elements[rightPos];
    if (leftValue <= rightValue) {
      leftPos++;
    } else {
      // Move all the elements from leftPos to excluding rightPos one field
      // to the right
      int movePos = rightPos;
      while (movePos > leftPos) {
        elements[movePos] = elements[movePos - 1];
        movePos--;
      }
      elements[leftPos] = rightValue;
      leftPos++;
      leftEnd++;
      rightPos++;
    }
  }
}Code-Sprache: Java (java)

Den vollständigen Quellcode findest du in der Klasse InPlaceMergeSort im GitHub-Repository.

Effiziente In-Place-Merge-Verfahren

Es gibt auch effizientere In-Place-Mergeverfahren, die eine Zeitkomplexität von O(n log n) erreichen und damit eine Gesamt-Zeitkomplexität von O(n (log n)²), diese sind jedoch sehr komplex, so dass ich sie hier nicht weiter behandeln werde.

Natural Mergesort

Natural Mergesort ist eine Optimierung von Mergesort: Es identifiziert vorsortierte Bereiche („runs“) in den Eingabedaten und merged diese jeweils miteinander. So wird das unnötige weitere Teilen und Mergen vorsortierter Teilfolgen vermieden. Komplett aufsteigend sortierte Eingabeelemente werden dementsprechend in der Größenordnung O(n) sortiert.

Je nach Implementierung werden auch absteigend sortierte Teilfolgen („descending runs“) erkannt und in umgekehrter Richtung gemerged. Diese Varianten erreichen auch für komplett absteigend sortierte Eingabedaten O(n).

Natural Mergesort – Beispiel

Die folgende Grafik zeigt Natural Mergesort am Beispiel unserer Zahlenfolge [3, 7, 1, 8, 2, 5, 9, 4, 6]. Im ersten Schritt werden die „runs“ identifiziert. In den folgenden Schritten werden diese gemerged:

Natural Mergesort – Quellcode

Der folgende Quellcode zeigt eine einfache Implementierung, bei der nur aufsteigend sortierte Bereiche identifiziert und gemerged werden:

public void sort(int[] elements) {
  int numElements = elements.length;

  int[] tmp = new int[numElements];
  int[] starts = new int[numElements + 1];

  // Step 1: identify runs
  int runCount = 0;
  starts[0] = 0;
  for (int i = 1; i <= numElements; i++) {
    if (i == numElements || elements[i] < elements[i - 1]) {
      starts[++runCount] = i;
    }
  }

  // Step 2: merge runs, until only 1 run is left
  int[] from = elements;
  int[] to = tmp;

  while (runCount > 1) {
    int newRunCount = 0;

    // Merge two runs each
    for (int i = 0; i < runCount - 1; i += 2) {
      merge(from, to, starts[i], starts[i + 1], starts[i + 2]);
      starts[newRunCount++] = starts[i];
    }

    // Odd number of runs? Copy the last one
    if (runCount % 2 == 1) {
      int lastStart = starts[runCount - 1];
      System.arraycopy(from, lastStart, to, lastStart,
            numElements - lastStart);
      starts[newRunCount++] = lastStart;
    }

    // Prepare for next round...
    starts[newRunCount] = numElements;
    runCount = newRunCount;

    // Swap "from" and "to" arrays
    int[] help = from;
    from = to;
    to = help;
  }

  // If final run is not in "elements", copy it there
  if (from != elements) {
    System.arraycopy(from, 0, elements, 0, numElements);
  }
}Code-Sprache: Java (java)

Die Signatur der merge()-Methode unterscheidet sich hier wie folgt vom Beispiel oben:

• Anstatt von Teil-Arrays wird hier das gesamte Ursprungs-Arrays sowie Positionsangaben der zu mergenden Bereiche übergeben.
• Anstatt ein neues Array zurückzugeben, wird auch das Ziel-Array zum Befüllen an die Methode übergeben.

Der eigentliche Merge-Algorithmus bleibt der gleiche.

Den vollständigen Quellcode einschließlich der merge()-Methode findest du in der Klasse NaturalMergeSort im GitHub-Repository.

Timsort

Das von Tim Peters entwickelte Timsort ist eine hoch optimierte Weiterentwicklung von Natural Mergesort, bei der unter anderem (Teil-)Arrays bis zu einer bestimmten Größe mit Insertion Sort sortiert werden.

Timsort ist der Standard-Sortieralgorithmus in Python. Im JDK wird es für alle nicht-primitiven Objekte verwendet, also in den folgenden Methoden:

• Collections.sort​(List<T> list)
• Collections.sort​(List<T> list, Comparator<? super T> c)
• List.sort(Comparator<? super E> c)
• Arrays.sort(T[] a, Comparator<? super T> c)
• Arrays.sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)

Mergesort vs. Quicksort

Wie schlägt sich Mergesort im Vergleich zu den im vorangegangenen Artikel behandelten Quicksort?

Das folgende Diagramm zeigt die Laufzeiten für unsortierte und aufsteigend sortierte Eingabedaten. Absteigend vorsortierte Elemente werden von beiden Algorithmen minimal langsamer verarbeitet als aufsteigend vorsortierte, ich habe sie deshalb der Übersichtlichkeit halber nicht in das Diagramm eingetragen.

Quicksort ist für eine Viertelmilliarde unsortierte Elemente etwa 50 % schneller als Mergesort. Für vorsortierte Elemente ist es sogar vier mal so schnell.

Der Grund liegt ganz einfach darin, dass beim Mergen immer alle Elemente kopiert werden. Bei Quicksort hingegen werden nur diejenigen Elemente verschoben, die sich in der falschen Partition befinden.

Mergesort hat gegenüber Quicksort den Vorteil, dass auch im worst case die Zeitkomplexität O(n log n) nicht überschritten wird und dass es stabil ist. Diese Vorteile erkauft man sich durch schlechtere Performance und einen zusätzlichen Platzbedarf in der Größenordnung O(n).

Zusamenfassung

Mergesort ist ein effizienter, stabiler Sortieralgorithmus mit einer Zeitkomplexität von O(n log n) im best, average und worst case.

Mergesort hat in seiner Standardimplementierung eine zusätzliche Platzkomplexität von O(n) – diese kann durch eine In-Place-Sortierung umgangen werden, welche allerdings entweder sehr komplex ist oder die Zeitkomplexität des Algorithmus gravierend verschlechtert.

Die JDK-Methoden Collections.sort(), List.sort() und Arrays.sort() (letzteres für alle nicht-primitiven Objekte) verwenden Timsort: ein optimiertes Natural Mergesort, wobei vorsortierte Bereiche in den Eingabedaten erkannt und nicht weiter geteilt werden.

In der Artikelserie über Sortieralgorithmen kommem wir nach drei relativ leicht zu verstehenden Sortierverfahren (Insertion Sort, Selection Sort, Bubble Sort) zu den komplexeren – dafür aber auch deutlich effizienteren Algorithmen.

Wir beginnen mit Quicksort („Sort“ ist hier kein separates Wort, also nicht „Quick Sort“). Dieser Artikel:

• beschreibt den Quicksort-Algorithmus,
• zeigt dessen Quellcode in Java,
• erklärt, wie man die Zeitkomplexität von Quicksort herleitet,
• testet, ob die Performance der Java-Implementierung mit dem erwarteten Laufzeitverhalten übereinstimmt,
• stellt mehrere Algorithmus-Optimierungen vor (Kombination mit Insertion Sort und Dual-Pivot Quicksort)
• und misst und vergleicht auch deren Geschwindigkeit.

Die Quellcodes der Artikelserie findest du in meinem GitHub-Repository.

Quicksort Algorithmus

Quicksort funktioniert nach dem „Teile-und-herrsche“-Prinzip („divide and conquer“):

Als erstes teilen wir die zu sortierenden Elemente auf zwei Bereiche auf – einen mit kleinen Elementen (im folgenen Beispiel „A“) und einen mit großen Elementen (im Beispiel „B“).

Welche Elemente klein sind und welche groß, entscheidet dabei das sogenannte Pivot-Element. Das Pivot-Element kann ein beliebiges Element aus dem Eingabe-Array sein. (Welches man wählt, bestimmt die Pivot-Strategie, dazu später mehr.)

Das Array wird nun so umsortiert, dass

• die Elemente, die kleiner als das Pivot-Element sind, im linken Bereich landen,
• die Elemente, die größer als das Pivot-Element sind, im rechten Bereich landen,
• und dass das Pivot-Element zwischen den zwei Bereichen positioniert wird – und damit automatisch an seiner endgültigen Position.

In folgendem Beispiel werden die Elemente [3, 7, 1, 8, 2, 5, 9, 4, 6] auf diese Art umsortiert. Als Pivot-Element habe ich das letzte Element des unsortierten Eingabe-Arrays gewählt (die orange gefärbte 6):

Dieses Aufteilen auf zwei Teil-Arrays nennt man Partitionieren. Wie die Partitionierung genau funktioniert, erfährst du im nächsten Abschnitt. Vorher zeige ich dir, wie der übergeordnete Algorithmus weitergeht.

Die Teil-Arrays links und rechts des Pivot-Elements sind nach der Partitionierung weiterhin unsortiert. Die Teil-Arrays werden nun ebenfalls partitioniert. Das Pivot-Element aus dem vorherigen Schritt, die 6, habe ich halbtransparent dargestellt, um die zwei Teil-Arrays besser erkennen zu können:

Nach der erneuten Partitionierung haben wir vier Bereiche: Aus A sind A1 und A2 entstanden; aus B sind B1 und B2 hervorgegangen. Die Bereiche A1, B1 und B2 bestehen aus nur noch einem Element und gelten damit als sortiert („beherrscht“ im Sinne von „Teile und herrsche“). Jetzt müssen wir nur noch das Teil-Array A2 partitionieren:

Die zwei in diesem Schritt aus A2 entstandenen Partitionen A2a und A2b haben wieder die Länge 1 und gelten damit als sortiert. Somit sind alle Teil-Arrays sortiert – und damit auch das gesamte Array:

Der Algorithmus ist damit beendet.

Wie die Aufteilung eines Arrays in zwei Bereiche funktioniert – die Partitionierung – erkläre ich im nächsten Abschnitt.

Quicksort Partitionierung

Die Aufteilung des Arrays in zwei Partitionen erfolgt, in dem wir von links beginnend nach Elementen suchen, die größer als das Pivot-Element sind, und von rechts beginnend nach Elementen, die kleiner sind als das Pivot-Element.

Diese Elemente werden dann jeweils vertauscht. Dies wiederholen wir solange, bis die linke und rechte Suchposition aufeinander getroffen oder aneinander vorbeigelaufen sind.

Im Beispiel von oben funktioniert das wie folgt:

• Das erste Element von links, das größer als das Pivot-Element 6 ist, ist die 7.
• Das erste Element von rechts, das kleiner als die 6 ist, ist die 4.
• Wir vertauschen die 7 und die 4.

Die 3 befand sich bereits auf der richtigen Seite (kleiner als 6, also links). Ich habe sie schwächer eingefärbt, da wir sie nicht weiter betrachten müssen.

Wir suchen weiter und finden von links aus die 8 (die 1 ist schon auf der richtigen Seite, da kleiner als 6) und von rechts aus die 5 (die 9 ist ebenfalls bereits auf der richtigen Seite, da größer als 6). Wir vertauschen die 8 und die 5:

Nun treffen sich die linke und rechte Suchposition an der 2. Das Vertauschen endet hier. Da die 2 kleiner ist als das Pivot-Element, schieben wir den Suchzeiger noch eine Position nach rechts, auf die 8, so dass alle Elemente ab dieser Position größer oder gleich dem Pivot-Element sind und alle Elemente davor kleiner:

Damit das Pivot-Element am Anfang der rechten Partition steht, vertauschen wir noch die 8 mit der 6:

Die Partitionierung ist abgeschlossen: Die 6 befindet sich an der richtigen Position, die Zahlen links von der 6 sind kleiner und die Zahlen rechts davon größer. Wir haben also den Stand erreicht, der im vorangegangenen Abschnitt nach der ersten Partitionierung gezeigt wurde:

Das Pivot-Element

„Pivot“ ist französisch und bedeutet „Dreh- und Angelpunkt“.

Im vorangegangenen Beispiel habe ich jeweils das letzte Element eines (Teil-)Arrays als Pivot-Element ausgewählt. Diese Strategie hat den Vorteil, dass sie den Algorithmus besonders einfach macht; sie kann sich aber negativ auf die Performance auswirken.

Vorteil der Pivot-Strategie „letztes Element“

Der Vorteil ist, wie oben erwähnt, ein vereinfachter Algorithmus:

Da das Pivot-Element bei dieser Strategie garantiert im rechten Bereich liegt, brauchen wir es bei den Vergleichs- und Tauschoperationen nicht zu berücksichtigen. Außerdem können wir im letzten Schritt der Partitionierung bedenkenlos das erste Element des rechten Bereichs mit dem Pivot-Element vertauschen, um dieses an seine finale Position zu setzen.

Nachteil der Pivot-Strategie „letztes Element“

In der Praxis führt die Strategie zu Problemen bei vorsortierten Eingabedaten. Bei einem aufsteigend sortierten Array wäre das Pivot-Element in jeder Iteration das größte Element.

Damit würde das Array nicht mehr in zwei möglichst gleich große Partitionen aufgeteilt werden, sondern in eine leere (da kein Element größer ist als das Pivotelement), und eine der Länge n-1 (mit allen Elementen außer dem Pivot-Element).

Dies würde sich negativ auf die Performance auswirken (s. Abschnitt „Quicksort Zeitkomplexität“).

Bei absteigend sortierte Eingabedaten wäre das Pivot-Element immer das kleinste Element, so dass die Partitionierung ebenfalls immer eine leere Partition und eine der Größe n-1 erzeugen würde.

Alternative Pivot-Strategien

Alternative Strategien für die Auswahl des Pivot-Elements sind z. B.:

• das mittlere Element,
• ein zufälliges Element,
• der Median aus drei, fünf oder mehr Elementen.

Wählt man auf eine dieser Arten das Pivot-Element aus, erhöht sich die Wahrscheinlichkeit, dass die aus der Partitionierung hervorgehenden Teil-Arrays möglichst gleich groß sind.

Wie sich die Wahl der Pivot-Strategie auf die Performance auswirkt, werde ich im Laufe des Artikels erklären.

Warum nicht der Median?

Im optimalen Fall teilt das Pivot-Element das Array in zwei gleich große Hälften. Warum wählt man dann nicht einfach den Median aller Elemente als Pivot-Element?

Aus folgendem Grund: Um den Median zu bestimmen, müsste man das Array erst einmal sortieren. Wir definieren aber gerade erst den Sortieralgorithmus – wir stehen also vor einem klassischen Henne-Ei-Problem.

Quicksort Java Quellcode

Der folgende Java-Quellcode (Klasse QuicksortSimple im GitHub-Repository) verwendet der Einfachheit halber als Pivot-Element immer das rechte Element eines zu sortierenden (Teil-)Arrays.

Wie oben erläutert, ist dies keine gute Wahl, wenn die Eingabedaten bereits sortiert sein könnten. Diese Variante macht den Code aber zunächst einfacher zu verstehen.

public class QuicksortSimple {

  public void sort(int[] elements) {
    quicksort(elements, 0, elements.length - 1);
  }

  private void quicksort(int[] elements, int left, int right) {
    // End of recursion reached?
    if (left >= right) {
      return;
    }

    int pivotPos = partition(elements, left, right);
    quicksort(elements, left, pivotPos - 1);
    quicksort(elements, pivotPos + 1, right);
  }

  public int partition(int[] elements, int left, int right) {
    int pivot = elements[right];

    int i = left;
    int j = right - 1;
    while (i < j) {
      // Find the first element >= pivot
      while (elements[i] < pivot) {
        i++;
      }

      // Find the last element < pivot
      while (j > left && elements[j] >= pivot) {
        j--;
      }

      // If the greater element is left of the lesser element, switch them
      if (i < j) {
        ArrayUtils.swap(elements, i, j);
        i++;
        j--;
      }
    }

    // i == j means we haven't checked this index yet.
    // Move i right if necessary so that i marks the start of the right array.
    if (i == j && elements[i] < pivot) {
      i++;
    }

    // Move pivot element to its final position
    if (elements[i] != pivot) {
      ArrayUtils.swap(elements, i, right);
    }
    return i;
  }

}Code-Sprache: Java (java)

Erklärung des Quellcodes:

Die Methode sort() ruft quicksort() auf und übergibt das Array sowie die Start- und Endpositionen.

Die Methode quicksort() ruft zuerst die Methode partition() auf, um das Array zu partitionieren. Daraufhin ruft sie sich selbst rekursiv auf – einmal für das Teil-Array links des Pivot-Elements und einmal für das Teil-Array rechts des Pivot-Elements. Die Rekursion endet, wenn quicksort() für ein Sub-Array der Länge 1 oder 0 aufgerufen wird.

Die Methode partition() partitioniert das Array und gibt die Position des Pivot-Elements zurück. Die Variable i stellt den linken Suchzeiger dar, die Variabe j den rechten Suchzeiger. Die einzelnen Schritte der partition()-Methode sind im Code dokumentiert – sie entsprechen den Schritten des Beispiels aus dem Abschnitt „Quicksort Partitionierung“.

Quellcode für alternative Pivot-Strategien

Wollen wir nicht das rechte, sondern ein anderes Element als Pivot-Element verwenden, muss der Algorithmus erweitert werden. Es gibt drei Varianten:

Algorithmus-Variante 1

Die einfachste Variante ist es das gewählte Pivot-Element vorab mit dem rechten Element zu tauschen. In diesem Fall kann der restliche Quellcode unverändert bleiben.

Eine entsprechende Implementierung findest du in der Klasse QuicksortVariant1 im GitHub-Repository. In dieser Variante wird vor jeder Partitionierung die Methode findPivotAndMoveRight() aufgerufen, die entsprechend der gewählten Strategie das Pivot-Element auswählt und mit dem Element ganz rechts vertauscht.

Mögliche Pivot-Strategien sind im Enum PivotStrategy definiert und lauten:

• RANDOM: ein zufälliges Element wird ausgewählt.
• LEFT: das linke Element wird ausgewählt.
• RIGHT: das rechte Element wird ausgewählt (entspricht letztendlich der oben abgedruckten Variante „QuicksortSimple“).
• MIDDLE: das mittlere Element wird ausgewählt.
• MEDIAN3: der Median aus drei Elementen des Arrays wird als Pivot-Element ausgewählt.

Algorithmus-Variante 2

In dieser Variante beziehen wir das Pivot-Element in den Tauschvorgang ein und tauschen Elemente, die größer oder gleich dem Pivot-Element sind mit Elementen, die kleiner als das Pivot-Element sind.

Wenn wir das Pivot-Element selbst vertauschen, müssen wir uns diese Positionsänderung merken.

Somit befindet sich das Pivot-Element vor dem letzten Schritt der Partitionierung im rechten Bereich und kann ohne weitere Prüfung mit dem ersten Element des rechten Bereichs getauscht werden.

Den Quellcode dieser Variante findest Du in QuicksortVariant2.

Algorithmus-Variante 3

In dieser Variante belassen wir das Pivot-Element während der Partitionierung zunächst an seinem Platz. Dies erreichen wir, in dem wir nur Elemente, die größer als das Pivot-Element sind mit Elementen tauschen, die kleiner als das Pivot-Element sind.

Im letzten Schritt der Partitionierung müssen wir dann prüfen, ob sich das Pivot-Element im linken oder rechten Bereich befindet. Befindet es sich im linken Bereich, müssen wir es mit dem letzten Element des linken Bereichs tauschen; befindet es sich im rechten Bereich, müssen wir es mit dem ersten Element des rechten Bereichs tauschen.

Den Quellcode dieser Variante findest Du in QuicksortVariant3.

Quicksort Zeitkomplexität

Klicke auf den folgenden Link für eine Einführung in „Zeitkomplexität“ und „O-Notation“ (mit Beispielen und Diagrammen).

Wir bezeichnen im Folgenden die Anzahl der zu sortierenden Elemente mit n.

Zeitkomplexität im best case

Quicksort erreicht optimale Performance, wenn wir die Arrays und Teil-Arrays immer wieder in zwei gleich große Partitionen aufteilen.

Denn dann brauchen wir bei einer Verdopplung der Anzahl der Elemente n nur eine einzige zusätzliche Stufe von Partitionierungen p. Folgendes Diagramm zeigt, dass bei vier Elementen zwei Partitionierungsstufen benötigt werden und bei acht Elementen nur eine mehr:

Wir haben also eine Anzahl an Partitionierungsstufen von log₂ n.

Auf jeder Partitionierungsstufe müssen wir insgesamt n Elemente auf linke und rechte Partition aufteilen (auf der ersten Ebene 1 × n, auf der zweiten 2 × n/2, auf der dritten 4 × n/4, usw.):

Diese Aufteilung erfolgt – aufgrund der einzelnen Schleife innerhalb der Partitionierung – mit linearem Aufwand: Bei Verdoppelung der Array-Größe verdoppelt sich auch der Partitionierungs-Aufwand. Der Gesamtaufwand ist daher auf allen Partitionierungsstufen gleich.

Wir haben also n Elemente mal log₂ n Partitionierungsstufen. Damit gilt:

Die Zeitkomplexität von Quicksort beträgt im best case: O(n log n)

Zeitkomplexität im average case

Die durchschnittliche Zeitkomplexität lässt sich leider nicht ohne komplizierte Mathematik herleiten. Diese würde den Rahmen dieses Artikels sprengen. Ich verwiese hier auf den englischsprachigen Wikipedia-Artikel.

Dieser kommt zu dem Schluss, dass die durchschnittlich Anzahl der Vergleichsoperationen 1,39 n × log₂ n beträgt – wir befinden uns also nach wie vor im quasilinearen Aufwand; es gilt:

Die Zeitkomplexität von Quicksort beträgt auch im average case: O(n log n)

Zeitkomplexität im worst case

Wenn das Pivot-Element immer das kleinste oder größte Element des (Teil-)Arrays ist (z. B. weil unsere Eingabedaten bereits sortiert sind und wir als Pivot-Element immer das letzte wählen), würde das Array nicht in zwei etwa gleich große Partitionen aufgeteilt werden, sondern in eine der Länge 0 (da kein Element größer als das Pivot-Element ist) und eine der Länge n-1 (alle Elemente bis auf das Pivot-Element).

Damit bräuchten wir n Partitionierungsstufen mit einem Partitionierungsaufwand der Größe n, n-1, n-2, usw:

Der Partitionierungsaufwand sinkt linear von n bis 0 – im Mittel beträgt er also ½ n. Bei n Partitionierungsstufen beträgt der Gesamtaufwand also n × ½ n = ½ n². Es gilt somit:

Die Zeitkomplexität von Quicksort beträgt im worst case: O(n²)

In der Praxis würde der Versuch ein aufsteigend oder absteigend vorsortiertes Array mit der Pivot-Strategie „rechtes Element“ zu sortieren sehr schnell an einer StackOverflowException scheitern, da die Rekursion so tief gehen müsste wie das Array groß ist.

Java Quicksort Laufzeit

Nach so viel Theorie zurück zur Praxis!

Mit dem Programm UltimateTest können wir die tatsächliche Performance von Quicksort (und allen anderen Algorithmen dieser Artikelserie) messen. Das Programm geht dabei wie folgt vor:

• Es sortiert Arrays der Größe 1.024, 2.048, 4.096, usw. bis maximal 536.870.912 (= 2²⁹), bricht dabei allerdings ab, wenn ein einzelner Sortiervorgang 20 Sekunden oder länger benötigt.
• Es wendet den Sortieralgorithmus auf unsortierte Eingabedaten, aufsteigend sortierte und absteigend sortierte Eingabedaten an.
• Es durchläuft zunächst zwei Warmup-Phasen, um dem HotSpot-Compiler ausreichend Zeit zu geben, den Code zu optimieren.
• Das ganze wird so oft wiederholt, bis der Prozess beendet wird.

Laufzeit-Messung der Quicksort-Algorithmus-Varianten

Zunächst müssen wir entscheiden, welche Algorithmus-Variante wir ins Rennen schicken wollen, um den Test nicht ausufern zu lassen. Dafür kombiniert das Programm CompareQuicksorts alle Varianten mit allen Pivot-Strategien und sortiert mit jeder Kombination 50 mal etwa 5,5 Millionen Elemente.

Hier ist das Ergebnis, sortiert nach Laufzeit (Datei Quicksort_Pivot_Strategies.log):

Folgendes lässt sich ablesen:

• Der simple Algorithmus ist am schnellsten.
• Für alle Algorithmus-Varianten ist die Pivot-Strategie RIGHT am schnellsten, dicht gefolgt von MIDDLE, danach mit etwas größerem Abstand MEDIAN3 (der Overhead ist hier offenbar größer als der Gewinn), und am langsamsten ist RANDOM (Zufallszahlen zu generieren ist teuer).
• Für alle Pivot-Strategien ist Variante 1 am schnellsten, Variante 3 am zweitschnellsten und Variante 2 am langsamsten.

Laufzeit-Messungen für verschiedene Pivot-Strategien und Array-Größen

Aufgrund dieses Ergebnisses führe ich den UltimateTest mit Algorithmus-Variante 1 aus (Pivot-Element wird vorab mit dem rechten Element vertauscht).

In den folgenden Abschnitten findest du die Ergebnisse für die verschiedenen Pivot-Strategien nach 50 Iterationen (dies sind nur Auszüge; das vollständige Testergebnis findest du in UltimateTest_Quicksort.log).

Messergebnisse für Pivot-Strategie „rechtes Element“

Folgendes lässt sich ablesen:

• Bei zufällig verteilten Eingabedaten verlängert sich die benötigte Zeit um etwas mehr als das doppelte, wenn sich die Größe des zu sortierenden Arrays verdoppelt. Dies entspricht der erwarteten quasi-linearen Laufzeit – O(n log n).
• Bei aufsteigend oder absteigend sortierten Eingabedaten vervierfacht sich die benötigte Zeit bei verdoppelter Eingabegröße, hier haben wir also quadratische Zeit – O(n²).
• Absteigend sortierte Daten zu sortieren dauert nur wenig länger als aufsteigend sortierte Daten zu sortieren.
• Bei nur 8.192 Elementen wird für das Sortieren vorsortierter Eingabedaten bereits 23 mal so lange benötigt wie für das Sortieren unsortierter Daten.
• Bei mehr als 8.192 Elementen kommt es bei vorsortierten Eingabedaten zur gefürchteten StackOverflowException.

Messergebnisse für Pivot-Strategie „mittleres Element“

Es lässt sich ablesen:

• Sowohl für unsortierte als auch sortierte Eingabedaten wird bei Verdoppelung der Array-Größe etwas mehr als die doppelte Zeit benötigt. Dies entspricht der erwarteten quasi-linearen Laufzeit – O(n log n).
• Für bereits sortierte Eingabedaten ist der Algorithmus deutlich schneller als für zufällig angeordnete – und zwar sowohl für aufsteigend als auch für absteigend sortierte Daten.
• Die Performance-Verlust durch den Vorabtausch des mittleren mit dem rechten Element beträgt in allen Tests mit unsortierten Eingabedaten weniger als 0,9 %.

Messergebnisse für Pivot-Strategie „Median aus drei Elementen“

Es lässt sich ablesen:

• Auch hier haben wir in allen Fällen quasi-linearen Aufwand – O(n log n).
• Wie schon beim Vergleich der Algorithmus-Varianten ist die Pivot-Strategie „Median aus drei Elementen“ etwas langsamer als die Strategie „mittleres Element“.

Überblick über alle Messergebnisse

Hier findest du die Messergebnisse noch einmal als Diagramm (absteigend sortierte Eingabedaten habe ich der Übersicht halber weggelassen):

Man sieht noch einmal schön, dass die Strategie „Rechtes Element“ für aufsteigend sortierte Daten zu quadratischem Aufwand führt (rote Linie) und für unsortierte Daten am schnellsten ist (blaue Linie). Am zweitschnellsten (mit minimalem Abstand) ist die Pivot-Stragie „Mittleres Element“ (gelbe Linie).

Quicksort optimiert: Kombination mit Insertion Sort

Für sehr kleine Arrays ist Insertion Sort schneller als Quicksort, daher werden in der Praxis diese Algorithmen häufig kombiniert. D. h. (Sub-)Arrays werden ab einer bestimmten Größe nicht weiter partitioniert, sondern mit Insertion Sort sortiert.

Quicksort/Insertion Sort Quellcode

Die Quellcode-Änderungen gegenüber des Standard-Quicksorts sind sehr überschaubar und beschränken sich auf die quicksort()-Methode. Hier noch einmal die Methode aus dem Standard-Algorithmus:

private void quicksort(int[] elements, int left, int right) {
  // End of recursion reached?
  if (left >= right) {
    return;
  }

  int pivotPos = partition(elements, left, right);
  quicksort(elements, left, pivotPos - 1);
  quicksort(elements, pivotPos + 1, right);
}Code-Sprache: Java (java)

Und hier die optimierte Variante, wobei die Variablen insertionSort und partitioningAlgorithm Instanzen des Insertion-Sort- und des Quicksort-Algorithmus sind. Hinzugekommen ist hier lediglich der mit „Threshold for insertion sort reached?“ kommentierte Code-Block in der Mitte der Methode:

private void quicksort(int[] elements, int left, int right) {
  // End of recursion reached?
  if (left >= right) {
    return;
  }

  // Threshold for insertion sort reached?
  if (right - left < threshold) {
    insertionSort.sort(elements, left, right + 1);
    return;
  }

  int pivotPos = partitioningAlgorithm.partition(elements, left, right);
  quicksort(elements, left, pivotPos - 1);
  quicksort(elements, pivotPos + 1, right);
}Code-Sprache: Java (java)

Den kompletten Quellcode findest du in der Klasse QuicksortImproved im GitHub-Repository. Als Konstruktorparameter wird der Grenzwert für das Umschalten auf Insertion Sort, threshold, übergeben, sowie eine Instanz der zu verwendenden Quicksort-Variante.

Quicksort/Insertion Sort Performance

Das Programm CompareImprovedQuickSort misst die benötigte Zeit zum Sortieren von etwa 5,5 Millionen Elementen bei verschiedenen Grenzwerten für das Umschalten auf Insertion Sort.

Da das optimierte Quicksort nur Arrays ab einer gewissen Größe partitioniert, könnte der Einfluss der Pivot-Strategie und der Algorithmus-Variante eine andere Rolle spielen als bisher. Um dies zu berücksichtigen, testet das Programm die Grenzwerte für alle drei Algorithmus-Varianten sowie die Pivot-Strategien „Mitte“ und „Median aus drei Elementen“.

Die kompletten Messergebnisse findest du in CompareImprovedQuicksort.log.

Wie auch in den vorangegangenen Tests performen hier Algorithmus-Variante 1 und Pivot-Strategie „Mittleres Element“ durchgehend am besten.

Hier die Messwerte für die gewählte Kombination und verschiedene Grenzwerte für das Umschalten auf Insertion Sort:

Hier die Messwerte in grafischer Darstellung:

Resultat:

Durch das Umschalten auf Insertion Sort für (Sub-)Arrays, die 48 oder weniger Elemente enthalten, können wir die Laufzeit von Quicksort bei 5,5 Millionen Elementen auf etwa 85 % des ursprünglichen Wertes reduzieren.

Wie sich der optimierte Quicksort-Algorithmus bei anderen Eingabegrößen schlägt, erfährst du im Abschnitt „Vergleich aller Quicksort-Optimierungen“.

Dual-Pivot Quicksort

Quicksort lässt sich noch weiter optimieren, in dem man nicht ein Pivot-Element verwendet, sondern zwei. Bei der Partitionierung werden die Elemente dann aufgeteilt in:

• Elemente kleiner als das kleinere Pivot-Element,
• Elemente größer als/gleich wie das kleinere Pivot-Element und kleiner als das größere Pivot-Element,
• Elemente größer als/gleich wie das größere Pivot-Element.

Auch hier gibt es unterschiedliche Pivot-Strategien, z. B.:

• Linkes und rechtes Element: Dies führt – analog zum regulären Quicksort – dazu, dass bei sortierten Elementen zwei Partitionen leer bleiben und eine Partition n-2 Elemente enthält. Dies wiederum resultiert in quadratischem Aufwand und StackOverflowExceptions schon bei vergleichsweise kleinen n.
• Elemente an den Position „ein Drittel“ und „zwei Drittel“: Dies ist vergleichbar mit der Strategie „Mittleres Element“ im regulären Quicksort.

Das folgende Diagramm zeigt eine beispielhafte Partitionierung mit zwei Pivot-Elementen an den „Drittel“-Positionen:

Dual-Pivot Quicksort wird (mit zusätzlichen Optimierungen) im JDK von der Methode Arrays.sort() eingesetzt.

Dual-Pivot Quicksort Quellcode

Die quicksort()-Methode ruft sich – im Vergleich zum regulären Algorithmus – nicht für zwei, sondern für drei Partitionen rekursiv auf:

private void quicksort(int[] elements, int left, int right) {
  // End of recursion reached?
  if (left >= right) {
    return;
  }

  int[] pivotPos = partition(elements, left, right);
  int p0 = pivotPos[0];
  int p1 = pivotPos[1];
  quicksort(elements, left, p0 - 1);
  quicksort(elements, p0 + 1, p1 - 1);
  quicksort(elements, p1 + 1, right);
}Code-Sprache: Java (java)

Die partition()-Methode ruft zunächst findPivotsAndMoveToLeftRight() auf, welche anhand der gewählten Pivot-Strategie die Pivot-Elemente auswählt und mit den Elementen links und rechts vertauscht (analog zum Vertauschen des Pivot-Elements mit dem rechten Elemente im regulären Quicksort).

Danach laufen wieder zwei Suchzeiger von links und rechts über das Array und vergleichen und tauschen die Elemente, so dass diese am Ende auf drei Partitionen aufgeteilt sind. Wie genau sie das tun, lässt sich anhand der sprechenden Variablennamen einigermaßen gut am Quellcode ablesen.

int[] partition(int[] elements, int left, int right) {
  findPivotsAndMoveToLeftRight(elements, left, right);
  int leftPivot = elements[left];
  int rightPivot = elements[right];

  int leftPartitionEnd = left + 1;
  int leftIndex = left + 1;
  int rightIndex = right - 1;

  while (leftIndex <= rightIndex) {

    // elements < left pivot element?
    if (elements[leftIndex] < leftPivot) {
      ArrayUtils.swap(elements, leftIndex, leftPartitionEnd);
      leftPartitionEnd++;
    }

    // elements >= right pivot element?
    else if (elements[leftIndex] >= rightPivot) {
      while (elements[rightIndex] > rightPivot && leftIndex < rightIndex) {
        rightIndex--;
      }
      ArrayUtils.swap(elements, leftIndex, rightIndex);
      rightIndex--;
      if (elements[leftIndex] < leftPivot) {
        ArrayUtils.swap(elements, leftIndex, leftPartitionEnd);
        leftPartitionEnd++;
      }
    }
    leftIndex++;
  }
  leftPartitionEnd--;
  rightIndex++;

  // move pivots to their final positions
  ArrayUtils.swap(elements, left, leftPartitionEnd);
  ArrayUtils.swap(elements, right, rightIndex);

  return new int[]{leftPartitionEnd, rightIndex};
}Code-Sprache: Java (java)

Die Methode findPivotsAndMoveToLeftRight() arbeitet wie folgt:

Bei der Pivot-Strategie LEFT_RIGHT prüft sie, ob das ganz linke Element kleiner ist als das ganz rechte. Wenn nicht, werden beide vertauscht.

Bei der Strategie THIRDS werden zunächst die Elemente an den Positionen „ein Drittel“ (Variable first) und „zwei Drittel“ (Variable second) extrahiert. Danach folgt eine Reihe von if-Abfragen, die letztendlich bloß das größere der beiden Elemente nach ganz rechts setzt und das kleinere der beiden Elemente nach ganz links.

(Der Code wird dadurch so aufgebläht, dass zwei Sonderfälle berücksichtigt werden müssen: In sehr kleinen Partitionen könnte das erste Pivotelement auf das ganz linke Element fallen und das zweite Pivotelement auf das ganz rechte Element.)

private void findPivotsAndMoveToLeftRight(int[] elements,
                                          int left, int right) {
  switch (pivotStrategy) {
    case LEFT_RIGHT -> {
      if (elements[left] > elements[right]) {
        ArrayUtils.swap(elements, left, right);
      }
    }

    case THIRDS -> {
      int len = right - left + 1;
      int firstPos = left + (len - 1) / 3;
      int secondPos = right - (len - 2) / 3;

      int first = elements[firstPos];
      int second = elements[secondPos];

      if (first > second) {
        if (secondPos == right) {
          if (firstPos == left) {
            ArrayUtils.swap(elements, left, right);
          } else {
            // 3-way swap
            elements[right] = first;
            elements[firstPos] = elements[left];
            elements[left] = second;
          }
        } else if (firstPos == left) {
          // 3-way swap
          elements[left] = second;
          elements[secondPos] = elements[right];
          elements[right] = first;
        } else {
          ArrayUtils.swap(elements, firstPos, right);
          ArrayUtils.swap(elements, secondPos, left);
        }
      } else {
        if (secondPos != right) {
          ArrayUtils.swap(elements, secondPos, right);
        }
        if (firstPos != left) {
          ArrayUtils.swap(elements, firstPos, left);
        }
      }
    }

    default -> throw new IllegalStateException("Unexpected value: " + pivotStrategy);
  }
}Code-Sprache: Java (java)

Den vollständigen Quellcode findest Du in der Datei DualPivotQuicksort.

Dual-Pivot Quicksort Performance

Ob und inwieweit Dual-Pivot Quicksort die Performance verbessert, findest du im Abschnitt „Vergleich aller Quicksort-Optimierungen“ heraus.

Dual-Pivot Quicksort kombiniert mit Insertion Sort

Genau wie das reguläre Quicksort kann auch Dual-Pivot Quicksort mit Insertion Sort kombiniert werden. Die Quellcode-Änderungen entsprechen denen für das reguläre Quicksort (s. Abschnitt „Quicksort/Insertion Sort Quellcode“). Ich gehe daher hier nicht noch einmal im Detail darauf ein.

Den Quellcode findest du in DualPivotQuicksortImproved.

Das Programm CompareImprovedDualPivotQuicksort testet den Algorithmus für verschiedene Grenzwerte für das Umschalten auf Insertion Sort.

Die Messwerte findest du in CompareImprovedDualPivotQuicksort.log. Hier sind sie als Diagramm:

Es lohnt sich also bei Dual-Pivot-Quicksort (Sub-)Arrays mit 64 Elementen oder weniger mit Insertion Sort zu sortieren.

Vergleich aller Quicksort-Optimierungen

Mit dem in Abschnitt „Java Quicksort Laufzeit“ erwähnten UltimateTest vergleiche ich abschließend noch einmal die Performance folgender Algorithmen:

• Reguläres Quicksort mit Pivot-Strategie „Mittleres Element“,
• Quicksort kombiniert mit Insertion Sort und einem Schwellwert von 48,
• Dual-Pivot Quicksort mit Pivot-Strategie „Elemente an den Positionen ein Drittel und zwei Drittel“,
• Dual-Pivot Quicksort kombiniert mit Insertion Sort und einem Schwellwert von 64,
• Arrays.sort() des JDK (die JDK-Entwickler haben ihren Dual-Pivot Quicksort-Algorithmus so weit optimiert, dass es sich bei diesem schon bei 44 Elementen lohnt auf Insertion Sort umzuschalten).

Das Ergebnis findest Du in UltimateTest_Quicksort_Optimized.log – und in folgendem Diagramm:

Zunächst einmal ist sehr schön der quasi-lineare Aufwand aller Varianten zu erkennen.

Die Performance von Dual-Pivot-Quicksort ist sichtbar besser als die des regulären Quicksort – bei einer Viertelmilliarde Elemente etwa 5 %. Die Kombinationen mit Insertion Sort bringen jeweils mindestens 10 % Performancegewinn.

An die Sortiermethode des JDK kommen die Eigenimplementierungen nicht ganz heran – es fehlen noch etwa 6 %. Die JDK-Methode wurde im Laufe der Jahre hoch optimiert. Wenn dich interessiert, wie genau, dann kannst du dir den Quellcode auf GitHub anschauen.

Außerdem ist gut zu erkennen, dass alle Varianten vorsortierte Daten deutlich schneller sortieren als unsortierte – und aufsteigend sortierte Daten etwas schneller als absteigend sortierte. Arrays.sort() ist auch für vorsortierte Daten optimiert, so dass die entsprechende Linie nur minimal über der Null-Linie liegt (172,7 ms bei einer Viertelmilliarde Elemente).

Weitere Eigenschaften von Quicksort

Als weitere Eigenschaften werden in diesem Kapitel die Platzkomplexität von Quicksort betrachtet, die Stabilität sowie die Parallelisierbarkeit.

Platzkomplexität von Quicksort

Für jede Rekursionsstufe brauchen wir zusätzlichen Speicher auf dem Stack. Im average und best case ist die maximale Rekursionstiefe durch O(log n) begrenzt (s. Abschnitt „Zeitkomplexität“).

Im worst case ist die maximale Rekursionstiefe n.

Der Algorithmus kann allerdings durch Endrekursion insoweit optimiert werden, dass immer nur die kleinere Partition durch Rekursion weiterverarbeitet wird und die größere durch Iteration.

Da die kleinere Teilpartition maximal halb so groß ist wie die Ausgangspartition (andernfalls wäre sie nicht die kleinere, sondern die größere Teilpartition), kommt es mit Endrekursion auch im worst case maximal zu einer Rekursionstiefe von log₂ n.

Der zusätzliche Speicherbedarf pro Rekursionsstufe ist konstant. Somit gilt:

Die Platzkomplexität von Quicksort ist im best und average case und – bei Einsatz von Endrekursion auch im worst case – O(log n)

Stabilität von Quicksort

Durch die Art und Weise, wie Elemente innerhalb der Partitionierung auf die Teilbereiche aufgeteilt werden, können Elemente mit gleichem Key ihre ursprüngliche Reihenfolge ändern.

Hier ein simples Beispiel: Partitioniert werden soll das Array [7, 8, 7, 2, 6] mit der Pivot-Strategie „Rechtes Element“. (Die zweite 7 habe ich als 7′ gekennzeichnet, um sie von der ersten unterscheiden zu können.)

Das erste Element von links, das größer als die 6 ist, ist die erste 7. Das erste Element von rechts, das kleiner als die 6 ist, ist die 2. Es müssen also die erste 7 und die 2 vertauscht werden:

Die erste 7 befindet sich danach nicht mehr vor, sondern hinter der zweiten 7 (7′). Dies bleibt auch so, nachdem das erste Element der rechten Partition (die 8) mit dem Pivot-Element (der 6) vertauscht wurde:

Quicksort ist demzufolge nicht stabil.

Parallelisierbarkeit von Quicksort

Es gibt verschiedene Varianten Quicksort zu parallelisieren.

Zum einen lassen sich mehrere Partitionen parallel weiter partitionieren. Bei dieser Variante kann jedoch die erste Partitionierungsstufe gar nicht parallelisiert werden, in der zweiten Stufe können nur zwei Cores ausgelastet werden, in der dritten nur vier, usw.

Es gibt mehrere andere, ausgefeiltere Varianten; eine Zusammenfassung findest du in diesem englischsprachigen Artikel über paralleles Quicksort.

Quicksort vs. Mergesort

Einen Vergleich der Laufzeiten von Quicksort und Mergesort findest du im Artikel über Mergesort.

Zusamenfassung

Quicksort ist ein effizienter, instabiler Sortieralgorithmus mit einer Zeitkomplexität von O(n log n) im best und average case und O(n²) im worst case.

Für sehr kleine n ist Quicksort langsamer als Insertion Sort und wird daher in der Praxis in der Regel mit Insertion Sort kombiniert.

Die Methode Arrays.sort() im JDK verwendet eine Dual-Pivot Quicksort-Implementierung, die (Teil-)Arrays mit weniger als 44 Elementen mit Insertion Sort sortiert.

Weitere Sortieralgorithmen findest du in der Übersicht aller Sortieralgorithmen und ihrer Eigenschaften im ersten Teil der Artikelserie.

Dieser Artikel ist Teil der Serie „Sortieralgorithmen: Ultimate Guide“ und…

• erklärt die Funktionsweise von Bubble Sort,
• stellt den Quellcode von Bubble Sort vor,
• erklärt, wie man die Zeitkomplexität von Bubble Sort herleitet
• und prüft, ob die Performance der eigenen Implementierung dem entsprechend der Zeitkomplexität erwarteten Laufzeitverhalten entspricht.

Die Quellcodes aller Artikel dieser Serie findest du in meinem GitHub-Repository.

Bubble Sort Algorithmus

Bei Bubble Sort (auch: „Bubblesort“) werden jeweils zwei aufeinanderfolgende Elemente miteinander verglichen und – wenn das linke Element größer ist als das rechte – werden diese vertauscht.

Diese Vergleichs- und Tauschoperationen führt man von links nach rechts über alle Elemente durch, so dass nach dem ersten Durchlauf das größte Element ganz rechts positioniert ist (besser gesagt: spätestens nach dem ersten Durchlauf – es kann auch schon vorher dort angekommen sein).

Diesen Prozess wiederholt man solange, bis es in einem Durchlauf zu keinem weiteren Vertauschen mehr kommt.

Bubble Sort Beispiel

Im folgenden zeige ich, wie man das Array [6, 2, 4, 9, 3, 7] mit Bubble Sort sortiert:

Vorbereitung

Wir teilen das Array gedanklich in einen linken, nicht sortierten, und einen rechten, sortierten Teil. Der rechte Teil ist zu Beginn leer:

Iteration 1

Wir vergleichen die ersten beiden Elemente, die 6 und die 2. Da die 6 kleiner ist, vertauschen wir die Elemente:

Nun vergleichen wir das zweite mit dem dritten Element, also die 6 mit der 4. Auch diese liegen in verkehrter Reihenfolge vor und werden vertauscht:

Wir vergleichen das dritte mit dem vierten Element, also die 6 mit der 9. Die 6 ist kleiner als die 9, also brauchen wir diese zwei Elemente nicht zu vertauschen.

Das vierte und fünfte Element, die 9 und die 3, müssen wiederum vertauscht werden:

Und zuletzt müssen das fünfte und sechste Elemente, die 9 und die 7, miteinander vertauscht werden. Danach ist die erste Iteration abgeschlossen.

Die 9 hat ihre finale Position erreicht und wir verschieben die Grenze zwischen den Bereichen um eine Position nach links:

Diese Bereichsgrenze zeigt uns in der nächsten Iteration, bis zu welcher Position die Elemente vergleichen werden müssen. Die Bereichsgrenze gibt es übrigens nur in der optimierten Variante von Bubble Sort. In der ursprünglichen Variante fehlt sie, so dass in jeder Iteration unnötigerweise bis zum Ende des Arrays verglichen wird.

Iteration 2

Wir starten erneut am Anfang des Arrays und vergleichen die 2 mit der 4. Diese liegen in korrekter Reihenfolge vor und müssen nicht vertauscht werden.

Das gleiche gilt für die 4 und die 6.

Die 6 und die 3 hingegen müssen vertauscht werden, um in richtiger Reihenfolge vorzuliegen:

Die 6 und die 7 liegen in korrekter Reihenfolge vor und müssen nicht vertauscht werden. Weiter brauchen wir nicht zu vergleichen, denn die 9 liegt bereits im sortierten Bereich.

Zuletzt schieben wir die Bereichsgrenze wieder um eine Position nach links, damit wir die letzten zwei Elemente, die 7 und die 9, nicht weiter betrachten müssen.

Iteration 3

Wieder starten wir am Anfang des Arrays. Die 2 und die 4 stehen korrekt zueinander. Die 4 und die 3 müssen vertauscht werden:

Die 4 und die 6 müssen nicht vertauscht werden. Die 7 und die 9 sind bereits sortiert. Damit ist diese Iteration auch schon beendet und wir schieben die Bereichsgrenze nach links:

Iteration 4

Wir beginnen wieder am Anfang des Arrays. Im unsortierten Bereich müssen weder die 2 und 3 noch die 3 und 4 vertauscht werden. Damit sind alle Elemente sortiert und wir können den Algorithmus beenden.

Herkunft des Namens

Wenn wir die Vertauschoperationen des vorherigen Beispiels animieren, steigen die Elemente nach und nach bis zu ihren Zielpositionen auf – ähnlich wie Luftblasen (english: „bubbles“), daher der Name „Bubble Sort“:

Bubble Sort Java Quellcode

Im folgenden findest Du die oben beschriebene, optimierte Implementierung von Bubble Sort.

Da in der ersten Iteration das größte Element bis ganz nach rechts wandert, in der zweiten Iteration das zweitgößte bis zur zweitletzten Position, usw., müssen wir in jeder Iteration ein Element weniger vergleichen als in der vorherigen.

(Im Beispiel im vorangegangenen Abschnitt hatte ich das durch die Bereichsgrenze dargestellt, die nach jeder Iteration um eine Position nach links wandert.)

Dazu dekrementieren wir in der äußeren Schleife den Wert max, beginnend bei elements.length - 1, in jeder Iteration um eins.

Die innere Schleife vergleicht dann jeweils zwei Elemente bis zur Position max miteinander und vertauscht diese, wenn das linke Element größer ist als das rechte.

Wurden in einer Iteration keine Elemente vertauscht (d. h. swapped ist false), endet der Algorithmus vorzeitig.

public class BubbleSortOpt1 {
  public static void sort(int[] elements) {
    for (int max = elements.length - 1; max > 0; max--) {
      boolean swapped = false;
      for (int i = 0; i < max; i++) {
        int left = elements[i];
        int right = elements[i + 1];
        if (left > right) {
          elements[i + 1] = left;
          elements[i] = right;
          swapped = true;
        }
      }
      if (!swapped) break;
    }
  }
}Code-Sprache: Java (java)

Der abgebildete Code unterscheidet sich leicht von der Klasse BubbleSortOpt1 im GitHub-Repository: Diese implementiert das Interface SortAlgorithm, um innerhalb des Testframeworks austauschbar zu sein.

Die nicht-optimierte Variante – in der der Algorithmus in jeder Iteration alle Elemente bis zum Ende vergleicht – findest du in der Klasse BubbleSort.

In der Klasse BubbleSortOpt2 findest du einen theoretisch noch stärker optimierten Algorithmus. Es kann nämlich auch sein, dass nach der n-ten Iteration, nicht nur die letzten n Elemente sortiert sind, sondern mehr – je nachdem, wie die Elemente ursprünglich angeordnet waren.

Diese Variante zählt daher max nicht um jeweils 1 herunter, sondern setzt max nach jeder Iteration auf die Position desjenigen Elements, das zuletzt vertauscht wurde. Der Test CompareBubbleSorts zeigt allerdings, dass diese Variante in der Praxis langsamer ist:

----- Results after 50 iterations-----
BubbleSort     -> fastest: 772.6 ms, median: 790.3 ms
BubbleSortOpt1 -> fastest: 443.2 ms, median: 452.7 ms
BubbleSortOpt2 -> fastest: 497.0 ms, median: 510.0 ms Code-Sprache: Klartext (plaintext)

Die vollständige Ausgabe des Testprogramms findest Du in der Datei TestResults_BubbleSort_Algorithms.log.

Warum ist die zweite optimierte Variante langsamer? Meine Vermutung ist, dass das Speichern und das (innerhalb einer Iteration) mehrfache Aktualisieren der Position des zuletzt vertauschten Elements deutlich teurer ist als das (pro Iteration) maximal einmalige Ändern des swapped-Werts.

Bubble Sort Zeitkomplexität

Wir bezeichnen die Anzahl der zu sortierenden Elemente mit n, im Beispiel oben wäre n = 6.

Die zwei ineinander verschachtelten Schleifen lassen vermuten, dass wir es bei Bubble Sort mit quadratischem Aufwand zu tun haben, also einer Zeitkomplexität* von O(n²). Dies wäre dann der Fall, wenn beide Schleifen bis zu einem Wert iteratieren, der linear mit n steigt.

Dies ist bei Bubble Sort nicht ganz so einfach nachzuweisen, wie z. B. bei Insertion Sort oder Selection Sort.

Bei Bubble Sort müssen wir best, worse und average case separat betrachten. Dies geschieht in den folgenden Unterabschnitten.

* Die Begriffe „Zeitkomplexität“ und „O-Notation“ (ausgesprochen „Groß O-Notation“) erkläre ich in diesem Artikel anhand von Beispielen und Diagrammen.

Zeitkomplexität im best case

Fangen wir mit dem einfachsten Fall an: Falls die Zahlen bereits aufsteigend sortiert sind, wird der Algorithmus in der ersten Iteration feststellen, dass keine Zahlenpaare vertauscht werden müssen und daraufhin umgehend terminieren.

Dabei muss der Algorithmus n-1 Vergleiche durchführen; also gilt:

Die Zeitkomplexität von Bubble Sort beträgt im best case: O(n)

Zeitkomplexität im worst case

Den worst case demonstriere ich an einem Beispiel. Nehmen wir an, wir wollen das absteigend sortierte Array [6, 5, 4, 3, 2, 1] mit Bubble Sort sortieren.

In der ersten Iteration wandert das größte Element, die 6, von ganz links nach ganz rechts. Die fünf Einzelschritte (Vertauschen der Paare 6/5, 6/4, 6/3, 6/2, 6/1) habe ich in der Abbildung weggelassen:

In der zweiten Iteration wird das zweitgrößte Element, die 5, von ganz links – über vier Zwischenschritte – an die vorletzte Position verschoben:

In der dritten Iteration wird die 4 – über drei Zwischenschritte – an die drittletzte Stelle geschoben:

In der vierten Iteration wird die 3 – über zwei Einzelschritte – an ihre finale Position verschoben:

Und zuletzt werden die 2 und die 1 vertauscht:

In Summe haben wir also 5 + 4 + 3 + 2 + 1 = 15 Vergleichs- und Tauschoperationen.

Das können wir auch wie folgt ausrechnen:

Sechs Elemente mal fünf Vergleichs- und Tauschoperationen; geteilt durch zwei, da im Mittel über alle Iterationen die Hälfte der Elemente verglichen und verschoben wird:

6 × 5 × ½   =   30 × ½   =   15

Ersetzen wir 6 durch n, erhalten wir:

n × (n – 1) × ½

Ausmultipliziert ergibt das:

½ (n² – n)

Die höchste Potenz von n in diesem Term ist n²; es gilt also:

Die Zeitkomplexität von Bubble Sort beträgt im worst case: O(n²)

Zeitkomplexität im average case

Die durchschnittliche Zeitkomplexität lässt sich bei Bubble Sort – im Gegensatz zu den meisten anderen Sortieralgorithmen – leider nicht auf anschauliche Art und Weise erklären.

Ohne dies mathematisch zu beweisen (das würde den Rahmen dieses Artikels sprengen) kann man grob sagen, dass man im average case etwa halb so viele Tauschoperationen hat wie im worst case, da sich etwa die Hälfte der Elemente im Vergleich zum Nachbarelement an der richtigen Position befindet. Die Anzahl der Tauschoperationen ist also:

¼ (n² – n)

Bei der Anzahl der Vergleichsoperationen wird es noch komplizierter, diese beträgt (Quelle: Wikipedia):

½ (n² – n × ln(n) – (? + ln(2) – 1) × n) + O(√n)

In beiden Termen ist die höchste Potenz von n wieder n², so dass gilt:

Die Zeitkomplexität von Bubble Sort beträgt im average case: O(n²)

Laufzeit des Java Bubble Sort-Beispiels

Überprüfen wir die Theorie mit einem Test! Im GitHub-Repository findest du das Programm UltimateTest, das Bubble Sort (und alle anderen in dieser Artikelserie vorgestellten Sortieralgorithmen) nach folgenden Kriterien testet:

• für Array-Größen beginnend ab 1.024 Elementen, mit einer Verdoppelung nach jeder Iteration, bis entweder eine Array-Größe von 536.870.912 erreicht ist (= 2²⁹) oder ein Sortiervorgang länger als 20 Sekunden dauert;
• für unsortierte, aufsteigend und absteigend vorsortierte Elemente;
• mit zwei Warm-Up-Runden, um dem HotSpot-Compiler ausreichend Zeit zu geben, um den Code zu optimieren.

Das ganze wird so oft wiederholt, bis der Prozess abgebrochen wird. Nach jeder Wiederholung gibt das Program den Median aller bisherigen Messergebnisse aus.

Hier das Ergebnis für Bubble Sort nach 50 Iterationen:

Dies ist nur ein Auszug, das vollständige Ergebnis findest Du hier.

Hier die Ergebnisse noch einmal als Diagramm:

Bei aufsteigend vorsortierten Elementen ist Bubble Sort so schnell, dass die Kurve keinen Ausschlag nach oben zeigt. Deshalb ist hier die Kurve noch einmal einzeln:

Es lässt sich sehr gut erkennen, …

• dass sich die Laufzeit bei Verdopplung der Eingabemenge bei unsortierten und absteigend sortierten Elementen in etwa vervierfacht;
• dass die Laufzeit bei aufsteigend sortierten Elementen linear wächst und um Größenordnungen kleiner ist als bei unsortierten Elementen;
• dass die Laufzeit im average case etwas mehr als doppelt so hoch ist wie im worst case.

Die ersten zwei Beobachtungen entsprechen den Erwartungen.

Doch warum ist die Laufzeit im average case so viel höher als im worst case? Müssten wir dort nicht nur etwa halb so viele Tauschoperationen haben und zumindest minimal weniger Vergleiche – und dementsprechend eher die halbe Zeit als die doppelte?

Tausch- und Vergleichsoperationen im average und worst case

Um das zu prüfen, nutze ich das Programm CountOperations, um die Anzahl der verschiedenen Operationen anzeigen zu lassen. Hier sind die Ergebnisse für unsortierte und absteigend sortierte Elemente in einer Tabelle zusammengefasst:

Die Ergebnisse bestätigen die Annahme: Bei unsortierten Elementen haben wir etwa halb so viele Tauschoperationen und minimal weniger Vergleiche als bei absteigend sortierten Elementen.

Warum ist Bubble Sort für absteigend sortierte Elemente schneller als für zufällig verteilte Elemente?

Wie kann es sein, dass Bubble Sort bei absteigend sortierten Element trotz doppelt so vieler Tauschoperationen so viel schneller ist als bei zufällig angeordneten Elementen?

Die Ursache für diese Diskrepanz ist in der Sprungvorhersage (englisch „branch prediction“) zu finden:

Wenn die Elemente absteigend sortiert sind, dann ist das Resultat der Vergleichsoperation if (left > right) im unsortierten Bereich immer true und im sortierten Bereich immer false.

Wenn die Sprungvorhersage davon ausgeht, dass das Ergebnis eines Vergleichs immer dasselbe ist wie das des vorangegangenen Vergleichs, dann hat sie mit dieser Annahme – mit einer einzigen Ausnahme: an der Bereichsgrenze – immer Recht. Somit kann die Befehls-Pipeline der CPU die meiste Zeit voll ausgenutzt werden.

Bei unsortierten Daten hingegen können keine verlässlichen Vorhersagen über das Ergebnis des Vergleichs getroffen werden, so dass die Pipeline häufig gelöscht und neu gefüllt werden muss.

Weitere Eigenschaften von Bubble Sort

In diesem Abschnitt geht es um die Platzkomplexität, Stabilität und Parallelisierbarkeit von Bubble Sort.

Platzkomplexität von Bubble Sort

Bubble Sort benötigt neben der Schleifenvariablen max und den Hilfsvariablen swapped, left und right keinen zusätzlichen Speicherplatz.

Die Platzkomplexität von Bubble Sort ist somit O(1).

Stabilität von Bubble Sort

Dadurch, dass immer zwei nebeneinander liegende Elemente miteinander verglichen werden – und diese nur dann vertauscht werden, wenn das linke Element größer ist als das rechte, können Elemente mit gleichem Key niemals die Position relativ zueinander tauschen.

Dazu müssten, wie beispielsweise bei Selection Sort, zwei Elemente über mehr als eine Position hinweg ihre Plätze tauschen. Das kann hier nicht passieren.

Bubble Sort ist somit ein stabiler Sortieralgorithmus.

Parallelisierbarkeit von Bubble Sort

Es gibt zwei Ansätze, um Bubble Sort zu parallelisieren:

Ansatz 1 „Odd-even sort“

Man vergleicht parallel das erste mit dem zweiten Element, das dritte mit dem vierten, das fünfte mit dem sechsten, usw. und vertauscht die jeweiligen Elemente, wenn das linke größer ist als das rechte.

Danach vergleicht man das zweite Element mit dem dritten, das vierte mit dem fünften, das sechste mit dem siebten usw.

Diese zwei Schritte führt man abwechselnd durch, solange bis in beiden Schritten keine Elemente mehr vertauscht werden:

Diesen Algorithmus bezeichnet man auch als „Odd–even sort“.

Du findest den Quellcode in der Klasse BubbleSortParallelOddEven im GitHub-Repository.

Die Synchronisation zwischen den Schritten (die Threads dürfen mit einem Schritt erst dann beginnen, wenn alle Threads den vorherigen Schritt beendet haben), erfolgt dabei mit einem Phaser.

Ansatz 2 „Divide and Conquer“

Man teilt das zu sortierende Array in so viele Bereiche („Partitionen“), wie man Cores zur Verfügung hat.

Nun führt man eine Bubble-Sort-Iteration in allen Partitionen parallel durch. Man wartet, bis alle Threads fertig sind, und vergleicht dann jeweils das letzte Element einer Partition mit dem ersten der nächsten Partition. Wenn auch damit alle Threads fertig sind, beginnt der Vorgang von vorne.

Diese Schritte wiederholt man solange, bis in allen Threads keine Elemente mehr vertauscht werden:

Du findest den Quellcodes des Algorithmus in der Klasse BubbleSortParallelDivideAndConquer im GitHub-Repository.

Auch hier wird zur Synchronisation der Threads ein Phaser verwendet. Tatsächlich ist ein Großteil des Codes beider Algorithmen gleich, da auch für den Odd-Even-Ansatz das Array in Partitionen aufgeteilt wird. Den gemeinsamen Code habe ich in die abstrakte Basisklasse BubbleSortParallelSort verschoben.

Bubble Sort parallel: Performance

Die Performance der parallelen Varianten vergleiche ich mit dem oben bereits genannten Test CompareBubbleSorts. Hier das Ergebnis für die parallelen Algorithmen, verglichen mit der schnellsten sequentiellen Variante:

----- Results after 50 iterations-----
BubbleSortOpt1                     -> fastest:   443.2 ms, median:   452.7 ms
BubbleSortParallelOddEven          -> fastest:    62.6 ms, median:    68.6 ms
BubbleSortParallelDivideAndConquer -> fastest:   126.8 ms, median:   145.7 ms Code-Sprache: Klartext (plaintext)

Die „odd-even“-Variante ist auf meiner 6-Core-CPU (12 virtuelle Kerne mit Hyper-Threading) und bei 20.000 unsortierten Elementen also 6,6 mal schneller als die sequentielle Variante.

Der „divide-and-conquer“-Ansatz ist nur 3,1 mal schneller. Dies dürfte daran liegen, dass jeder Thread im zweiten Teilschritt der Iteration jeweils nur einen Vergleich durchführt. Demgegenüber steht ein relativ hoher Synchronisationsaufwand durch den Phaser.

Zusammenfassung

Bubble Sort ist ein einfach zu implementierender, stabiler Sortieralgorithmus mit einer Zeitkomplexität von O(n²) im average und worst case – und O(n) im best case.

Weitere Sortieralgorithmen findest du in dieser Übersicht aller Sortieralgorithmen und ihrer Eigenschaften im ersten Teil der Artikelserie.

Bubble Sort war das letzte einfache Sortierverfahren dieser Artikelserie; im nächsten Teil steigen wir mit Quicksort in die effizienten Sortierverfahren ein.

Dieses Tutorial erklärt – Schritt für Schritt und mit vielen Code-Beispielen – wie man in Java primitive Datentypen (ints, longs, doubles, etc.) und Objekte beliebiger Klassen sortieren kann.

Im einzelnen beantwortet der Artikel folgende Fragen:

• Wie sortiert man in Java Arrays von primitiven Datentypen?
• Wie sortiert man in Java Arrays und Listen von Objekten?
• Wie sortiert man in Java parallel?
• Welche Sortieralgorithmen verwendet das JDK intern?

Der Artikel ist Teil des Ultimate Guides über Sortieralgorithmen, der einen Überblick über die gängigsten Sortierverfahren und deren Eigenschaften, wie z. B. deren Zeit- und Platzkomplexität, gibt.

Alle Quellcodes dieses Artikels findest du in meinem GitHub-Repository.

Was kann man in Java sortieren?

Die folgenden Datentypen lassen sich mit Java-Bordmitteln sortieren:

• Arrays von primitiven Datentypen (int[], long[], double[], usw.),
• Arrays und Listen von Objekten, die das Comparable-Interface implementieren,
• Arrays und Listen von Objekten beliebiger Klassen, mit Angabe eines Comparators, d. h. eines zusätzlichen Objekts, das das Comparator-Interface implementiert (oder eines entsprechenden Lambdas).

Den genauen Unterschied zwischen Comparable und Comparator erkläre ich in einem separaten Artikel. Dort zeige ich auch, wie man seit Java 8 mit Comparator.comparing() sehr elegant Comparatoren erstellen und aneinanderreihen kann.

Arrays.sort() – primitive Datentypen sortieren

Die Klasse java.util.Arrays stellt Sortiermethoden für alle primitiven Datentypen (außer boolean) bereit:

• static void sort(byte[] a)
• static void sort(char[] a)
• static void sort(double[] a)
• static void sort(float[] a)
• static void sort(int[] a)
• static void sort(long[] a)
• static void sort(short[] a)

Beispiel: Sortieren eines int-Arrays

Das folgenden Beispiel zeigt, wie ein int-Array sortiert und dann auf der Konsole ausgegeben wird:

int[] a = {4, 8, 5, 9, 2, 3, 1, 7, 6};
Arrays.sort(a);
System.out.println(Arrays.toString(a));Code-Sprache: Java (java)

Die Ausgabe dieses kurzen Programs lautet:

[1, 2, 3, 4, 5, 6, 7, 8, 9]Code-Sprache: Klartext (plaintext)

Teilbereiche eines Arrays sortieren

Für jeden der o. g. Datentypen (int, long, double, usw.) gibt es eine überladene Methode, die nur einen Teilbereich des Arrays sortiert, z. B.:

• static void sort(int[] a, int fromIndex, int toIndex)

Das folgende Beispiel sortiert nur die ersten fünf Elemente des Arrays:

int[] a = {4, 8, 5, 9, 2, 3, 1, 7, 6};
Arrays.sort(a, 0, 5);
System.out.println(Arrays.toString(a));Code-Sprache: Java (java)

Das Programm gibt folgendes aus:

[2, 4, 5, 8, 9, 3, 1, 7, 6]Code-Sprache: Klartext (plaintext)

Die ersten fünf Elemente 2, 4, 5, 8, 9 wurden sortiert, die restlichen vier Elemente 3, 1, 7, 6, sind unverändert.

Java-Objekte sortieren

Primitive Datentypen werden nach ihrer natürlichen Ordnung sortiert. Dementsprechend wird unser Beispiel-Array [4, 8, 5, 9, 2, 3, 1, 7, 6] nach dem Sortieren zu [1, 2, 3, 4, 5, 6, 7, 8, 9].

Doch in welcher Reihenfolge werden Objekte sortiert?

Integer- und String-Arrays sortieren

Wie ein Integer– oder String-Array sortiert wird, versteht jeder Java-Entwickler intuitiv:

Integer[] a = {4, 8, 5, 9, 2, 3, 1, 7, 6};
Arrays.sort(a);
System.out.println(Arrays.toString(a));Code-Sprache: Java (java)

Auch hier bekommen wir:

[1, 2, 3, 4, 5, 6, 7, 8, 9]Code-Sprache: Klartext (plaintext)

Sortieren wir ein paar Vornamen:

String[] names = {"Susan", "Thomas", "Judith", "Daniel", "Eva", "Ben",
      "Antonia", "Paul"};
Arrays.sort(names);
System.out.println(Arrays.toString(names));Code-Sprache: Java (java)

Das Ergebnis lautet – wie erwartet:

[Antonia, Ben, Daniel, Eva, Judith, Paul, Susan, Thomas]Code-Sprache: Klartext (plaintext)

Integer-Objekte werden also offensichtlich genau so wie int-Primitive sortiert. Und Strings alphabetisch.

Objekte eigener Klassen sortieren

Doch wie sortiert man seine selbstgebaute Customer-Klasse? Oder eine Invoice?

Probieren wir es aus! Hier zunächst unsere Customer-Klasse:

public class Customer {
  private int id;
  private String firstName;
  private String lastName;

  public Customer(int id, String firstName, String lastName) {
    this.id = id;
    this.firstName = firstName;
    this.lastName = lastName;
  }

  @Override
  public String toString() {
    return "Customer{" +
          "id=" + id +
          ", firstName='" + firstName + ''' +
          ", lastName='" + lastName + ''' +
          '}';
  }Code-Sprache: Java (java)

Wir versuchen diese mit Arrays.sort() zu sortieren:

Customer[] customers = {
      new Customer(43423, "Elizabeth", "Mann"),
      new Customer(10503, "Phil", "Gruber"),
      new Customer(61157, "Patrick", "Sonnenberg"),
      new Customer(28378, "Marina", "Metz"),
      new Customer(57299, "Caroline", "Albers")
};
Arrays.sort(customers);
System.out.println(Arrays.toString(customers));Code-Sprache: Java (java)

Diesen Versuch quittiert Java mit folgender Fehlermeldung:

Exception in thread „main“ java.lang.ClassCastException:
class eu.happycoders.sorting.Customer cannot be cast to class java.lang.Comparable

Java weiß ohne zusätzliche Informationen nicht, wie Customer-Objekte sortiert werden sollen. Wie stellen wir diese Informationen bereit? Das erfährst du im nächsten Kapitel.

Sortieren mit Comparable und Comparator

Die Sortier-Instruktionen können wir auf zwei unterschiedliche Arten bereitstellen:

1. indem wir die Klasse Customer das Interface java.lang.Comparable implementieren lassen (so wie von der Fehlermeldung gefordert) oder
2. indem wir der Arrays.sort()-Methode eine Implementierung des Interfaces java.util.Comparator mitgeben.

Die beiden Varianten werden in den folgenden zwei Abschnitten beschrieben. Einen tieferen Einblick in die Interfaces Comparable und Comparator bietet der Artikel „Comparator, Comparable und compareTo – Vergleichen von Objekten in Java“.

Sortieren mit Comparable

Das Interface java.lang.Comparable definiert eine einzige Methode:

• public int compareTo(T o)

Diese wird vom Sortieralgorithmus aufgerufen, um zu prüfen, ob ein Objekt kleiner, gleich oder größer als ein anderes Objekt ist. Je nachdem muss die Methode eine negative Zahl, 0 oder eine positive Zahl zurückliefern.

(Wenn du dir die Quellcodes von Integer und String anschaust, wirst du feststellen, dass beide das Comparable-Interface und die compareTo()-Methode implementieren.)

Wir wollen unsere Kunden nach Kundennummer sortieren. Dazu müssen wir die Customer-Klasse wie folgt erweitern (den Konstruktor und die toString()-Methode lasse ich hier der Übersicht halber weg):

public class Customer implements Comparable<Customer> {
  private int id;
  private String firstName;
  private String lastName;

  // Constructor and toString method omitted

  @Override
  public int compareTo(Customer o) {
    return this.id < o.id ? -1 : (this.id == o.id ? 0 : 1);
  }
}Code-Sprache: Java (java)

Die Funktionsweise aus Perspektive der compareTo()-Methode:

• Wenn meine Kundennummer kleiner ist als deine, dann gib -1 zurück;
• wenn unsere Kundennummern gleich sind, gib 0 zurück;
• ansonsten gib 1 zurück.

Etwas kürzer wird es, wenn man die Methode Integer.compare() verwendet. Diese vergleicht die zwei IDs auf genau die gleiche Art und Weise:

@Override
public int compareTo(Customer o) {
  return Integer.compare(this.id, o.id);
}Code-Sprache: Java (java)

Unsere so erweiterte Customer-Klasse können wir nun problemlos sortieren lassen (hier noch mal, damit du nicht scrollen musst, das Customer-Sortier-Beispiel von oben):

Customer[] customers = {
      new Customer(43423, "Elizabeth", "Mann"),
      new Customer(10503, "Phil", "Gruber"),
      new Customer(61157, "Patrick", "Sonnenberg"),
      new Customer(28378, "Marina", "Metz"),
      new Customer(57299, "Caroline", "Albers")
};
Arrays.sort(customers);
System.out.println(Arrays.toString(customers));Code-Sprache: Java (java)

Dieses mal läuft das Programm ohne Fehler durch und gibt folgendes aus (die Zeilenumbrüche habe ich der Übersicht halber manuell eingefügt):

[Customer{id=10503, firstName='Phil', lastName='Gruber'},
 Customer{id=28378, firstName='Marina', lastName='Metz'},
 Customer{id=43423, firstName='Elizabeth', lastName='Mann'},
 Customer{id=57299, firstName='Caroline', lastName='Albers'},
 Customer{id=61157, firstName='Patrick', lastName='Sonnenberg'}]Code-Sprache: Klartext (plaintext)

Unsere Kunden sind nun, wie gewünscht, nach Kundernnummer sortiert.

Was aber, wenn wir die Kunden für einen anderen Use Case nicht nach Nummern, sondern nach Namen sortieren wollen? Wir können ja compareTo() nur einmal implementieren. Müssen wir uns für immer und ewig auf eine Reihenfolge festlegen?

Hier kommt das Interface Comparator ins Spiel, das ich im nächsten Abschnitt beschreiben werde.

Sortieren mit einem Comparator

Mit der Customer.compareTo()-Methode haben wir die sogenannte „natürliche Ordnung“ der Kunden definiert. Mit dem Interface Comparator können wir beliebig viele weitere Sortierreihenfolgen für eine Klasse definieren.

Analog zur compareTo()-Methode definiert das Comparator-Interface die folgende Methode:

• int compare(T o1, T o2)

Diese wird aufgerufen, um zu prüfen, ob das Objekt o1 kleiner, gleich oder größer als das Objekt o2 ist. Entsprechend muss auch diese Methode eine negative Zahl, 0 oder eine positive Zahl als Rückgabewert liefern.

Seit Java 8 können wir einen Comparator sehr elegant mit Comparator.comparing() erstellen. Mit folgendem Code können wir die Kunden zunächst nach Nachnamen und dann nach Vornamen sortieren:

Arrays.sort(customers,
      Comparator.comparing(Customer::getLastName)
            .thenComparing(Customer::getFirstName));Code-Sprache: Java (java)

Wie du siehst, kann man hier beinahe in natürlicher Sprache aufschreiben, wie die Kunden sortiert werden sollen.

Den Comparator können wir auch in einer Konstanten in der Customer-Klasse speichern, um ihn an verschiedenen Stellen wiederzuverwenden:

public static final Comparator<Customer> NAME_COMPARATOR = Comparator
    .comparing(Customer::getLastName)
    .thenComparing(Customer::getFirstName);Code-Sprache: Java (java)

Sortieren würden wir die Kunden dann so:

Arrays.sort(customers, Customer.NAME_COMPARATOR);Code-Sprache: Java (java)

Weitere Möglichkeiten, um Comparatoren zu erstellen, findest Du in diesem Artikel. Probier es einfach mal aus!

Sortieren einer Liste in Java

Bis jetzt haben wir ausschließlich die folgenden zwei Methoden der Klasse java.util.Arrays verwendet, um Objekte zu sortieren:

• static void sort(Object[] a) – zum Sortieren von Objekten entsprechend ihrer natürlichen Ordnung,
• static void sort(T[] a, Comparator<? super T> c) – zum Sortieren von Objekten anhand des übergebenenen Comparators.

Oft haben wir Objekte nicht in einem Array vorliegen, sondern in einer Liste. Um diese zu sortieren, gibt es (seit Java 8) zwei Möglichkeiten:

Liste sortieren mit Collections.sort()

Bis einschließlich Java 7 musste die Methode Collections.sort() zu Hilfe genommen werden, um eine Liste zu sortieren.

Im folgenden Beispiel sollen wieder unsere Kunden sortiert werden, zunächst nach Kundennummer (also entsprechend ihrer „natürlichen Ordnung“):

ArrayList<Customer> customers = new ArrayList<>(List.of(
      new Customer(43423, "Elizabeth", "Mann"),
      new Customer(10503, "Phil", "Gruber"),
      new Customer(61157, "Patrick", "Sonnenberg"),
      new Customer(28378, "Marina", "Metz"),
      new Customer(57299, "Caroline", "Albers")
));
Collections.sort(customers);
System.out.println(customers);Code-Sprache: Java (java)

Das Programm gibt, wie im vorherigen Beispiel auch, die Kunden sortiert nach ihrer Kundennummer aus.

Warum werden im Beispiel zwei Listen erstellt? Eine mit List.of() und dann eine weitere mit new ArrayList<>()?

List.of() ist die eleganteste Art eine Liste zu erstellen. Die ist allerdings unveränderlich (was in den meisten Anwendungsfällen von List.of() auch sinnvoll ist) und kann dementsprechend nicht sortiert werden. Daher übergebe ich diese dann an den Konstruktor von ArrayList, der daraus eine veränderliche Liste macht. Zugegeben: nicht die performanteste Lösung, sie macht den Code aber schön kurz.

Collections.sort() prüft übrigens (im Gegensatz zu Arrays.sort()) schon zur Compile-Zeit, ob die übergebene Liste aus Objekten besteht, die Comparable implementieren.

Liste sortieren mit Collections.sort() und einem Comparator

Auch einen Comparator kann man Collections.sort() mitgeben. Folgende Code-Zeile sortiert die Kunden nach Namen:

Collections.sort(customers, Customer.NAME_COMPARATOR);Code-Sprache: Java (java)

Liste sortieren mit List.sort()

Seit Java 8 gibt es (dank der Default-Methoden in Interfaces) die Möglichkeit eine Liste direkt mit List.sort() zu sortieren. Dabei muss immer ein Comparator angegeben werden:

customers.sort(Customer.NAME_COMPARATOR);Code-Sprache: Java (java)

Der Comparator darf allerdings auch null sein, um die Liste entsprechend ihrer natürlichen Ordnung zu sortieren:

customers.sort(null);Code-Sprache: Java (java)

Auch hier bekommen wir eine ClassCastException, wenn die übergebene Liste Objekte enthält, die nicht Comparable implementieren.

Arrays parallel sortieren

Seit Java 8 steht jede der Sortiermethoden aus der java.util.Arrays-Klasse auch in einer parallelen Variante zur Verfügung. Diese verteilt den Sortieraufwand ab einer festgelegten Array-Größe (8.192 Elemente von Java 8 bis Java 13; 4.097 Elemente seit Java 14) auf mehrere CPU Cores. Ein Beispiel:

• static void parallelSort(double[] a)

Das folgende Beispiel misst die benötigte Zeit für das Sortieren von 100 Millionen double-Werten einmal mit Arrays.sort() und einmal mit Arrays.parallelSort():

public class DoubleArrayParallelSortDemo {
  private static final int NUMBER_OF_ELEMENTS = 100_000_000;

  public static void main(String[] args) {
    for (int i = 0; i < 5; i++) {
      sortTest("sort", Arrays::sort);
      sortTest("parallelSort", Arrays::parallelSort);
    }
  }

  private static void sortTest(String methodName, Consumer<double[]> sortMethod) {
    double[] a = createRandomArray(NUMBER_OF_ELEMENTS);
    long time = System.currentTimeMillis();
    sortMethod.accept(a);
    time = System.currentTimeMillis() - time;
    System.out.println(methodName + "() took " + time + " ms");
  }

  private static double[] createRandomArray(int n) {
    ThreadLocalRandom current = ThreadLocalRandom.current();
    double[] a = new double[n];
    for (int i = 0; i < n; i++) {
      a[i] = current.nextDouble();
    }
    return a;
  }
}Code-Sprache: Java (java)

Mein System (DELL XPS 15 mit Core i7-8750H) gibt folgende Messwerte aus:

sort() took 9596 ms
parallelSort() took 2186 ms
sort() took 9232 ms
parallelSort() took 1835 ms
sort() took 8994 ms
parallelSort() took 1917 ms
sort() took 9152 ms
parallelSort() took 1746 ms
sort() took 8899 ms
parallelSort() took 1757 msCode-Sprache: Klartext (plaintext)

Die jeweils ersten Aufrufe dauern etwas länger, da der HotSpot-Compiler etwas Zeit braucht, um den Code zu optimieren.

Danach ist gut zu sehen, wie das parallele Sortieren etwa fünf mal schneller ist als das sequentielle. Für sechs Cores ist das ein sehr gutes Ergebnis, da die Parallelisierung natürlich auch einen gewissen Overhead mit sich bringt.

Sortieralgorithmen im Java Development Kit (JDK)

Im JDK werden je nach Aufgabenstellung verschiedene Sortieralgorithmen angewendet:

• Counting Sort für byte[], short[] und char[], wenn mehr als 64 Bytes bzw. mehr als 1750 Shorts oder Characters sortiert werden.
• Dual-Pivot Quicksort für das Sortieren primitiver Datentypen mit Arrays.sort(). Hierbei handelt es sich um eine optimierte Variante von Quicksort, kombiniert mit Insertion Sort und Counting Sort. Der Algorithmus erreicht eine Zeitkomplexität von O(n log n) bei vielen Eingabedaten, für die andere Quicksort-Implementierungen in der Regel auf O(n²) zurückfallen.
• Timsort (ein optimiertes Natural Mergesort kombiniert mit Insertion Sort) für alle anderen Objekte.

Beim parallelen Sortieren werden folgende Algorithmen angewendet:

• Bytes, Shorts, Characters werden niemals parallel sortiert.
• Für andere primitive Datentypen wird eine Kombination aus Quicksort, Mergesort, Insertion Sort und Heapsort eingesetzt.
• Für Objekte wird ebenfalls Timsort eingesetzt – die parallele Variante allerdings erst bei einer Listengröße von mehr als 8.192 Elementen; darunter wird die Single-Threaded Variante verwendet, da ansonsten der Overhead größer ist als der Gewinn.

Zusamenfassung

Du hast in diesem Artikel gelernt (oder aufgefrischt), wie du in Java primitive Datentypen und Objekte sortieren kannst und welche Sortierverfahren das JDK intern anwendet.

Sortieralgorithmen sind Thema jeder Informatiker-Ausbildung. Viele von uns haben irgendwann einmal die genaue Funktionsweise von Insertion Sort bis Merge- und Quicksort auswendig lernen müssen, einschließlich deren Zeitkomplexitäten im best, average und worst case in Big-O-Notation … um nach der Prüfung das meiste davon wieder zu vergessen ;-)

Wenn du eine Auffrischung brauchst, wie die gebräuchlichsten Sortieralgorithmen funktionieren und wie sie sich unterscheiden, ist diese Artikelserie genau das Richtige für dich.

Dieser erste Artikel behandelt folgende Fragen:

• Welches sind die gebräuchlichsten Sortierverfahren?
• In welchen Eigenschaften unterscheiden sie sich?
• Wie ist das Laufzeitverhalten der einzelnen Sortiermethoden (Platz- und Zeitkomplexität)?

Möchtest du wissen, wie ein bestimmter Sortieralgorithmus genau funktioniert? Jedes aufgelistete Sortierverfahren linkt zu einem vertiefenden Artikel, welcher…

• die Funktionsweise des jeweiligen Verfahrens anhand eines Beispiels erklärt,
• die Zeitkomplexität herleitet (auf anschauliche Weise, ohne komplizierte mathematische Beweise),
• zeigt, wie man den jeweiligen Sortieralgorithmus in Java implementiert, und
• die Performance der Java-Implementierung misst und mit dem theoretischen Laufzeitverhalten abgleicht.

Die Quellcodes der gesamten Artikelserie findest du in meinem GitHub-Repository.

Eigenschaften von Sortieralgorithmen

Sortierverfahren unterscheiden sich hauptsächlich in den folgenden Eigenschaften (Erklärungen findest du in den folgenden Abschnitten):

• Geschwindigkeit (oder besser: Zeitkomplexität)
• Platzkomplexität
• Stabilität
• Vergleichsbasiert / nicht-vergleichsbasiert
• Parallelisierbarkeit
• Rekursiv / nicht rekursiv
• Adaptionsfähigkeit

Du kannst die Erklärungen auch erstmal überspringen und später hierher zurückkehren. Hier geht es direkt zu den wichtigsten Sortieralgorithmen.

Zeitkomplexität von Sortieralgorithmen

Das wichtigste Kriterium bei der Auswahl eines Sortierverfahrens ist in den meisten Fällen dessen Geschwindigkeit. Interessant ist hierbei in erster Linie, wie sich die Geschwindigkeit in Abhängigkeit von der Anzahl der zu sortierenden Elemente ändert.

Denn ein Algorithmus kann bei hundert Elementen doppelt so schnell sein wie ein anderer, bei tausend Elementen aber durchaus fünf mal langsamer (oder noch viel viel langsamer; aber das ließ sich nicht mehr gut in dem Diagramm abbilden):

Deshalb gibt man die Laufzeit eines Algorithmus im allgemeinen als Zeitkomplexität in der sogenannten „O-Notation“ (englisch: „Big O notation“) an.

Die folgenden Klassen von Zeitkomplexitäten sind für Sortieralgorithmen relevant (detailliertere Beschreibungen dieser Komplexitätsklassen findest Du in dem jeweils verlinkten Artikel):

• O(n) (ausgesprochen „O von n“): linearer Aufwand – für doppelt so viel Elemente benötigt die Sortiermethode doppelt so lange;
• O(n log n) (ausgesprochen „O von n log n“): quasi-linearer Aufwand – fast so gut wie linearer Aufwand;
• O(n²) (ausgesprochen: „O von n Quadrat“): quadratischer Aufwand – für doppelt so viele Elemente benötigt die Sortierfunktion viermal so lange, für 10× so viele Elemente 100× so lang, für 1000× so viele Elemente 1.000.000× so lang, usw.

Hier noch einmal das Diagramm von oben mit der Angabe der Zeitkomplexitäten und einer zusätzlichen Kurve für quasilinearen Aufwand. Da die Zeitkomplexität keine Aussage über die absolut benötigten Zeiten macht, sind die Achsen hier nicht mehr mit Werten beschriftet.

Bei quadratischer Komplexität stößt man relativ schnell an die Leistungsgrenzen heutiger Hardware:

Während Quicksort auf meinem Laptop eine Milliarde Elemente in 90 Sekunden sortiert, breche ich den Versuch mit Insertion Sort nach einer Viertelstunde ab. Ausgehend von etwa 100 Sekunden für eine Million Elemente, würde Insertion Sort für eine Milliarde Elemente beeindruckende drei Jahre und zwei Monate brauchen.

Quadratische Komplexität sollte also, wenn möglich, vermieden werden.

Platzkomplexität von Sortieralgorithmen

Nicht nur Zeitkomplexität ist für Sortierverfahren relevant, sondern auch die Platzkomplexität. Diese gibt an, wie viel zusätzlichen Speicherplatz der Algorithmus in Abhängigkeit von der Anzahl der zu sortierenden Elemente benötigt. Damit ist nicht der Speicherplatz gemeint, der für die zu sortierenden Elemente selbst benötigt wird, sondern darüberhinaus benötigter Platz für z. B. Hilfsvariablen, Schleifenzähler und temporäre Arrays.

Platzkomplexität wird mit den gleichen Klassen angegeben wie Zeitkomplexität. Hier treffen wir noch auf eine weitere Klasse:

• O(1) (ausgesprochen „O von 1“): konstanter Aufwand – bei vielen Sortieralgorithmen ist der zusätzliche Speicherbedarf unabhängig von der Anzahl der zu sortierenden Elemente.

Stabile und nicht-stabile Sortierverfahren

Bei stabilen Sortierverfahren wird die relative Reihenfolge von Elementen, die den gleichen Sortierschlüssel haben, beibehalten. Bei nicht-stabilen Sortierverfahren wird dies nicht garantiert: Die relative Reihenfolge kann beibehalten werden, muss es aber nicht.

Was bedeutet das?

In folgendem Beispiel haben wir eine zufällig erzeugte Namensliste. Die Liste ist zunächst nach Vornamen sortiert:

Diese Liste soll nun – ohne die Vornamen zu betrachten – nach Nachnamen sortiert werden. Wenn wir dafür ein stabiles Sortierverfahren anwenden, ist das Ergebnis immer:

D. h. die Reihenfolge von Fabio und Mathias bleibt bei einem stabilen Sortierverfahren immer unverändert. Bei einem unstabilen Sortierverfahren kann auch folgendes Sortierergebnis herauskommen:

Mathias und Fabio sind hierbei gegenüber der Ausgangsreihenfolge vertauscht.

Vergleichsbasierte und nicht-vergleichsbasierte Sortierverfahren

Die meisten der bekannten Sortierverfahren basieren auf dem Vergleich zweier Elemente auf kleiner, größer oder gleich. Es existieren jedoch auch nicht-vergleichsbasierte Sortieralgorithmen.

Wie das funktionieren kann, erfährst du in den Abschnitten Counting Sort und Radix Sort.

Parallelisierbarkeit

Diese Eigenschaft beschreibt, ob und in wie weit sich ein Sortieralgorithmus für die parallele Abarbeitung auf mehreren CPU Cores eignet.

Rekursive / nicht-rekusive Sortiermethoden

Ein rekursiver Sortieralgorithmus benötigt zusätzlichen Speicherplatz auf dem Stack. Bei zu tiefer Rekursion droht die gefürchtete StackOverflowExecption.

Adaptionsfähigkeit (adaptability)

Ein adaptiver Sortieralgorithmus kann sein Verhalten während der Laufzeit an bestimmte Eingabedaten (z. B. vorsortierte Elemente) anpassen und diese deutlich schneller sortieren als zufällig verteilte Elemente.

Vergleich der wichtigsten Sortieralgorithmen

Die folgende Tabelle gibt einen Überblick über alle in dieser Artikelserie vorgestellten Sortieralgorithmen. Es handelt sich um eine Auswahl der am meisten verbreitetsten Sortierverfahren. Dies sind auch die, die man in der Regel in der Informatik-Ausbildung lernt.

Jeder Eintrag ist verlinkt zu einem vertiefenden Artikel, der den jeweiligen Algorithmus und dessen Eigenschaften im Detail beschreibt und auch dessen Quellcode enthält.

Wenn dir zunächst ein Überblick genügt, findest du im Anschluss an die Tabelle die Sortieralgorithmen in jeweils einem Satz erklärt.

Die Variable k steht bei Counting Sort steht für keys (die Anzahl der möglichen Schlüsselwerte) und bei Radix Sort für key length (die maximale Länge eines Schlüssels). Die Variable b bei Radix Sort steht für Basis.

Einfache Sortierverfahren

Einfache Sortierverfahren sind gut geeignet, um kleine Listen zu sortieren. Für große Listen sind sie aufgrund des quadratischen Aufwands ungeeignet. Insbesondere Insertion Sort (was aufgrund von weniger Vergleichen ungefähr doppelt so schnell ist wie Selection Sort) wird gerne verwendet, um effiziente Sortieralgorithmen wie Quicksort und Mergesort weiter zu optimieren. Dazu lässt man diese Verfahren kleine Teillisten im Größenbereich bis ca. 50 Elemente mit Insertion Sort sortieren.

Insertion Sort

Insertion Sort verwendet man zum Beispiel beim Sortieren von Spielkarten: man nimmt eine Karte nach der anderen auf und fügt sie an der richtigen Stelle in die bereits sortieren Karten ein (auf deutsch: Einfüge-Sortieren).

Selection Sort

Selection Sort kannst du dir anhand des Spielkartenbeispiels so vorstellen, dass alle einzusortierenden Karten offen vor dir liegen. Du suchst die kleinste Karte und nimmst sie auf, dann suchst du die nächstgrößere Karte und nimmst sie rechts neben die zuerst aufgenommene Karte, usw. bis du als letztes die größte Karte aufnimmst und nach ganz rechts auf die Hand nimmst.

Bubble Sort

Bei Bubble Sort werden von links nach rechts jeweils nebeneinanderliegende Elemente verglichen und – falls diese in der falschen Reihenfolge vorliegen – miteinander vertauscht. Dieser Vorgang wird so oft wiederholt bis alle Elemente sortiert sind.

Effiziente Sortierverfahren

Effiziente Sortieralgorithmen erreichen eine deutlich bessere Zeitkomplexität von O(n log n). Sie eignen sich daher auch für große Datensätze mit Milliarden von Elementen.

Quicksort

Quicksort funktioniert nach dem „Teile und Herrsche“-Prinzip. Durch eine sogenannte Partitionierung wird der Datensatz zunächst grob in kleine und große Elemente aufgeteilt: kleine kommen nach links, große nach rechts. Jede dieser Partitionen wird danach rekursiv wieder partitioniert, solange bis eine Partition nur noch ein Element enthält und damit als sortiert gilt.

Sobald für alle Partionen und Teil-Partitionen die tiefste Rekursionsstufe erreicht ist, ist die gesamte Liste sortiert.

Quicksort hat zwei Nachteile:

• Im worst case (bei absteigend sortierten Elementen) ist die Zeitkomplexität O(n²).
• Quicksort ist nicht stabil.

Mergesort

Mergesort funktioniert ebenfalls nach dem „Teile und Herrsche“-Prinzip. Wobei hier sozusagen in umgekehrter Reihenfolge vorgegangen wird wie bei Quicksort: Anstatt zuerst zu sortieren und dann in die Rekursion abzusteigen, geht Mergesort zuerst in die Rekursion, bis Teillisten mit nur noch einem Element erreicht sind und fügt dann jeweils zwei Teillisten so zusammen („merged“ sie), dass eine sortierte Teilliste entsteht.

Beim letzten Schritt aus der Rekursion heraus werden zwei verbleibende Teillisten gemerged und ergeben das sortierte Gesamtergebnis.

Mergesort hat gegenüber Quicksort den Vorteil, dass auch im worst case die Zeitkomplexität O(n log n) nicht überschreitet und dass es stabil ist. Allerdings erkauft man sich diese Vorteile durch einen zusätzlichen Platzbedarf in der Größenordnung O(n).

Heapsort

Der Begriff Heapsort ist für Java-Entwickler oft verwirrend, da man ihn zunächst mit dem Java Heap in Verbindung bringt. Die Heaps von Heapsort und Java sind allerdings zwei völlig unterschiedliche Dinge.

Heapsort arbeitet mit der Datenstruktur Heap, einem auf ein Array abgebildeter Binärbaum, in dem jeder Knoten größer oder gleich seiner Kinder ist. Das größte Element liegt also immer auf der Wurzelposition.

Dieses Wurzelelement wird entnommen, dann wird das letzte Element auf die Wurzelposition gesetzt und danach der Baum per „Heapify“-Operation repariert, woraufhin wiederum das größte der verbleibenden Element auf der Wurzelposition liegt. Der Prozess wird solange wiederholt, bis der Baum leer ist. Die dem Baum entnommenen Elemente ergeben das sortierte Ergebnis.

Nicht vergleichsbasierte Sortierverfahren

Nicht vergleichsbasierte Sortierverfahren basieren nicht auf dem Vergleich zweier Element auf kleiner, größer oder gleich.

Wie können sie dann funktionieren?

Am besten lässt sich das an einem Beispiel erklären – im folgenden anhand von Counting Sort.

Counting Sort

Bei Counting Sort werden Elemente – wie der Name schon sagt – gezählt. Um beispielsweise ein Array mit Zahlen aus dem Bereich 1 bis 10 zu sortieren, zählen wir (in einem einzigen Durchgang), wie oft die 1 vorkommt, wie oft die 2, usw. bis zur 10.

Im zweiten Durchgang schreiben wir dann die 1 so oft von links beginnend in das Array, wie sie vorkommt, dann die 2 so oft, wie diese vorkommt, usw. wiederum bis zur 10.

Dieses Verfahren wird in der Regel nur für kleine Zahlentypen wie byte, char oder short eingesetzt, oder wenn der Bereich der zu sortierenden Zahlen bekannt ist (z. B. ints zwischen 0 und 150). Der Grund dafür ist, dass wir für das Zählen der Elemente ein zusätzliches Array entsprechend der Größe des Zahlenbereichs benötigen.

Die Variable k steht für die Anzahl der möglichen Werte (keys).

Radix Sort

Bei Radix Sort werden die Elemente Ziffer für Ziffer sortiert. Dreistellige Zahlen z. B. zuerst nach den Einerstellen, dann nach den Zehnerstellen und zuletzt nach den Hunderterstellen.

Dieses Verfahren eignet sich im Gegensatz zu Counting Sort auch für große Zahlenräume wie int und long, ist stabil und kann sogar schneller sein als Quicksort, hat jedoch mit O(n) eine höhere Platzkomplexität und wird daher seltener eingesetzt.

Sonstige Sortieralgorithmen

Es gibt zahlreiche weitere Sortieralgorithmen (Shell Sort, Comb Sort, Bucket Sort, um nur ein paar zu nennen). Die in diesem Artikel vorgestellten Methoden zu kennen stellt meiner Meinung nach jedoch ein sehr gutes Grundlagenwissen dar.

Falls du dir die Javadocs von List.sort() und Arrays.sort() durchgelesen hast, fragst du dich vielleicht, warum ich hier Timsort und Dual-Pivot Quicksort nicht aufführe.

Timsort ist kein komlett eigenständiges Sortierverfahren. Vielmehr ist es eine Kombination aus Mergesort, Insertion Sort und etwas zusätzlicher Logik. Ich werde Timsort im Artikel über Mergesort beschreiben.

Ebenso ist Dual-Pivot Quicksort eine Variante des regulären Quicksort und wird im entsprechenden Artikel beschrieben werden.

Zusamenfassung

Dieser Artikel hat einen Überblick über die gängigsten Sortieralgorithmen gegeben und die Eigenschaften beschrieben, in denen sich diese hauptsächlich unterscheiden.

In den folgenden Teilen dieser Serie beschreibe ich je einen Sortieralgorithmus im Detail – anhand von Beispielen und mit Quellcodes.

In einem weiteren Teil gebe ich einen Überblick über die Sortiermethoden, die Java bereitstellt, und zeige, wie man zum einen primitive Datentypen sortiert und zum anderen Objekte mit Hilfe von Comparator und Comparable.