Wanneer uw sorteertaak grote reeksen kleine integers omvat, zoals graden, leeftijden, of quitte codes .. de klassieke vergelijkingsgebaseerde algoritmen zoals QuickSort of MergeSort kunnen als overkill voelen. Deze algoritmen draaien in O(n log n) tijd, maar als het bereik van mogelijke waarden beperkt is, kunt u sorteren in lineaire O(n + k) tijd met Counting Sort. Deze niet-vergelijking sorteeralgoritme maakt gebruik van het feit dat je gebeurtenissen kunt tellen in plaats van elementen te vergelijken, het leveren van een stabiel soort dat zowel eenvoudig als stralend snel is voor de juiste ingangen.

Hoe tellen sorteren werkt

Tellen Sort exploiteert de kennis dat de inputwaarden gehele getallen zijn die uit een klein bereik worden getrokken . In plaats van paarsgewijze vergelijkingen, bouwt het een frequentiehistogram van de waarden en gebruikt het dat histogram om elk element in zijn juiste gesorteerde positie te plaatsen.

De basisaanpak: directe wederopbouw

De eenvoudigste versie van Counting Sort werkt in twee passen:

  1. Tel frequenties . . . Itereert door de invoer array en increërt een teller voor elke waarde die je ziet.
  2. Overschrijf de input . . Loop door de tellerreeks van het kleinste naar het grootste en schrijf het voor elke waarde terug in de invoerarray zo vaak als het aantal.

Dit levert een gesorteerde uitvoer op, maar behoudt niet de relatieve volgorde van duplicaten (het is niet stabiel). Stabiliteit is belangrijk wanneer je op een sleutel sorteert terwijl je de oorspronkelijke volgorde van records met gelijke toetsen bewaart. De stabiele variant, hierna beschreven, is de meest gebruikte in de praktijk.

De Stabiele Variant: Cumulatieve Tellingen

Om Telling Sort stabiel te maken, voegen we een derde pas toe:

  1. Tel frequenties zoals voorheen.
  2. Transformeer de frequentiereeks in een cumulatieve telreeks. Na deze stap houdt het aantal elementen ≤ i.
  3. Iterate de invoer array in omgekeerde (van laatste element tot eerste). Voor elk element, gebruik zijn cumulatieve telling om zijn positie in de uitvoer array te vinden, plaats het, en decrement de telling.

Omdat we in omgekeerde richting doorkruisen, wordt de relatieve orde van gelijke elementen behouden. De uitvoerarray is gescheiden van de invoer, dus deze versie gebruikt O(n) extra ruimte voor de uitvoer, terwijl de basisversie op zijn plaats kan sorteren door de invoer te overschrijven.

Tenuitvoerlegging van het tellen Sorteren in C#

Hieronder staan twee C# implementaties: de basisversie (voor scenario's waar stabiliteit niet nodig is) en de stabiele versie die gebruik maakt van een hulparray. Beide vereisen het vooraf kennen van de maximale waarde.

Basis (niet-stabiel) Telsort

Deze variant sorteert de invoer array direct zonder extra output buffer. Het is geheugen-efficiënt maar niet stabiel.

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

Stabiel tellend Sorteren

De stabiele versie vereist een uitvoerreeks van dezelfde grootte als de invoer. Het gebruikt ook cumulatieve tellingen om elementen correct te plaatsen.

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 beide implementaties is het grootste geheel getal dat in de array verschijnt. Als het werkelijke maximum onbekend is, kun je het berekenen met een voorbereidende scan (O(n)). De stabiele versie geeft een nieuwe gesorteerde array terug, waardoor het origineel ongewijzigd blijft.

Complexiteitsanalyse

Laat n het aantal elementen zijn en k = max

  • Tijd: Telsort loopt in O(n + k) tijd. De telfase is O(n), het cumulatieve voorvoegsel is O(k), en de reconstructie is O(n). Wanneer k O(n is), is het algoritme lineair.
  • Ruimte: De basisversie maakt gebruik van O(k) extra ruimte voor de count array. De stabiele versie maakt gebruik van O(n + k) omdat het ook de output array toewijst. Dit maakt het tellen van Sorteren ongeschikt wanneer het bereik groot is ten opzichte van het aantal items.
  • Vergelijken met andere soorten: Vergelijkingsgebaseerde soorten zoals QuickSort en MergeSort vereisen minstens O(n log n) vergelijkingen. Voor kleine k (bijv. k < 10.000 en n > 100.000), kan tellen Sort orden van grootte sneller zijn.

Wijzigingen en uitbreidingen

Behandeling van negatieve integers

Tellen Sort werkt inheems met niet-negatieve gehele getallen. Om negatieve waarden te hanteren, verschuift u het gehele bereik zodat het minimum nul wordt. Bijvoorbeeld, als getallen variëren van -1000 tot 1000, verrekent elk element met +1000. De telarray heeft dan grootte .

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

Niet-integreersleutels in kaart brengen

Tellen Sort vereist integer keys. Als uw gegevens bestaan uit tekens (bytes), of tellingen die kunnen worden gecast naar gehele getallen, kunt u nog steeds toepassen. Voor grotere objecten, kunt u een integer key extraheren en sorteren van de objecten dienovereenkomstig dit is precies hoe Radix Sort vaak gebruikt Tellen Sorteren als zijn binnenste subroutine.

Radix Sorteer Combo

Radix Sorteer verwerkt cijfers (of bits) individueel, en Telsort is de natuurlijke keuze voor elke pas wanneer de basis (bijv. 10 of 256) klein is. Hierdoor kan lineaire tijdsortering van willekeurige gehele getallen, niet alleen kleine.

Praktische overwegingen in C#

Geheugenvoetafdruk en grote k

De grootste valkuil is het toewijzen van een tellingsarray groter dan het beschikbare geheugen. Bijvoorbeeld, het sorteren van 1000 elementen met een bereik van 1.000.000 afvalruimte. Controleer altijd of k] geen orden van grootte groter is dan n]. Anders gebruik je een vergelijkings- of hybride benadering.

Parallelisme en Span<T>

Voor extreem grote arrays kunt u de telfase parallel maken door de invoer over draden te verdelen. Elke thread telt zijn segment in een private array, en dan worden de gedeeltelijke resultaten samengevoegd. Gebruik makend van en voor de tellingsarray kan hopentoewijzingen verminderen wanneer het bereik klein is.

Randgevallen

  • Leeg array ..terug onmiddellijk.
  • Een element ..sortering is triviaal.
  • Alle identieke waarden .. De telling array heeft één niet-nul ingang; reconstructie loopt in O(n).
  • Grote bereik maar schaarse gegevens . . . Telsort wordt inefficiënt omdat de meeste tellingen nul zijn. Overweeg een hash-gebaseerde counting benadering of Emmer Sorteren.

Uitvoeringsaanbevelingen

Gebruik Telsort wanneer u weet dat de invoer gehele getallen vallen in een klein bereik (bijv., graden 0

Wanneer moet u het telsort gebruiken (en wanneer niet)

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 en prestaties

In een typische benchmark met n = 1.000.000 en k = 1.000, Tellen Sort vult in ongeveer 20

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

Wanneer het bereik groeit tot 10.000, Telt Sort wint nog steeds, maar de marge vernauwt. Voor k = 100.000, het geheugen overhead (≈ 400 KB voor de count array) begint te beschadigen CPU cache, en prestaties kunnen degraderen.

Conclusie

Telsort is een misleidend eenvoudig algoritme dat lineaire prestaties levert wanneer de gegevens aan de beperkingen voldoen. Voor C#-ontwikkelaars die met grote arrays van kleine gehele getallen omgaan, is het een waardevol hulpmiddel dat de sorteertijd drastisch kan verminderen. Houd een oogje op het bereik van uw gegevens: als het klein en bekend is, zal Telsort elk vergelijkingsgebaseerd alternatief overtreffen. Voor meer algemeen gebruik sorteert u de ingebouwde , maar altijd klaar zijn om in Telsort te vallen wanneer de getallen op elkaar aansluiten.

Voor meer informatie, raadpleeg Wikipedia artikel over Tellen Sorteren, de Microsoft docs on Array.Sorteren, en een praktische gids van GeeksforGeeks.