Når sorteringsoppgaven involverer store rekker av små heltal ⁇ som kvaliteter, aldre eller kategorisk kode ⁇ kan de klassiske sammenligningsbaserte algoritmene som QuickSort eller MergeSort føles som overkill. Disse algoritmene kjører i O(n log n) tid, men hvis intervallet av mulige verdier er begrenset, kan du sortere i lineær O(n + k) tid med [[FLT: 0]]Counting Sort[FLT: 1]. Denne ikke-komparasjon sorteringsalgoritmen utnytter det faktum at du kan telle forekomster i stedet for å sammenligne elementer, levere en stabil type som er både enkel og blazing raskt for de riktige inngangene.

Hvordan telle sortering fungerer

I stedet for parvis sammenligninger, bygger det en frekvens histogram av verdiene og bruker deretter det histogrammet til å plassere hvert element i sin riktige sorterte posisjon.

Grunnleggende tilnærming: Direkte rekonstruksjon

Den enkleste versjonen av Counting Sort fungerer i to passeringer:

  1. ] ⁇ Iterere gjennom innmatingsarrangementet og trinn en teller for hver verdi du ser.
  2. Overskriv inngangen ⁇ Gå gjennom kontraarrangøren fra minste til største og for hver verdi, skriv den tilbake til innmatingsarrangøren så mange ganger som dets teller.

Dette gir en sortert utgang, men gjør ikke bevarer den relative rekkefølgen av dupliker (det er ikke stabilt). Stabilitet betyr når du sorterer på en nøkkel mens du holder den opprinnelige rekkefølgen av poster med like nøkler. Den stabile varianten, som er beskrevet neste, er den som er mest brukt i praksis.

Den stabile varianten: Kumulative counts

For å gjøre telling Sortering stabil, legger vi til en tredje pass:

  1. Tal frekvenser som tidligere.
  2. Omforme frekvensen til en kumulativ tallarrangering. Etter dette trinnet holder antall elementer ≤ ]i].
  3. Iterer inngangsarray i omvendt (fra siste element til første). For hvert element, bruk det kumulative antall til å finne sin posisjon i utgangsarray, plassere det og dekremer tellingen.

Fordi vi krysser omvendt, er den relative rekkefølgen av like elementer bevart. Utgangsarrangøren er adskilt fra inngangen, så denne versjonen bruker O(n) ekstra plass for utgangen, mens den grunnleggende versjonen kan sortere på plass ved å overskrive inngangen.

Sorter i C#

Nedenfor er to C#-implementasjoner: den grunnleggende versjon på plass (for scenarier der stabilitet er unødvendig) og den stabile versjonen som bruker en hjelpearray. Begge krever å vite maksimalverdien på forhånd.

Grunnleggende (Non ⁇ Stable) Counting Sort

Denne varianten sorterer inngangsarray direkte uten ekstra utgangsbuffer. Det er minne-effektivt, men ikke stabilt.

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;
 }
 }
}

Stabil Counting Sort

Den stabile versjonen krever en utgangslinje av samme størrelse som inngangen. Den bruker også kumulative teljinger til posisjonselementer riktig.

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;
}

I begge implementeringer er det største heiltalet som vises i tabellen. Hvis det sanne maksimumet er ukjent, kan du beregne det med en forberedende skann (O(n)). Den stabile versjonen returnerer en ny sortert rekkefølge, slik at den opprinnelige uendret.

Kompleksitetsanalyse

La n være antall elementer og k] = max ⁇ min + 1 (området for mulige verdier).

  • Tid:] Tellingssortering kjører i O(n + k)] tid. Countingfasen er O(n), det kumulative prefikset er O(k), og rekonstruksjonen er O(n). Når k er O(n), algoritmen er lineær.
  • Space: Den grunnleggende versjonen bruker ekstra plass til tellearrangøren O(k). Den stabile versjonen bruker O(n + k) fordi den også tildeler utgangsarrangøren. Dette gjør Counting Sorter upassende når intervallet er stort i forhold til antall elementer.
  • Samsvar med andre typer: Sammenligning ⁇ baserte typer som QuickSort og MergeSort krever minst O(n log n) sammenligninger. For små k (f.eks. k < 10.000 og n > 100.000), kan telling Sort være størrelsesorden raskere.

Variasjoner og utvidelser

Håndtering av negative heltal

Sortering av innfødte fungerer med ikke-negative heltal. For å håndtere negative verdier, skift hele området så minste blir null. For eksempel, hvis tallene varierer fra -1000 til 1000, forskyv hvert element med + 1000. Tellingstabellen har deretter størrelse .

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;
}

Kartlegging ikke-heltalsnøkler

Telling Sort krever heltallstastene. Hvis dataene dine består av tegn (byte) eller opptellinger som kan kastes på heltalls, kan du fortsatt bruke dem. For større objekter kan du trekke ut en heltallsnøkkel og sortere objektene i henhold til dette ⁇ dette er nøyaktig hvordan Radix Sort ofte bruker telling Sorter som dens indre subrutine.

Radix Sorter kombinasjon

Radix Sort behandler siffer (eller biter) individuelt, og telling Sort er det naturlige valget for hvert pass når basen (f.eks. 10 eller 256) er liten. Dette gjør det mulig å sortere lineær-tid på vilkårlige heltal, ikke bare små.

Praktiske vurderinger i C#

Minne Fotavtrykk og Stor K

Den største gropefall er å bestemme en telleliste større enn det tilgjengelige minnet. For eksempel er sortering av 1000 elementer med et område på 1.000.000 avfallsplass. Alltid verifisere at k] ikke er størrelsesorden større enn ]n]-på annen måte bruke en sammenligningstype eller en hybrid tilnærming.

Parallalitet og Span<T>

For ekstremt store tabeller kan du parallellisere tellingsfasen ved å dele innspillet på tvers av tråder. Hver tråd teller segmentet i en privat rekkevidde, og deretter blir de delvise resultatene samlet. Ved hjelp av og for tellingsarrangementet kan redusere haugfordelingene når intervallet er lite.

Kantsaker

  • Tom array] ⁇ retur umiddelbart.
  • Enkelt element ⁇ sortering er triviell.
  • Alle identiske verdier] ⁇ count array har én ikke-null oppføring; rekonstruksjon kjører i O(n).
  • Stor rekkevidde men sparsomme data ⁇ Tellingssortering blir ineffektiv fordi de fleste telleoppføringer er null. Tenk på en hash-basert telletilnærming eller Bucket Sort.

Prestasjonsanbefalinger

Bruk telling Sorter når du vet inngangsheltal faller i et lite område (f.eks. grader 0 ⁇ 100, alder 0 ⁇ 20 eller feilkoder 0 ⁇ 255). For større områder, vurdere Radix Sort eller en hybrid som faller tilbake til QuickSort for høy-range partisjoner.

Når du skal bruke telling (og når ikke å)

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 og ytelse

I en typisk referanse med n = 1.000.000 og k = 1000, fullføres tellingssortering i ca. 20 ⁇ 30% av tiden som tas av (som bruker introsort). Gapet utvides etter hvert som k reduseres. Nedenfor er en omtrentlig sammenligning (utførelsestider på en moderne CPU med .NET 8):

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

Når rekkevidden vokser til 10.000, vinner likevel tellingssorteringen, men marginen smalner. For k = 100.000 begynner minneoverskuddet ( ⁇ 400 KB for tellingsarray) å skade CPU-cache, og ytelsen kan nedgradere.

Konklusjon

Counting Sort er en vildledende enkel algoritme som leverer lineær ytelse når data passer til sine begrensninger. For C# utviklere som håndterer store rekker av små heltal, er det et verdifullt verktøy som kan dramatisk redusere sorteringstiden. Hold øye med spekteret av dataene dine: Hvis det er lite og kjent, vil Counting Sort overgå enhver sammenligning -basert alternativ. For mer generell - formål sortering, bruk den innebygde - i , men alltid være klar til å slippe i Counting Sort når tallene linjen opp - litteralt og figurativt.

For videre lesing, se ]Wikipedia artikkel om Counting Sort, ]Microsoft docs on Array.Sort] og en praktisk guide fra GeeksforGeeks].