Kun lajittelutehtävään liittyy suuria elementtejä pieniä kokonaislukuja. Kuten arvosanat, ikäluokat tai kategoriakoodit.Klassinen vertailuun perustuva algoritmi, kuten QuickSort tai MergeSort, voi tuntua liioittelulta. Nämä algoritmit toimivat O(n log n) ajassa, mutta jos mahdollisten arvojen valikoima on rajallinen, voit lajitella lineaarisesti O(n + k) aikaa [ Counting Sort]. Tämä ei-vertailu lajittelualgoritmi vipuvoimaa sitä, että voit laskea tapahtumia eikä vertailla elementtejä, joka on vakaa laji, joka on sekä yksinkertainen ja räikeä nopeasti oikeat panokset.

Miten lasken Lajitelma toimii

Counting Sort hyödyntää tietoa, että syötearvot ovat kokonaislukuja peräisin pienestä . Sen sijaan parivertailuja, se rakentaa taajuus histogrammi arvoja ja sitten käyttää että histogrammi sijoittaa kunkin elementti sen oikea lajiteltu sijainti.

Peruslähestymistapa: suora jälleenrakennus

Yksinkertaisin versio Counting Järjestä toimii kahdessa syöttöä:

  1. Korkeat taajuudet [ ... Iteroida sisääntulojärjestelmän läpi ja lisätä laskuri jokaista näkemääsi arvoa varten.
  2. Overwrite input[ ... .....................................................................................................................................................................................................................................

Tämä tuottaa lajitellun tuloksen, mutta ei [] säilytä kopioiden suhteellista järjestystä (se ei ole vakaa). Vakaus on tärkeää, kun lajittelet avainta samalla kun säilytät alkuperäisen järjestys tietueiden kanssa samat avaimet. Seuraavaksi kuvattu vakaa variantti on yksi yleisimmin käytetty käytännössä.

Vakaa variantti: kumulatiiviset luvut

Jotta Counting Sot vakaa, lisäämme kolmannen syöttö:

  1. Laske taajuudet kuten ennenkin.
  2. Muuntaa taajuusmatriisi kumulatiiviseksi laskentamatriisiksi. Tämän vaiheen jälkeen on elementtien lukumäärä ≤ i.
  3. Iteroida syöttöjärjestelmä käänteisessä (viimeisestä elementistä ensimmäiseen). Käytä kunkin elementin, sen kumulatiivinen kreivi löytää sijaintinsa lähtö array, aseta se, ja decrement kreivi.

Koska kuljemme taaksepäin, suhteellinen järjestys tasa-aineiden säilytetään. Tulostematriisi on erillinen syötteestä, joten tämä versio käyttää O(n) lisätilaa ulostuloon, kun taas perusversio voi lajitella paikan päälle kirjoittamalla syötteen.

Toteutuslaskenta C#

Alla on kaksi C#-toteutusta: perusversio (jos vakaus on tarpeetonta) ja vakaa versio, joka käyttää apujärjestelmää. Molemmat vaativat suurimman arvon etukäteen tuntemista.

Perus (ei-vakaa)

Tämä variantti lajittelee syöttöjärjestelmän suoraan ilman lisäulostulopuskuria. Se on muistitehokas mutta ei vakaa.

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

Vakaa laskentajärjestys

Vakaa versio edellyttää samankokoista lähtöä kuin syöte. Se käyttää myös kumulatiivisia arvoja sijainti-elementteihin oikein.

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

Molemmissa implementeissä [ on suurin kokonaisluku, joka näkyy matriisissa. Jos todellinen maksimi on tuntematon, voit laskea sen valmistelevalla skannauksella (O(n)).Tavanmukainen versio palauttaa uuden lajitellun ryhmän jättäen alkuperäisen ennalleen.

Kompleksisuusanalyysi

Olkoon n elementtien lukumäärä ja k[ = max . . . min + 1 (mahdollisten arvojen vaihteluväli).

  • Aika:[] Laskujärjestys toimii ]O(n + k). Laskuvaihe on O(n), kumulatiivinen etuliite on O(k), ja korjaus on O(n). Kun k on O(n), algoritmi on lineaarinen.
  • Avaruus:[ Perusversio käyttää O(k) lisätilaa laskentaan. Vakaa versio käyttää O(n + k) koska se jakaa myös lähtömatriisin. Tämä tekee Counting Sort sopimattomasta, kun vaihteluväli on suuri suhteessa kappaleiden määrään.
  • Vertailu muunlaisiin:[ Vertailupohjaiset lajit kuten QuickSort ja MergeSort vaativat vähintään O(n log n) vertailuja. Pienen k:n (esim. k < 10 000 ja n > 100 000) osalta Counting Sort voi olla suuruusluokkaa nopeampi.

Muutokset ja laajennukset

Negatiivisten tekijöiden käsittely

Counting Järjestä natiivi toimii ei-negatiivisia kokonaislukuja. Voit käsitellä negatiivisia arvoja, siirtää koko vaihteluvälin niin, että minimi tulee nolla. Esimerkiksi, jos numerot vaihtelevat -1000 1000, korvata jokaisen osan +1000. Count array sitten on koko .

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

Kartta ei-kokoavaimet

Counting Sort edellyttää kokonaisluku avaimet. Jos tiedot koostuvat merkkejä (tavuja), tai numeroinnit, jotka voidaan heittää kokonaislukuja, voit silti soveltaa sitä. Suurempia esineitä, voit poimia kokonaisluku avain ja lajitella objektit vastaavasti.Tämä on juuri näin Radix Järjestä usein käyttää Counting Järjestä sen sisäisenä aliohjelma.

Radix Järjestä Combo

Radix Järjestä prosessit numerot (tai bitit) erikseen, ja Counting Sort on luonnollinen valinta kunkin sola, kun pohja (esim. 10 tai 256) on pieni. Tämä mahdollistaa lineaarisen-aika lajittelu mielivaltaisia kokonaislukuja, ei vain pieniä.

Käytännön pohdintoja C#:ssa

Muistin jalanjälki ja suuri k

Suurin ansa on jakaa laskenta-alue suurempi kuin käytettävissä muisti. Esimerkiksi lajittelu 1000 elementtiä, joiden valikoima on 1000 000 jätteitä tilaa. Aina tarkistaa, että [k] ei ole suuruusluokka suurempi kuin []n[[]]].Muuta käyttää vertailun laji tai hybridi lähestymistapa.

Rinnakkaishoito ja span < T >

Erittäin suurille rakenteille voit sovittaa laskentavaiheen jakamalla syötteen säikeille. Jokainen lanka laskee segmentinsä yksityiseksi matriisiksi, ja sitten osittaiset tulokset yhdistetään. Käyttämällä ja laskenta-alueelle voi vähentää kasajakoja, kun alue on pieni.

Syrjäistapaukset

  • Tyhjä matriisi Palaa välittömästi.
  • Yksinkertainen osa[ .
  • Kaikki samat arvot[ . ... ...
  • Suuren mutta harvan tiedon [ ... .....................................................................................................................................................................................................................................

Suorituskykyä koskevat suositukset

Käytä Counting Sortia, kun tiedät syöte kokonaislukujen putoavan pieneen vaihteluväliin (esim. luokat 0..100, ikä 0..120 tai virhekoodit 0...2555). Isompien alueiden osalta harkitse Radix Sortia tai hybridiä, joka palaa takaisin QuickSortin korkea-aluejakoihin.

Milloin käytetään laskentaa Järjestä (ja milloin ei)

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.

Vertailuanalyysi ja tulos

Tyypillisessä vertailussa n = 1 000 000 ja k = 1 000, Counting Sort valmistuu noin 20 .30% [[FLT: 9]] ajasta (joka käyttää introsorttia).

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

Kun vaihteluväli kasvaa 10 000, Counting Sort voittaa vielä, mutta marginaali kapenee. K = 100 000, muistin yläpuolella (...400 KB lukujonolle) alkaa satuttaa CPU välimuistia, ja suorituskyky voi heikentyä.

Päätelmä

Counting Sort on petollisen yksinkertainen algoritmi, joka tuottaa lineaarista suorituskykyä, kun data sopii sen rajoitteisiin. C# kehittäjille, jotka käsittelevät suuria elementtejä pieniä kokonaislukuja, se on arvokas työkalu, joka voi dramaattisesti vähentää lajitteluaikaa. Pidä silmällä tietosi valikoimaa: jos se on pieni ja tunnettu, Counting Sort ylittää vertailuun perustuvan vaihtoehdon. Yleisempään-tarkoitukseen lajitteluun, käytä sisäänrakennettua , mutta aina ole valmis pudottamaan Counting Sort, kun numerot riviin .

Lisätietoja saa ]Wikipedia-artikkelista, joka koskee laskentaa [, Microsoft-dokumenteista Arrayssa.Sort, ja käytännön opas []GeeksitforGeeeksit.