Wenn Ihre Sortieraufgabe große Arrays von kleinen Ganzzahlen wie Noten, Alter oder kategorische Codes umfasst, können sich die klassischen vergleichsbasierten Algorithmen wie QuickSort oder MergeSort wie Overkill anfühlen. Diese Algorithmen laufen in O(n log n) Zeit, aber wenn der Bereich der möglichen Werte begrenzt ist, können Sie in linearer O(n + k) Zeit mit Counting Sort sortieren. Dieser Nicht-Vergleichs-Sortieralgorithmus nutzt die Tatsache, dass Sie Ereignisse zählen können, anstatt Elemente zu vergleichen, was eine stabile Sortierung liefert, die sowohl einfach als auch blazingly schnell für die richtigen Eingaben ist.

Wie Counting Sort funktioniert

Counting Sort nutzt das Wissen, dass die Eingangswerte Ganzzahlen aus einem kleinen Bereich sind. Statt paarweise Vergleiche, baut es ein Frequenzhistogramm der Werte und dann verwendet, dass Histogramm jedes Element in seiner richtigen sortierten Position zu platzieren.

Der Grundansatz: Direkte Rekonstruktion

Die einfachste Version von Counting Sort funktioniert in zwei Durchgängen:

  1. Count-Frequenzen – Iterieren Sie durch das Eingabefeld und inkrementieren Sie einen Zähler für jeden Wert, den Sie sehen.
  2. Überschreiben Sie die Eingabe – Gehen Sie durch das Zählerfeld vom kleinsten zum größten und schreiben Sie es für jeden Wert so oft wie seine Zählung zurück in das Eingabefeld.

Dies ergibt eine sortierte Ausgabe, aber not behält die relative Reihenfolge der Duplikate bei (sie ist nicht stabil). Stabilität ist wichtig, wenn Sie nach einem Schlüssel sortieren, während Sie die ursprüngliche Reihenfolge der Datensätze mit gleichen Schlüsseln beibehalten. Die als nächstes beschriebene stabile Variante ist die am häufigsten verwendete in der Praxis.

Die stabile Variante: Kumulative Counts

Um Counting Sort stabil zu machen, fügen wir einen dritten Durchlauf hinzu:

  1. Frequenzen zählen wie zuvor.
  2. Nach diesem Schritt hält die Anzahl der Elemente ≤ i fest.
  3. Das Eingabefeld wird umgekehrt (vom letzten Element zum ersten) wiederholt. Für jedes Element wird die kumulative Anzahl verwendet, um seine Position im Ausgabefeld zu finden, sie zu platzieren und die Anzahl zu verringern.

Da wir in umgekehrter Richtung gehen, bleibt die relative Reihenfolge der gleichen Elemente erhalten. Das Ausgabefeld ist vom Eingang getrennt, so dass diese Version O(n) zusätzlichen Platz für den Ausgang verwendet, während die Basisversion durch Überschreiben des Eingangs ortsunabhängig sortieren kann.

Zählen Sortieren in C#

Im Folgenden sind zwei C#-Implementierungen aufgeführt: die grundlegende In-Place-Version (für Szenarien, in denen Stabilität nicht erforderlich ist) und die stabile Version, die ein Hilfsarray verwendet.

Grundlegende (nicht stabile) Zählung Sortierung

Diese Variante sortiert das Eingabefeld direkt ohne zusätzlichen Ausgangspuffer, ist speichereffizient, aber nicht stabil.

public static void CountingSortBasic(int[] array, int maxValue)
{
 int[] counts = new int[maxValue + 1];

 // Count each element's frequency
 for (int i = 0; i < array.Length; i++)
 {
 counts[array[i]]++;
 }

 // Overwrite the original array in sorted order
 int index = 0;
 for (int value = 0; value <= maxValue; value++)
 {
 while (counts[value]-- > 0)
 {
 array[index++] = value;
 }
 }
}

Stabiles Zählen Sortieren

Die stabile Version erfordert ein Ausgangsarray von der gleichen Größe wie der Eingang und verwendet auch kumulative Zählungen, um Elemente richtig zu positionieren.

public static int[] CountingSortStable(int[] array, int maxValue)
{
 int[] counts = new int[maxValue + 1];
 int[] output = new int[array.Length];

 // Step 1: Count occurrences
 foreach (int num in array)
 {
 counts[num]++;
 }

 // Step 2: Transform counts to cumulative counts
 for (int i = 1; i <= maxValue; i++)
 {
 counts[i] += counts[i - 1];
 }

 // Step 3: Build the output array (iterate input in reverse for stability)
 for (int i = array.Length - 1; i >= 0; i--)
 {
 int value = array[i];
 output[counts[value] - 1] = value;
 counts[value]--;
 }

 return output;
}

In beiden Implementierungen ist die größte ganze Zahl, die im Array erscheint. Wenn das wahre Maximum unbekannt ist, können Sie es mit einem vorbereitenden Scan (O(n)) berechnen. Die stabile Version gibt ein neues sortiertes Array zurück, wobei das Original unverändert bleibt.

Komplexitätsanalyse

Lasst n die Anzahl der Elemente sein und k = max – min + 1 (der Bereich der möglichen Werte).

  • Time: Counting Sort läuft in O(n + k) time. The Counting phase is O(n), the cumulative prefix is O(k), and the reconstruction is O(n). When k is O(n), the algorithm is linear.
  • Space: Die Basisversion verwendet O(k) Extra-Platz für das Zählfeld. Die stabile Version verwendet O(n + k), weil sie auch das Ausgabefeld zuweist.
  • Vergleich mit anderen Sorten: Vergleichsbasierte Sorten wie QuickSort und MergeSort erfordern mindestens O (n log n) Vergleiche. Für kleine k (z. B. k < 10.000 und n > 100.000) kann Zählen Sortieren um Größenordnungen schneller sein.

Variationen und Erweiterungen

Umgang mit Negativintegritäten

Zählen Sort nativ arbeitet mit nicht-negativen Ganzzahlen. Um negative Werte zu behandeln, verschieben Sie den gesamten Bereich, so dass das Minimum Null wird. Zum Beispiel, wenn Zahlen von -1000 bis 1000 reichen, verrechnen Sie jedes Element um +1000. Das Zählfeld hat dann die Größe .

public static int[] CountingSortWithNegative(int[] array)
{
 if (array.Length == 0) return array;

 int min = array.Min();
 int max = array.Max();
 int range = max - min + 1;

 int[] counts = new int[range];
 int[] output = new int[array.Length];

 foreach (int num in array)
 counts[num - min]++;

 for (int i = 1; i < range; i++)
 counts[i] += counts[i - 1];

 for (int i = array.Length - 1; i >= 0; i--)
 {
 int value = array[i];
 output[counts[value - min] - 1] = value;
 counts[value - min]--;
 }

 return output;
}

Mapping nicht-integrierter Schlüssel

Zählen Sie Sortieren erfordert ganzzahlige Schlüssel. Wenn Ihre Daten aus Zeichen (Bytes) oder Aufzählungen bestehen, die in Ganzzahlen umgewandelt werden können, können Sie sie trotzdem anwenden. Für größere Objekte können Sie einen ganzzahligen Schlüssel extrahieren und die Objekte entsprechend sortieren - genau so verwendet Radix Sort oft Zählen Sortieren als sein inneres Unterprogramm.

Radix Sort Combo

Radix Sort verarbeitet Ziffern (oder Bits) einzeln, und Counting Sort ist die natürliche Wahl für jeden Durchlauf, wenn die Basis (z. B. 10 oder 256) klein ist.

Praktische Überlegungen in C#

Memory Footprint und Large K

Die größte Falle ist die Zuweisung eines Zählerfeldes, das größer ist als der verfügbare Speicher. Zum Beispiel, indem man 1.000 Elemente mit einem Bereich von 1.000.000 verschwendet Speicher. Immer überprüfen, ob k nicht um Größenordnungen größer ist als n - ansonsten verwenden Sie eine Vergleichssortierung oder einen Hybridansatz.

Parallelismus und Span<T>

Für extrem große Arrays können Sie die Zählphase parallelisieren, indem Sie die Eingabe über Threads verteilen. Jeder Thread zählt sein Segment in ein privates Array und dann werden die Teilergebnisse aggregiert.

Randgehäuse

  • Leeres Array – sofort zurückkehren.
  • Single element – Sortieren ist trivial.
  • Alle identischen Werte – das Zählfeld hat einen Eintrag von ungleich Null; Rekonstruktion läuft in O(n).
  • Großer Bereich, aber spärliche Daten – Zählen Sort wird ineffizient, weil die meisten Zähleinträge Null sind.

Leistungsempfehlungen

Verwenden Sie Counting Sort, wenn Sie wissen, dass die Eingabe-Integer in einen kleinen Bereich fallen (z. B. Klassen 0–100, Alter 0–120 oder Fehlercodes 0–255).

Wann Zählen Sortieren (und Wann nicht)

SituationRecommendation
Small integer range (k ~ n)Excellent choice – linear time, simple code.
Large integer range (k >> n)Avoid – memory waste and O(k) overhead.
Need stabilityUse the stable variant (cumulative counts).
Strings or objectsConsider Radix Sort or a comparison sort.
Extremely large datasetsCounting Sort can be parallelized; but watch memory.

Benchmarking und Performance

In einem typischen Benchmark mit n = 1.000.000 und k = 1.000, Counting Sort schließt in etwa 20-30% der Zeit von (die Introsort verwendet). Die Lücke erweitert sich, wenn k abnimmt.

n = 1,000,000 | k = 1,000
Array.Sort (QuickSort variant) : 68 ms
CountingSortBasic : 12 ms
CountingSortStable : 18 ms

Wenn der Bereich auf 10.000 anwächst, gewinnt Counting Sort immer noch, aber der Rand verengt sich. Für k = 100.000 beginnt der Speicher-Overhead (≈ 400 KB für das Zählfeld) den CPU-Cache zu verletzen, und die Leistung kann sich verschlechtern.

Schlussfolgerung

Counting Sort ist ein täuschend einfacher Algorithmus, der eine lineare Leistung liefert, wenn Daten ihren Einschränkungen entsprechen. Für C#-Entwickler, die sich mit großen Arrays kleiner Ganzzahlen befassen, ist es ein wertvolles Werkzeug, das die Sortierzeit dramatisch reduzieren kann. Behalten Sie den Bereich Ihrer Daten im Auge: Wenn es klein und bekannt ist, wird Counting Sort jede vergleichende Alternative übertreffen. Verwenden Sie für allgemeinere Sortierungen das eingebaute , aber seien Sie immer bereit, den Counting Sort zu fallen, wenn die Zahlen sich buchstäblich und bildlich anordnen.

Für weitere Informationen lesen Sie den Wikipedia-Artikel zum Zählen von Sort, die Microsoft-Dokumente auf Array.Sort und einen praktischen Leitfaden von GeeksforGeeks.