Counting Sort Sortieralgorithmen - Feature-Bild

Counting Sort – Algorithmus, Quellcode, Zeitkomplexität

Autor-Bild
von Sven Woltmann – 2. September 2020

Artikelserie: Sortieralgorithmen

Teil 1: Einführung

Teil 2: Sortieren in Java

Teil 3: Insertion Sort

Teil 4: Selection Sort

Teil 5: Bubble Sort

Teil 6: Quicksort

Teil 7: Mergesort

Teil 8: Heapsort

Teil 9: Counting Sort

Teil 10: Radix Sort

(Melde dich für den HappyCoders-Newsletter an,
um sofort über neue Teile informiert zu werden.)

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:

Counting Sort Algorithmus - zu sortierendes Array

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:

Counting Sort Algorithmus - Zähler-Array

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:

Counting Sort Algorithmus - Zählen, Schritt 1

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

Counting Sort Algorithmus - Zählen, Schritt 2

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

Counting Sort Algorithmus - Zählen, Schritte 3 und 4

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:

Counting Sort Algorithmus - Zählen, Schritte 5 und 6

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:

Counting Sort Algorithmus - Zählen, Schritte 7 bis 15

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.

Counting Sort Algorithmus - Neu anordnen, Schritt 1

(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.

Counting Sort Algorithmus - Neu anordnen, Schritt 2

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

Counting Sort Algorithmus - Neu anordnen, Schritt 3

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

Counting Sort Algorithmus - Neu anordnen, Schritt 4

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:

Counting Sort Algorithmus - Neu anordnen, Schritte 5 bis 10

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:

Counting Sort - Allgemeiner Algorithmus - zu sortierendes Array

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

Counting Sort - Allgemeiner Algorithmus - Histogramm

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:

Counting Sort - Allgemeiner Algorithmus - Phase 2 - Aggregation - Schritt 1

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

Counting Sort - Allgemeiner Algorithmus - Phase 2 - Aggregation - Schritt 2

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

Counting Sort - Allgemeiner Algorithmus - Phase 2 - Aggregation - Schritt 3

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

Counting Sort - Allgemeiner Algorithmus - Phase 2 - Aggregation - Schritt 9

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:

Counting Sort - Allgemeiner Algorithmus - Phase 3 - Zielarray

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).

Counting Sort - Allgemeiner Algorithmus - Phase 3 - Schritt 1

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:

Counting Sort - Allgemeiner Algorithmus - Phase 3 - Schritt 2

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:

Counting Sort - Allgemeiner Algorithmus - Phase 3 - Schritt 3

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

Counting Sort - Allgemeiner Algorithmus - Phase 3 - Schritt 4

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:

Counting Sort - Allgemeiner Algorithmus - Phase 3 - Schritt 5

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:

Counting Sort - Allgemeiner Algorithmus - Phase 3 - Schritt 15

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:

n, kunsortiertaufsteigendabsteigend
............
33.554.4321.276 ms195 ms210 ms
67.108.8642.857 ms381 ms388 ms
134.217.7286.087 ms745 ms766 ms
268.435.45612.684 ms1.477 ms1.529 ms
536.870.91227.249 ms2.945 ms3.039 ms

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

Counting Sort - Laufzeit

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)

Wenn dir der Artikel gefallen hat, teile ihn gerne über einen der Share-Buttons am Ende. Möchtest du per E-Mail informiert werden, wenn ich einen neuen Artikel veröffentliche? Dann klicke hier, um dich in den HappyCoders-E-Mail-Verteiler einzutragen