Counting Sort

Grundidee

Auf Deutsch kann das Sortierverfahren als „Sortieren durch Abzählen“ übersetzt werden. Die Sortiertechnik basiert dabei auf Schlüssel zwischen einem bestimmten Bereich. Dabei wird die Anzahl der Elemente mit unterschiedlichen Schlüsselwerte gezählt. In Folge dessen wird dann aus den Ergebnissen eine sortierte Liste aufgebaut.

Eigenschaften

Im Folgenden ein kurzer Überblick über die wichtigsten Eigenschaften eines Counting Sorts:

• Das Verfahren gehört zu den stabilen Sortieralgorithmen .
• Es handelt sich dabei um keinen vergleichsbasierter Sortieralgorithmus. Er arbeitet adressbasiert.

direkt ins Video springen

• Das Sortierverfahren zeigt sich am effizientesten, wenn der Bereich der Eingabedaten nicht unmittelbar größer ist als die Anzahl der zu sortierenden Elemente. Entsprechend wird diese Form der Sortierung meist nur in einem mäßig großen Wertebereich verwendet.
• Die Counting Sort Laufzeitkomplexität kann allgemein mit  inklusive einem zusätzlichen Datenbereich als proportionalen Raum definiert werden.
• Das Sortierverfahren kann durch eine Erweiterung auch für das Sortieren von negativen Zahlen verwendet werden

Countingsort Beispiel

Zur Veranschaulichung des Prinzips eines Countingsort wird als Beispiel der folgende Array gegeben:

[3][1][9][4][3][8][9][5]

Zu Beginn wird ein Index mit den Zahlen von 0 bis 9 aufgelistet. Darunter entsteht eine temporäre Liste in Form eines Hilfsarrays, zur Speicherung der Häufigkeiten der jeweiligen Elemente. Entsprechend ergeben sich für den Array die folgenden Werte:

Die Werte der temporären Liste werden im Anschluss von links nach rechts summiert. Dadurch ergibt sich ein neuer Array:

Der Zählvorgang ist damit abgeschlossen, wodurch nun das Sortieren einsetzen kann. Die Reihenfolge der Sortierung wird durch die Eingabeliste bestimmt, wodurch die erste zu sortierende Zahl 3 ist. Entsprechend dem Index von 3 und den Werten des zugehörigen neuen Hilfsarrays, kann der endgültige Platz des Elements bestimmt werden – in diesem Fall Platz 3. Der Wert im Hilfsarray muss entsprechend um 1 minimiert werden.

Im Anschluss wird die Zahl 1 sortiert und dabei muss wiederum der Wert der temporären Liste angepasst werden.

Dieser Vorgang wird für die restlichen Elemente des Ursprungarrays wiederholt. Der genaue Sortiervorgang wird ausführlichen im Video beschrieben! Am Ende lassen sich die Werte des Sortierens durch Zählen inklusive der zusammengefügten neuen, sortierten Liste wie folgt darstellen:

direkt ins Video springen

Algorithmus

Für den Algorithmus muss am Anfang eine zu sortierende Eingabeliste übergeben werden. Im ersten Schritt muss ein Maximum der Zahlen berechnet werden. Sollte es der Fall sein, dass es etwas Größeres als das Aktuelle gibt, soll dies nun das neue Größte sein. Im Anschluss soll eine temporäre Liste in Form eines Hilfsarrays erstellt werden. Im Anschluss werden dann die Indizes aller Zahlen überprüft und dadurch entsprechend gezählt, wie oft jede Zahl vorhanden ist. Die Anzahl wird entsprechend in der temporären Liste gespeichert. Nun geht es an die Sortierung, entsprechend wird die tatsächliche, finale Position der Zahl in der sortierten Reihenfolge gesucht. Beim Sortieren werden die Indizes der temporären Liste nach ihrer Anzahl geprüft. Dabei soll die Anzahl von i durchgegangen werden, um entsprechende gleiche Elemente hintereinander einzutragen. Die Zahl soll nun entsprechend in der richtigen Reihenfolge an die entsprechende Position eingefügt werden um dann als sortierte Liste zurückgegeben zu werden.

Pseudocode

Als Pseudocode lässt sich der Algorithmus dann beispielsweise so darstellen:

countingsort int[] zahlen
  maximumZahlen = zahlen [0]
  for i=1; i 
    if zahlen[i] > maximumZahlen
      maximumZahlen = zahlen [i]
  temporäreListe = int [maximum+1]
  for i = 0; i 
    temporäreliste[zahlen[i]]++
  finaleposition = 0;
  for int i = 0; i 
    for int j = 0; j 
      zahlen[finaleposition] = i
      finaleposition++
  return zahlen

Counting Sort Java

Im Folgenden wird ein Quellcode einer Counting Sort Java-Implementierung aufgezeigt:

static int[] countingsort(int[] zahlen) {
  int maximum = zahlen[0];
  for (int i = 1; i 
    if (zahlen[i] > maximum)
      maximum = zahlen[i];
  }
  int[] hilfsarray = new int[maximum+1];
  for (int i = 0; i 
    hilfsarray[zahlen[i]]++;
  }
  int position = 0;
  for (int i = 0; i 
    for (int j = 0; j 
      zahlen[position] = i;
      position++;
    }
  }
  return zahlen;
}

Counting Sort Laufzeit

Die Counting Sort Laufzeit ist immer abhängig von der Anzahl der Elemente einer Liste n und der Größe des entsprechenden Zahleninvervalls k. Deshalb handelt es sich bei der Sortierung um einen linearen Zeitaufwand. Durch die vorhandene for-Schleife besitzt dabei jeweils n- oder k-Durchläufe. Dadurch lässt sich eine Laufzeitkomplexität von  bestimmen. Entsprechend kann es sich für den Sortieralgorithmus vorteilhaft auswirken, wenn die Intervalllänge im Gegensatz zur Anzahl der Objekte n deutlich kleiner ist.

Speicherplatzkomplexität

Dadurch, dass der Counting Sort out-of-place arbeitet, braucht der Algorithmus eine temporäre Liste/ ein Hilfsarray zur Zwischenspeicherung unserer Zahlenwerte. Entsprechend beträgt der Speicherplatz k-Elemente, wodurch die Speicherplatzkomplexität  entspricht.