Counting Sort on tehokas lajittelualgoritmi, jota käytetään kokonaislukujen lajitteluun tietyn vaihteluvälin sisällä. Se toimii laskemalla kunkin arvon esiintymisten määrän ja laskemalla sitten kunkin elementtien positiot lajiteltuun matriisiin. Tämä menetelmä on erityisen hyödyllinen, kun syöttötietojen valikoima ei ole merkittävästi suurempi kuin lajiteltavan osan määrä.

Miten lasken Lajitelma toimii

Algoritmi alkaa luomalla laskenta-asetin, joka tallentaa kunkin arvon taajuuden syöttötiedoissa. Se muuttaa tätä laskenta-asetetta siten, että se sisältää kunkin elementtien todelliset kannat lajitellussa lähtömuodossa. Lopuksi se rakentaa lajitellun matriisin asettamalla elementit niiden oikeisiin asemiin, jotka perustuvat laskenta-asetteeseen.

Laskelmaesimerkki

Oletetaan, että meillä on matriisi: [4, 2, 2, 8, 3, 3, 1]. Arvojen vaihteluväli on 1-8. Laskentaprosessi johtaa laskenta-asteikko:

[0, 1, 2, 2, 1, 0, 0, 0, 1]

Tämä osoittaa kunkin numeron taajuuden. Algoritmi laskee sitten kumulatiiviset arvot määrittää positiot:

[0, 1, 3, 5, 6, 6, 6, 7]

Näiden avulla lajiteltu matriisi tulee: [1, 2, 2, 3, 3, 4, 8].

Sovellusskenaariot

Counting Sort sopii skenaarioihin, joissa syötetiedot koostuvat kokonaislukuja sisällä tunnettu, rajoitettu vaihteluväli. Sitä käytetään usein:

  • Opiskelija-asteiden lajittelu (esim. 0-100)
  • Tietojen järjestäminen taajuusanalyysissä
  • Pienien kokonaislukujen lajittelu sulautetuissa järjestelmissä
  • Toteutussäteiden lajitteleminen aliohjelmaksi

Sen tehokkuus riippuu alueen koosta suhteessa alkuaineiden määrään. Kun alue on pieni, Counting Sort voi ylittää vertailuun perustuvat algoritmit, kuten quicksort tai sulfacesort.