Telling Sort er en effektiv sorteringsalgoritme som brukes for sortering av heltall i et bestemt område. Det fungerer ved å telle antall forekomster av hver verdi og deretter beregne posisjoner for hvert element i den sorterte tabellen. Denne metoden er spesielt nyttig når spekteret av inngangsdata ikke er signifikant større enn antall elementer å sortere.

Hvordan telle sortering fungerer

Algoritmen begynner ved å opprette en tellearray som lagrer frekvensen til hver verdi i inngangsdataene. Den endrer deretter denne tellearrayen for å inneholde de faktiske posisjonene til hvert element i den sorterte utgangen. Til slutt bygger den sorterte tabellen ved å plassere elementene på deres riktige posisjoner basert på tellearrangøren.

Eksempel på beregning

Antak at vi har rekkevidde: [4, 2, 2, 8, 3, 3, 1]. Talingsprosessen resulterer i en rekkevidde:

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

Dette indikerer frekvensen til hvert tall. Algoritmen beregner deretter de kumulative tallene for å bestemme posisjonene:

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

Ved hjelp av disse blir den sorterte rekken: [1, 2, 2, 3, 3, 4, 8].

Søknadsscenarier

Telling Sort er egnet for scenarier der inngangsdata består av heltallsverdier innenfor et kjent, begrenset område. Den brukes ofte i:

  • Sortere studentgrader (f.eks. 0-100)
  • Organisering av data i frekvensanalyse
  • Sortering av små heltall i innebygde systemer
  • Implementere radix-sort som en subrutine

Effektiviteten avhenger av størrelsen på området i forhold til antall elementer. Når området er lite, kan telling Sort overgå sammenligningsbaserte algoritmer som hurtigsort eller flettesort.