Countingsort

Countingsort (von engl. count „zählen“) ist ein einfaches, stabiles Sortierverfahren. Es sortiert eine gegebene Zahlenfolge nicht durch Vergleiche, sondern setzt das Wissen voraus, aus welchem Intervall die Zahlen des Schlüssels stammen.

Problemstellung

Die zu sortierenden Zahlen liegen in $\{0,1,\ldots,k\}$ für ein festes, im Voraus bekanntes k. Dann bestimme für jedes zu sortierende Element x die Anzahl der Elemente, welche in der sortierten Reihenfolge vor x liegen, und platziere damit x an die korrekte Stelle.

Eingabe

Feld A[1..n] mit $A[j] \in \{0, \ldots, k\}$ für alle $j=1,\ldots,n$. Als Parameter werden A,k,n übergeben.

Ausgabe

Feld B[1..n] mit Inhalt von A in sortierter Reihenfolge.

Zudem wird bei dem Sortierverfahren ein Hilfsvektor C[0..k] benötigt.

Implementierungen

Pseudocode

Der nachfolgende Pseudocode bezieht sich auf die in der Problemstellung benutzten Bezeichnungen.

COUNTINGSORT(A, B, k)
1 for i = 0 to k
2     do C[i] = 0
3 for j = 1 to length[A]
4     do C[A[j]] = C[A[j]] + 1
          //C[i] gibt nun an, wie oft i in A vorkommt.
5 for i = 1 to k
6     do C[i] = C[i] + C[i - 1]
          //C[i] gibt nun die Anzahl der Elemente <= i in A an,
          //bzw. die Stelle mit dem größten Index, an dem
          //das Element i im sortierten Array stehen wird.
7 for j = length[A] downto 1
8     do B[C[A[j]]] = A[j]
9         C[A[j]] = C[A[j]] - 1

Python

def counting_sort(A):
    C = [0] * (max(A)+1)
    B = [""] * len(A)
    for index in xrange(len(A)):
        C[A[index]]+=1
    for index in xrange(1, len(C)):
        C[index]+=C[index-1]
    for index in xrange(len(A)-1, -1, -1):
        B[C[A[index]]-1]=A[index]
        C[A[index]]-=1
    return B

Java

// sortiert ein Zahlen-Array mit CountingSort
// erwartet als Parameter ein int-Array und gibt dieses sortiert wieder zurück
static int[] countingSort(int[] numbers) {
        // Maximum der Zahlen berechnen
        int max = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
                // wenn es größeres als das aktuelle gibt, ist das nun das neue größte
                if (numbers[i] > max)
                        max = numbers[i];
        }
 
        // temporäres Array erzeugen mit: Länge = Maximum des Zahlenarrays + die "0"
        int[] sortedNumbers = new int[max+1];
 
        // Indizes des Zahlen-Arrays durchgehen
        for (int i = 0; i < numbers.length; i++) {
                // wir zählen, wie oft jede Zahl aus numbers vorkommt und
                // speichern diese Anzahl in sortedNumbers[] bei Index number[i]
                sortedNumbers[numbers[i]]++;
        }
 
        // insertPosition steht für die Schreib-Position im Ausgabe-Array
        int insertPosition = 0;
 
        // Indizes von sortedNumbers[] durchgehen, um zu sehen, wie oft jede Zahl vorkommt
        for (int i = 0; i <= max; i++) {
                // Anzahl von i durchgehen, um gleiche Zahlen hintereinander einzutragen
                for (int j = 0; j < sortedNumbers[i]; j++) {
                        // das Zahlen-Array wird jetzt sortiert neu geschrieben für jedes
                        // Auftreten von i
                        numbers[insertPosition] = i;
                        insertPosition++;
                }
        }
        return numbers;
}

Beispiel

Ausführung von Countingsort auf ein Eingabefeld A[1..8] mit Elementen aus $\{0, \ldots, 5\}$ mit Hilfsfeld C und sortierter Ausgabe in Feld B.

1	2	3	4	5	6	7	8
2	5	3	0	2	3	0	3

0	1	2	3	4	5
0	0	0	0	0	0

1	2	3	4	5	6	7	8

Darstellung untereinander Ausgangsliste A, Hilfsvektor C, dessen Länge vom Definitionsbereich der Liste abhängt. In unterster Liste werden die Elemente sortiert eingefügt. Die Obige Abbildung stellt die gegebene Zahlenfolge dar, wobei die erste Schleife des Algorithmus bereits abgearbeitet wurde, indem lediglich der Vektor C mit 0 initialisiert wird. Zweite Schleife inkrementiert für jede Ziffer deren Stelle im Vektor um eins.

1	2	3	4	5	6	7	8
2	5	3	0	2	3	0	3

0	1	2	3	4	5
2	0	2	3	0	1

1	2	3	4	5	6	7	8

Die dritte Schleife summiert den Vektor C auf, so dass dessen Inhalt angibt, bis zu welcher Position ein Wert in der sortierten Liste auftaucht. Zwei gleiche aufeinanderfolgende Zahlen bedeuten dabei, dass die letzte der beiden Zahlen in der Folge überhaupt nicht auftaucht, also vorher in C an dieser Position ein 0 gewesen war.

1	2	3	4	5	6	7	8
2	5	3	0	2	3	0	3

0	1	2	3	4	5
2	2	4	7	7	8

1	2	3	4	5	6	7	8

Nun folgt die letzte Schleife. In dieser werden nun sukzessive die Werte aus A in den Vektor B übertragen und zwar genau an der Stelle im Zielvektor, die der Hilfsvektor C für die entsprechende Zahl angibt. Vor der Schleife ist dies immer die letzte Stelle, an der die Zahl auftauchen wird. Nach dem übertragen jeder Zahl wird zusätzlich der Wert in C[Zahl] dekrementiert. Die nächste gleiche Zahl wird deswegen eine Stelle weiter vorn im Zielvektor eingefügt. Nachfolgend die 8 Schritte.

Die ersten 7 Schritte im Detail

1. Schritt

1	2	3	4	5	6	7	8
2	5	3	0	2	3	0	3

0	1	2	3	4	5
2	2	4	6	7	8

1	2	3	4	5	6	7	8
						3

2. Schritt

1	2	3	4	5	6	7	8
2	5	3	0	2	3	0	3

0	1	2	3	4	5
1	2	4	6	7	8

1	2	3	4	5	6	7	8
	0					3

3. Schritt

1	2	3	4	5	6	7	8
2	5	3	0	2	3	0	3

0	1	2	3	4	5
1	2	4	5	7	8

1	2	3	4	5	6	7	8
	0				3	3

4. Schritt

1	2	3	4	5	6	7	8
2	5	3	0	2	3	0	3

0	1	2	3	4	5
1	2	3	5	7	8

1	2	3	4	5	6	7	8
	0		2		3	3

5. Schritt

1	2	3	4	5	6	7	8
2	5	3	0	2	3	0	3

0	1	2	3	4	5
0	2	3	5	7	8

1	2	3	4	5	6	7	8
0	0		2		3	3

6. Schritt

1	2	3	4	5	6	7	8
2	5	3	0	2	3	0	3

0	1	2	3	4	5
0	2	3	4	7	8

1	2	3	4	5	6	7	8
0	0		2	3	3	3

7. Schritt

1	2	3	4	5	6	7	8
2	5	3	0	2	3	0	3

0	1	2	3	4	5
0	2	3	4	7	7

1	2	3	4	5	6	7	8
0	0		2	3	3	3	5

8. Schritt

1	2	3	4	5	6	7	8
2	5	3	0	2	3	0	3

0	1	2	3	4	5
0	2	2	4	7	7

1	2	3	4	5	6	7	8
0	0	2	2	3	3	3	5

Laufzeitanalyse

Wie man aus obigem Pseudocode leicht ersehen kann, hängt die Laufzeit der Funktion von N (Anzahl der Elemente des Eingabe(arrays)) und M(Anzahl jeder Zahl) ab. Die erste for-Schleife wird genau N-mal durchlaufen, die zweite genau M-mal. Die Zeitkomplexität von Countingsort beträgt $\mathcal{O}(N + M)$.

Speicherplatzbedarf

Zusätzlich zur Eingabe, die N Speicherfelder benötigt, wird noch eine Liste zur Speicherung der Häufigkeiten der Zahlenwerte benötigt. Diese benötigt im Falle der obigen Implementierung einen Speicherplatz von M Feldern. Die Platzkomplexität von Countingsort liegt in $\mathcal{O}(N + M)$.

Weblinks

• Interaktives Java-Applet zur Demonstration