Innføring til telling

Counting Sort er en ikke-komparasjonbasert sorteringsalgoritme som utmerker seg når sorteringsheltal over et lite, kjent område. I motsetning til sammenligningsbaserte typer som Quicksort eller Mergesort, som er avhengig av sammenlikninger av parvise element, bestemmer Counting Sort den sorterte rekkefølgen ved å telle frekvensen av hver bestemt verdi. Denne tilnærmingen gir lineær tidskompleksitet under gunstige forhold, noe som gjør det til et go-to-valg for mange ytelseskritiske programmer der inngangsdomene er begrenset.

Algoritmen ble først beskrevet av Harold H. Seward i 1954 og forblir en grunnleggende teknikk i datavitenskap. Dens enkelhet og effektivitet gjør det ideelt for oppgaver som sortering studentalder, karakterer eller alle heltaldata med en beskjeden spredning. Ved å utnytte hjelpelagring proporsjonal til verdiområdet, unngår Counting Sort den O(n log n) lavere grensen for sammenligning sortering, oppnå O(n + k) tid hvor k er spekteret av inngangsverdier.

Hvordan å telle sortering fungerer

Kjernemekanismen i tellingssortering er enkel: det teller hvor mange ganger hver verdi vises i inngangsarrangøren, og deretter bruker det som teller for å beregne hvert elements endelige posisjon. Prosessen består av tre forskjellige faser:

  1. Counting: Opprett en rekke størrelser k (området for inngangsverdier), initiert til null. Iterere gjennom innmatingsarrayet og auker tellingen for hver verdi.
  2. Komputerende prefiks: Transformere countarray til en prefiks sumararray, der hvert element ved indeksen jeg har det kumulative antall elementer mindre enn eller lik i. Dette trinnet bestemmer utgangsposisjonene for hver bestemt verdi i den sorterte utgangen.
  3. Placing elementer: Traverse inngangsarray fra høyre til venstre (for stabilitet), bruk tellingsarray til å finne riktig indeks i utgangsarrangøren, plassere elementet der og dekrementere tellingen. Den endelige utgangen er en sortert kopi av inngangen.

Algoritmen returnerer en ny sortert rekkefølge, som etterlater den originale uendret. En variant kalt på plass Counting Sort eksisterer, men brukes sjelden fordi den kompromisser enten stabilitet eller romeffektivitet.

Trinn ⁇ for ⁇ Step eksempel

Vurder å sortere rekkefølgen [4, 2, 2, 8, 3, 3, 1] der verdier varierer fra 0 til 8.

  1. Count: Count array size 9 (0 ⁇ 8) → [0,1,2,2,1,1,0,0,1]. (Index 1 vises én gang, indeks 2 to ganger, indeks 3 to ganger, indeks 4 én gang, indeks 8 én gang.)
  2. Prefix summer: Transformer til kumulativ → [0,1,3,5,6,6,6,6,7]. Nå forteller hver verdi oss startposisjonen for det tallet i sortert utdata.
  3. Utgangspunkt: Traverse originalt array fra slutten: første element lest er 1 → posisjon = count[1] - 1 = 0 → utgang[0]=1, nedgangstall[1] til 0. Neste er 3 → posisjon = count[3] - 1 = 4 → utgang[4]=3, count[3]=4. Fortsett til alle elementer plassert. Sluttutgang: [1,2,2,3,3,4,8].

Dette eksemplet viser hvordan tellingssortering unngår sammenligninger helt og holdent, avhengig av aritmetiske operasjoner.

Beregningskompleksitet

Tidskompleksitet

  • Best, Gjennomsnittlig og verste tilfelle: O(n + k), hvor n er antall elementer og k er spekteret av inngangsverdier. Når k er liten i forhold til n, kjører algoritmen i lineær tid.
  • Komparasjon til sammenligningstyper: Hurtigsortering og fusjonssort har O(n log n) gjennomsnittlig kompleksitet. For n = 106 og k = 1000, tellingssortering ( ⁇ 1.001 000 operasjoner) er ca. 13 ganger raskere enn en typisk O(n logg n)-sort.

Space Complexity

  • Primary: O(k) for tellingsarray, pluss O(n) for utgangsarray. Dette minneoverskuddet kan være forbudt hvis k er stort (f.eks. sortering 32-bit heltall der k = 232).
  • Stable variant: krever et hjelpeutgangsspekter av størrelse n; på plass varianter ofre stabilitet eller bruke kompleks indeksmanipulering.

Når du skal bruke telling

Counting Sort er mest effektiv under følgende betingelser:

  • Inngangen består av heltallsverdier (eller data som kan kartlegges til et lite heltallsområde, som for eksempel tegn eller diskrete kategorier).
  • Området k er ikke signifikant større enn n. En vanlig tommelfingerregel er k ≤ O(n).
  • Minne er ikke alvorlig begrenset, fordi tellingsarray og utgangsbuffer krever ekstra plass.
  • Stabilitet kreves (f.eks. sortering med flere nøkler). Standard implementering er stabil når elementene plasseres fra høyre til venstre.

Utmerket brukstilfeller inkluderer sorteringskvaliteter (0-100), aldersgrupper (0-20), produktkategorier (opp til noen få hundre SKUs), eller som en subrutine i Radix Sort.

Begrensninger og hensyn

Til tross for hastigheten har Counting Sort ulemper som begrenser bruken av den:

  • Bareheltal: Den kan ikke sortere flytende tall eller strenger direkte med mindre de konverteres til et sammenhengende heltallssett.
  • Stort område: Hvis k dvergene n ⁇ for eksempel, sorterer 100 tall med verdier mellom 1 og 107 ⁇ tar countarray enormt minne mens sortering bare noen få elementer.
  • Non ⁇ adaptiv: Counting Sort krever alltid å skanne hele inngangen og bygge tellingsarrangementet, selv om dataene allerede er sortert eller nesten sortert.
  • Negative verdier: Standard tellingssortering antar ikke-negative heltall. For å håndtere negative, kan du flytte verdiene ved å trekke fra minimum (gjør området 0 til max ⁇ min).

Disse begrensningene betyr å telle sortering er et spesialisert verktøy, ikke en universell erstatning for generelle algoritmer.

Sammenligning med Relaterte sorteringsalgoritmer

Sorter mot Radix Sorter

Radix Sort utvider ideen ved å sortere siffer fra minst signifikant til mest signifikant, ved hjelp av en stabil sortering (ofte tellesortering) på hvert siffer. Mens telling av sortering fungerer på ett passerer over hele området k, utfører Radix Sort flere passeringer over et mindre sifferområde (f.eks. base 256), reduserer minnebruken for store k. For eksempel vil sortering av 32- bits heltall med tellingssorter kreve en rekke 232 oppføringer, mens Radix Sort med 8-bits siffer krever 256 oppføringer per pass og bare fire passeringer.

Sorter mot Bucket Sorter

Bucket Sort distribuerer elementer til et antall bøtter og sorterer hver bøtte individuelt (ofte med innsettingssorter). Telling Sort kan ses som et spesielt tilfelle av Bucket Sort der hver bøtte tilsvarer en enkelt bestemt verdi. Bucket Sort fungerer godt på jevnt fordelt flytende data, men Counting Sort er begrenset til heltallsdomener.

Implementere en stabil teller-sort

Stabilitet er viktig når sorteringen med én nøkkel bevares mens den relative rekkefølgen av like elementer fra en annen nøkkel. Standard-telling- sorteringsalgoritmen er iboende stabil når utgangsplasseringssløyfen krysser inngangen fra høyre til venstre. Her er en tekstform av den stabile varianten:

  1. Beregne count array som beskrevet.
  2. Konverter til prefiks summer (posisjoner av hver verdi i den sorterte utgangen).
  3. Iterer inngangsarray i omvendt rekkefølge. For hvert element plasserer det i den posisjonen som er angitt av dets antall, og deretter dekrement som teller.

Fordi vi behandler elementer fra slutten, går den siste forekomsten av en gitt verdi inn i den høyeste mulige indeksen, bevare relativ rekkefølge. Denne stabile versjonen er avgjørende for Radix Sort å fungere riktig på hvert siffer.

Praktiske applikasjoner

  • Utdanningssystemer: Sortere hundrevis av eksamenspoeng (intervall 0 ⁇ 100) i O(n) tid.
  • Bioinformatikk: Sortering av heltal lesningstall eller DNA k ⁇ mer frekvenser når alfabetstørrelsen er liten (A, C, G, T).
  • Databaseindeksvedlikehold: Sortere unike heltallsidentifikatorer i området som er små nok til å passe i minnet.
  • Imagebehandling: Sortere histogram bins eller farge intense (0-255) når du bygger opp tabeller.
  • Sortering etter sekundær nøkkel: Brukt inne i Radix Sort, som er arbeidshesten for effektiv sortering i mange biblioteker og språk (f.eks. bruker .NET-kjøretiden en adaptiv blanding av algoritmer inkludert tellingssortering for små områder).

For mer om teorien og variantene, konsultere autoritative referanser som ]Wikipedia: Counting Sort og ]GeeksforGeeks: Counting Sort. Praktiske sammenligninger med andre algoritmer kan finnes i Brilliants Counting Sort Article.

Optimering av telling av store områder

Når k er stor, men n er også stor, blir ren telling Sort minne-intensiv. Flere optimeringer eksisterer:

  • Komprimert sparsomhet: Bruk et hashkart i stedet for en sammenhengende rekkevidde når rekkevidden av brukte verdier er stor, men antall forskjellige verdier er lite. Dette handler konstant tidsindeksering for hashing overhead men reduserer minneforbruket.
  • Hybrid tilnærminger: Kombinere telling Sorter med andre algoritmer. For eksempel, hvis området overstiger 106, bruk Radix Sort med en base som holder siffer intervaller små.
  • I ⁇ place varianter: Noen optimeringer reduserer ekstra plass til O(k) uten utgangsarray, men de vanligvis ofre stabilitet eller krever sykluser for å lokalisere posisjoner.

Konklusjon

Tallsortering skiller seg ut som en bemerkelsesverdig effektiv algoritme for sortering av heltall når verdiområdet er lite i forhold til antall elementer. Dens O(n + k) tidskompleksitet og lineær ytelse gjør det uunnværlig i scenarier som klassesortering, Radix Sort subrutiner og programmer med begrensede heltallstaster. Men algoritmens avhengighet av heiltalsinngang og minneoverskudd i store rekkevidde minner oss om at ingen enkelt sort er optimal for alle situasjoner. Ved å forstå når telling av sorteringsutmerkelser ⁇ og når det mislykkes ⁇ developerers kan bygge raskere, mer forutsigbare systemer. For ytterligere lesing på ikke-komparisonbasert sortering, se ]TutorialsPoint: Counting Sort] og