Inleiding tot het tellen van het Sorteren

Telsort is een niet-vergelijkend sorteeralgoritme dat uitblinkt bij het sorteren van gehele getallen over een klein, bekend bereik. In tegenstelling tot vergelijkingsgebaseerde soorten zoals Quicksort of Mergesort, die vertrouwen op vergelijkingen van een paarsgewijze element, bepaalt Counting Sort de gesorteerde volgorde door de frequentie van elke afzonderlijke waarde te tellen. Deze benadering geeft lineaire tijd complexiteit onder gunstige omstandigheden, waardoor het een keuze is voor vele prestatiekritische toepassingen waar het invoerdomein beperkt is.

Het algoritme werd voor het eerst beschreven door Harold H. Seward in 1954 en blijft een basistechniek in de computerwetenschap. De eenvoud en efficiëntie maken het ideaal voor taken zoals het sorteren van studentenleeftijden, cijfers, of een geheel getal gegevens met een bescheiden spreiding. Door het benutten van hulpopslag evenredig aan het waardebereik, Counting Sort vermijdt de O(n log n) ondergrens van vergelijking sorteren, bereiken van O(n + k) tijd waar k is het bereik van input waarden.

Hoe tellen sorteren werkt

Het kernmechanisme van Telsort is eenvoudig: het telt hoeveel keer elke waarde in de invoerarray verschijnt, gebruikt dan die telling om de eindpositie van elk element te berekenen. Het proces bestaat uit drie verschillende fasen:

  1. Telling: Maak een telreeks van grootte k (het bereik van invoerwaarden), geïnitialiseerd op nul. Iteer door de invoerarray en verhoog het aantal voor elke waarde.
  2. Computing prefixes: Transformeer de count array in een voorvoegsel sum array, waarbij elk element op index i de cumulatieve telling van elementen kleiner dan of gelijk aan i. Deze stap bepaalt de beginposities voor elke afzonderlijke waarde in de gesorteerde output.
  3. Place elementen: De invoerreeks van rechts naar links doorkruisen (voor stabiliteit), de telarray gebruiken om de juiste index in de uitvoerarray te vinden, het element daar plaatsen en de waarde verlagen. De uiteindelijke uitvoer is een gesorteerde kopie van de invoer.

Het algoritme geeft een nieuwe gesorteerde array terug, waardoor het origineel ongewijzigd blijft. Een variant genaamd in-place Telsort bestaat maar wordt zelden gebruikt omdat het ofwel stabiliteit of ruimte-efficiëntie compromitteert.

Stap voor stap voorbeeld

Overweeg het sorteren van de array [4, 2, 8, 3, 3] waar de waarden variëren van 0 tot 8.

  1. Tel: Tel array grootte 9 (0
  2. Voorvoegsel sommen: Transformeer naar cumulatief → [0,1,3,5,6,6,6,7,7]. Nu vertelt elke waarde ons de uitgangspositie voor dat getal in gesorteerde output.
  3. Uitvoer: Traverse originele array vanaf het einde: eerste element gelezen is 1 → positie = aantal[1] - 1 = 0 → uitvoer[0]=1, afname aantal[1] tot 0. Volgende is 3 → positie = aantal[3] - 1 = 4 → output[4]=3, aantal[3]=4. Ga verder tot alle elementen geplaatst. Einduitvoer: [1,2,2,3,3,4,8].

Dit voorbeeld toont aan hoe Counting Sort vergelijkingen volledig vermijdt, waarbij uitsluitend rekenbewerkingen worden gebruikt.

Computational Complexity

Tijd Complexiteit

  • Beste, gemiddelde en slechtste geval: O(n + k), waarbij n het aantal elementen is en k het bereik van inputwaarden is. Wanneer k klein is ten opzichte van n, draait het algoritme in lineaire tijd.
  • Vergelijken met vergelijkingstypen: Quicksort en Mergesort hebben een gemiddelde complexiteit van O(n log n. Voor n = 106 en k = 1000 is het tellen van Sort (≈ 1,001.000 operaties) ongeveer 13 keer sneller dan een typische O(n log n) soort.

Ruimtecomplexiteit

  • Primair: O(k) voor de telarray, plus O(n) voor de uitvoerarray. Deze geheugenoverhead kan onbetaalbaar zijn als k groot is (bv. 32-bit gehele getallen sorteren waarbij k = 232).
  • Stabiele variant: Vereist een hulpuitvoerreeks van grootte n; in-place varianten offerstabiliteit of gebruik complexe index manipulatie.

Wanneer moet ik tellen gebruiken

Telsort is het meest effectief onder de volgende voorwaarden:

  • De invoer bestaat uit gehele getallen (of gegevens die kunnen worden in kaart gebracht naar een klein geheel getal, zoals tekens of discrete categorieën).
  • Het bereik k is niet significant groter dan n. Een veel voorkomende vuistregel is k ≤ O(n).
  • Het geheugen is niet ernstig beperkt, omdat de tellingsarray en outputbuffer extra ruimte vereisen.
  • Stabiliteit is vereist (bijvoorbeeld sorteren met meerdere toetsen). De standaard implementatie is stabiel wanneer elementen van rechts naar links worden geplaatst.

Uitstekende gebruikscases omvatten sorteerkwaliteiten (0

Beperkingen en overwegingen

Ondanks zijn snelheid, heeft Counting Sort nadelen die de toepasbaarheid beperken:

  • Alleen integer: Het kan geen floating-point nummers of strings direct sorteren tenzij ze worden omgezet in een aaneengesloten geheel getal.
  • Grote reeks: Als k dwergen n.v.t. bijvoorbeeld 100 getallen sorteren met waarden tussen 1 en 107 .De telling array verbruikt enorm geheugen terwijl het sorteren van slechts een paar elementen.
  • Niet-adaptief: Telsort vereist altijd het scannen van de gehele invoer en het opbouwen van de telarray, zelfs als de gegevens al gesorteerd of bijna gesorteerd zijn.
  • Negatieve waarden: Standaard Telsort neemt niet-negatieve gehele getallen aan. Om negatieven te behandelen, kunt u de waarden verschuiven door het minimum af te trekken (het bereik 0 tot max

Deze beperkingen betekenen dat Tellen Sort is een gespecialiseerd hulpmiddel, niet een universele vervanging voor algemene algoritmen.

Vergelijking met gerelateerde sorteeralgoritmen

Telsort vs. Radix Sorteren

Radix Sort breidt het idee uit door cijfers van de minst significante naar de meest significante te sorteren, met een stabiel soort (vaak Tellen Sorteren) op elk cijfer. Terwijl Telen Sort werkt op een pas over het volledige bereik k, voert Radix Sort meerdere passen uit over een kleiner cijferbereik (bv. basis 256), waardoor het geheugengebruik voor grote k wordt verminderd. Bijvoorbeeld, het sorteren van 32-bit gehele getallen met Tellen Sort zou een telreeks van 232 ingangen vereisen, terwijl Radix Sorteren met 8-bit cijfers 256 ingangen per pas en slechts vier pasjes.

Telsort vs. Emmer Sorteren

Bucket Sort verdeelt elementen in een aantal emmers en sorteert elke emmer afzonderlijk (vaak met insertie-sort). Telsort kan worden gezien als een speciaal geval van Emmer Sorteren waar elke emmer overeenkomt met een enkele afzonderlijke waarde. Bucket Sort werkt goed op gelijkmatig gedistribueerde floating-point data, maar Telsort is beperkt tot integer domeinen.

Een stabiele telsort implementeren

Stabiliteit is belangrijk bij het sorteren met één toets en het behoud van de relatieve volgorde van gelijke elementen van een andere toets. Het standaard Telsort algoritme is inherent stabiel wanneer de uitvoerplaatsing loop de invoer van rechts naar links doorkruist. Hier is een tekstuele omtrek van de stabiele variant:

  1. Bereken het aantal array zoals beschreven.
  2. Converteer naar voorvoegsel sommen (posities van elke waarde in de gesorteerde output).
  3. Iterate de invoer array in omgekeerde volgorde. Voor elk element, plaats het op de positie aangegeven door de telling, dan decrement dat telt.

Omdat we elementen vanaf het einde verwerken, gaat het laatste optreden van een bepaalde waarde naar de hoogst mogelijke index, waarbij de relatieve orde behouden blijft. Deze stabiele versie is essentieel voor Radix Sort om op elk cijfer correct te kunnen functioneren.

Praktische toepassingen

  • Onderwijs-indelingssystemen: Honderden examenscores sorteren (bereik 0
  • Bioinformatica: Sorteren van gehele leestellingen of DNA k‐mer frequenties wanneer de alfabetgrootte klein is (A, C, G, T).
  • Database index onderhoud: Sorteren van unieke gehele identificaties in bereik klein genoeg om in het geheugen te passen.
  • Afbeeldingverwerking: Sorteren van histogrammen of kleurintensiteiten (0
  • Sorteren op secundaire sleutel: Gebruikt binnen Radix Sort, dat is het werkpaard voor efficiënte sorteren in vele bibliotheken en talen (bijvoorbeeld, de .NET runtime maakt gebruik van een adaptieve mix van algoritmen, waaronder Tellen Sorteren voor kleine reeksen).

Voor meer over de theorie en varianten, raadpleeg gezaghebbende referenties zoals Wikipedia: Telsort en GeeksforGeeks: Telsort. Praktische vergelijkingen met andere algoritmen zijn te vinden in Briljant.

Telsort optimaliseren voor grote series

Wanneer k groot is maar n ook groot, wordt pure Telsort geheugenintensief. Er bestaan verschillende optimalisaties:

  • Gecomprimeerde zeldzaamheid: Gebruik een hash-kaart in plaats van een aaneengesloten array wanneer het bereik van gebruikte waarden groot is maar het aantal verschillende waarden klein is. Dit handelt constant-tijd indexeren voor hashing overhead maar vermindert het geheugenverbruik.
  • Hybride benaderingen: Tellen combineren met andere algoritmen. Bijvoorbeeld, als het bereik hoger is dan 106, gebruik Radix Sorteren met een basis die cijferbereiken klein houdt.
  • In plaats van varianten: Sommige optimalisaties verminderen extra ruimte naar O(k) zonder een output array, maar ze offeren meestal stabiliteit of cycli nodig om posities te lokaliseren.

Conclusie

Telsort onderscheidt zich als een opmerkelijk efficiënt algoritme voor het sorteren van gehele getallen wanneer het waardebereik klein is ten opzichte van het aantal elementen. De complexiteit van de O(n + k) tijd en lineaire prestaties maken het onmisbaar in scenario's zoals rangsortering, Radix Sort subroutines en toepassingen met begrensde gehele getallen. Echter, het algoritme is afhankelijk van gehele invoer en het geheugen overhead voor grote reeksen herinneren ons eraan dat geen enkele soort is optimaal voor alle situaties. Door te begrijpen wanneer Tellen Excels en wanneer het mislukt kan sneller bouwen, meer voorspelbare systemen. Voor verdere lezing op niet-comparison gebaseerde sorteren, zie TutorialsPoint: Counting Sort[ en Coursera: Counting Sort Lecture[.