Countingsort

Countingsort sortiert überhaupt nicht durch Vergleichen. Wissen Sie, dass jeder Wert eine ganze Zahl zwischen, sagen wir, 1 und 40 ist, können Sie einfach zählen, wie viele es von jedem gibt, und aus den Zählerständen ableiten, wohin jeder gehört. Bei einem kleinen Bereich ist das etwa so schnell, wie Sortieren überhaupt sein kann.

Balken einer Liste, ein Streifen mit Zählern, die zeigen, wie oft jeder Wert vorkommt, und eine Pufferzeile, in der jeder Wert seinen eigenen Abschnitt hat
Balken einer Liste, ein Streifen mit Zählern, die zeigen, wie oft jeder Wert vorkommt, und eine Pufferzeile, in der jeder Wert seinen eigenen Abschnitt hat

Zählen

Suchen Sie den kleinsten und den größten Wert und legen Sie für jeden Wert dazwischen einen Zähler an, alle bei null. Lesen Sie die Liste einmal von vorn bis hinten und erhöhen Sie den Zähler jedes Werts, den Sie sehen, um eins. Die Zähler bilden nun ein Histogramm: wie viele Einsen, wie viele Zweien und so weiter. Bei n Werten und k Zählern braucht das n Schritte.

Aufsummieren

Die Werte, die gleich dem kleinsten Wert sind, kommen zuerst, ihr Abschnitt beginnt also auf Platz 1. Der Abschnitt des nächsten Werts beginnt direkt danach, und so weiter: Jeder Abschnitt beginnt nach der Summe aller Zählerstände davor. Diese laufenden Summen, Präfixsummen genannt, machen aus dem Histogramm einen Plan der sortierten Liste. Das braucht k Schritte.

Platzieren

Lesen Sie die Liste ein zweites Mal und verschieben Sie jeden Wert an den nächsten freien Platz seines Abschnitts. Weil die Werte in der Reihenfolge verschoben werden, in der sie vorkommen, behalten gleiche Werte ihre ursprüngliche Reihenfolge: Countingsort ist stabil. Kopieren Sie den Puffer zurück, und die Liste ist sortiert. Die App zeigt, wie jeder Zähler wieder sinkt, während seine Werte platziert werden.

Ein Beispiel

Nehmen Sie 4, 1, 3, 4, 2, 1, 4. Die Zähler für 1 bis 4 enden bei 2, 1, 1 und 3. Das Aufsummieren ergibt die Abschnitte: die Einsen auf Platz 1 und 2, die 2 auf Platz 3, die 3 auf Platz 4 und die Vieren auf Platz 5 bis 7. Werden die Werte in Listenreihenfolge platziert, ergibt sich 1, 1, 2, 3, 4, 4, 4: 7 gezählte Werte, 14 Verschiebungen, 4 Zähler und keine Vergleiche.

Wann es sich lohnt

Der Gesamtaufwand wächst mit n + k. Ist k klein im Vergleich zu n, etwa bei tausend Prüfungsergebnissen von 0 bis 100, ist Countingsort schneller als jedes vergleichsbasierte Sortierverfahren, das etwa n log₂ n Vergleiche braucht. Bei einem großen Bereich ist es verschwenderisch: Ein paar Werte bis zu einer Million brauchen eine Million Zähler. Radixsort löst das, indem es Countingsort einmal pro Ziffer ausführt, sodass jeder Durchgang nur zehn Zähler braucht. Harold Seward beschrieb Countingsort zusammen mit Radixsort 1954.

Selbst ausprobieren

Öffnen Sie die App und drücken Sie „Schritt“. Der Streifen zwischen der Liste und der Pufferzeile zeigt einen Zähler pro Wert. Sehen Sie zu, wie sich die Zähler füllen, während die Liste gelesen wird, wie die Abschnitte im Puffer erscheinen, wenn die Zählerstände aufsummiert werden, und wie die Zähler wieder sinken, während die Werte platziert werden. Wählen Sie wenige verschiedene Werte, um große Abschnitte zu sehen, oder geben Sie weit auseinanderliegende Zahlen ein, um zu sehen, wie viele Zähler ein großer Bereich braucht.

Häufig gestellte Fragen

Welche Zeitkomplexität hat Countingsort?

O(n + k) bei n Werten und k möglichen Werten, dazu O(n + k) zusätzlicher Speicher für die Zähler und den Puffer.

Warum ist Countingsort nicht immer am schnellsten?

Weil seine Kosten vom Wertebereich abhängen, nicht nur von der Anzahl der Werte. Ist der Bereich viel größer als die Liste, bleiben die meisten Zähler bei null, und Zeit und Speicher werden verschwendet.

Kann Countingsort negative Zahlen verarbeiten?

Ja. Die Zähler reichen vom kleinsten bis zum größten Wert, also ziehen Sie den kleinsten Wert ab, um den Index eines Zählers zu erhalten. Die App macht es genauso.

Ist Countingsort stabil?

Ja, solange die Werte in Listenreihenfolge an den nächsten freien Platz ihres Abschnitts verschoben werden. Radixsort ist darauf angewiesen.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Countingsort ausprobieren