Counting sort
Counting sort sorteert helemaal niet door waarden te vergelijken. Als je weet dat elke waarde een geheel getal is tussen bijvoorbeeld 1 en 40, kun je gewoon tellen hoeveel er van elk zijn, en uit die aantallen afleiden waar elke waarde hoort. Bij een klein bereik is dat ongeveer zo snel als sorteren kan zijn.
Tellen
Zoek de kleinste en grootste waarde en maak één teller voor elke waarde daartussen, allemaal beginnend bij nul. Lees de lijst één keer van begin tot eind en tel één op bij de teller van elke waarde die je ziet. De tellers vormen nu een histogram: hoeveel 1'en, hoeveel 2'en, enzovoort. Met n waarden en k tellers kost dit n stappen.
Optellen
De waarden gelijk aan de kleinste waarde komen eerst, dus hun reeks begint op plek 1. De reeks van de volgende waarde begint direct daarna, enzovoort: elke reeks begint na de som van alle aantallen ervoor. Deze lopende totalen, prefixsommen genoemd, maken van het histogram een kaart van de gesorteerde lijst. Dit kost k stappen.
Plaatsen
Lees de lijst een tweede keer en zet elke waarde op de volgende vrije plek in haar reeks. Omdat de waarden worden verplaatst in de volgorde waarin ze voorkomen, houden gelijke waarden hun oorspronkelijke volgorde: counting sort is stabiel. Kopieer de buffer terug en de lijst is gesorteerd. De app laat elke teller weer dalen terwijl zijn waarden geplaatst worden.
Een voorbeeld
Neem 4, 1, 3, 4, 2, 1, 4. De tellers voor 1 t/m 4 eindigen op 2, 1, 1 en 3. Optellen geeft de reeksen: de 1'en op plek 1 en 2, de 2 op plek 3, de 3 op plek 4 en de 4'en op plek 5 t/m 7. De waarden in lijstvolgorde plaatsen geeft 1, 1, 2, 3, 4, 4, 4: 7 waarden geteld, 14 verplaatsingen, 4 tellers en geen vergelijkingen.
Wanneer gebruik je het
Het totale werk groeit met n + k. Als k klein is vergeleken met n, zoals duizend examenscores van 0 tot 100, is counting sort sneller dan elk vergelijkend sorteeralgoritme, dat ongeveer n log₂ n vergelijkingen nodig heeft. Bij een groot bereik is het verspillend: een paar waarden verspreid tot een miljoen hebben een miljoen tellers nodig. Radix sort lost dat op door counting sort één keer per cijfer te draaien, zodat elke ronde maar tien tellers nodig heeft. Harold Seward beschreef counting sort, samen met radix sort, in 1954.
Probeer het zelf
Open de app en druk op Stap. De strook tussen de lijst en de bufferrij toont één teller per waarde. Zie de tellers vollopen terwijl de lijst gelezen wordt, de reeksen in de buffer verschijnen als de aantallen worden opgeteld, en de tellers weer dalen terwijl de waarden geplaatst worden. Kies weinig unieke waarden om grote reeksen te zien, of typ getallen die ver uit elkaar liggen om te zien hoeveel tellers een groot bereik nodig heeft.
Veelgestelde vragen
Wat is de tijdcomplexiteit van counting sort?
O(n + k) voor n waarden en k mogelijke waarden, en O(n + k) extra geheugen voor de tellers en de buffer.
Waarom is counting sort niet altijd het snelst?
Omdat de kosten afhangen van het bereik van de waarden, niet alleen van hoeveel het er zijn. Als het bereik veel groter is dan de lijst, blijven de meeste tellers op nul en gaan tijd en geheugen verloren.
Kan counting sort negatieve getallen aan?
Ja. De tellers lopen van de kleinste waarde tot de grootste, dus trek de kleinste waarde af om de index van een teller te krijgen. De app doet hetzelfde.
Is counting sort stabiel?
Ja, zolang de waarden in lijstvolgorde naar de volgende vrije plek in hun reeks gaan. Radix sort is daarvan afhankelijk.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Probeer counting sort