Direkt zum Inhalt

Lexikon der Mathematik: countingsort

spezielles Sortierverfahren zum Sortieren von n ganzen Zahlen eines Bereiches [1 … k] für eine feste natürliche Zahl k.

Das Verfahren besteht aus drei Schritten. Im ersten Schritt wird für jedes i ∈ {1, …, k} gezählt, wieviele Elemente der Eingabefolge, die in einem Feld A[1 … n] der Größe n abgespeichert ist, den Schlüssel i haben. Dieses Zwischenergebnis wird in einem Feld C der Größe k abgespeichert. Die Komponente C[i] speichere die Anzahl der Elemente der Eingabefolge mit dem Schlüssel i.

Im zweiten Schritt wird für alle i ∈ {1, …, k} die Anzahl der Elemente der Eingabefolge, die einen Schlüssel kleiner gleich i haben, berechnet. Dies erfolgt sequentiell, beginnend mit i = 2 bis hin zu i = n durch Setzen der iten Komponente C[i] von C auf C[i] + C[i – 1].

Im dritten Schritt wird die Eingabefolge (beginnend mit dem letzten Element A[n] der Eingabefolge) durch direktes Einreihen in ein Feld B[1n] der Größe n sortiert. Dies erfolgt jeweils durch die Befehlssequenz

\begin{eqnarray}\begin{array}{c}\text{B[C[A[j]]]:=A[j];}\\ \text{C[A[j]]:=C[A[j]]-1}\text{.}\end{array}\end{eqnarray}

Countingsort ist ein stabiles Sortierverfahren. Es benötigt höchstens c1 · n + c2 · k Schritte, um eine Eingabefolge der Länge n zu sortieren. Hierbei bezeichnen c1 und c2 zwei von n und k unabhängige Konstanten.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos