Geteld
Verplaatsingen
Tellers

  • Wordt geteld
  • Net verplaatst
  • Op zijn plek

Meer over counting sort

Counting sort

Counting sort werkt als de waarden gehele getallen in een klein bereik zijn. Het houdt één teller bij voor elke mogelijke waarde, telt hoe vaak elke waarde voorkomt en weet uit die aantallen precies waar elke waarde hoort. Zie de tellers vollopen terwijl de lijst gelezen wordt, en weer leeglopen als elke waarde naar haar reeks gaat, één verplaatsing per keer. Druk op Afspelen om het sorteren te volgen, of gebruik Stap en Terug om per verplaatsing te gaan. Sleep de stappenschuif om ergens naartoe te springen. De strook tussen de lijst en de bufferrij heeft één teller per waarde. De tegels tellen de getelde waarden, de verplaatsingen en de tellers. Kies hoeveel staven, hoe ze beginnen, of typ je eigen getallen. Als het bord geselecteerd is, zetten de pijltjestoetsen een stap, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het eind.

Hoe het werkt

  1. Kies hoeveel staven en hoe ze beginnen, of typ je eigen gehele getallen. Probeer een lijst met weinig unieke waarden.
  2. Druk op Afspelen, of gebruik Stap en Terug om per waarde te gaan. Sleep de stappenschuif om naar elk punt in het sorteren te springen.
  3. Let op de tellers: ze lopen vol terwijl de lijst gelezen wordt en tellen af als elke waarde geplaatst wordt.

Hoe counting sort werkt

Maak een teller voor elke waarde van de kleinste tot de grootste. Lees de lijst één keer en tel één op bij de teller van elke waarde die je ziet. Tel dan de aantallen op vanaf de kleinste waarde: de reeks van een waarde begint direct na alle kleinere waarden. Loop ten slotte de lijst opnieuw door, zet elke waarde op de volgende vrije plek in haar reeks en kopieer het resultaat terug.

Snel bij een klein bereik

Counting sort leest de lijst twee keer en loopt de tellers één keer door, dus het werk groeit met n + k: het aantal waarden plus het aantal tellers. Voor veel waarden in een klein bereik, zoals examenscores van 0 tot 100 of leeftijden, verslaat dat elk vergelijkend sorteeralgoritme. Bij een groot bereik verspilt het tijd en geheugen aan tellers die niemand gebruikt: drie waarden verspreid van 1 tot 1.000.000 hebben een miljoen tellers nodig. Het is ook de stap die radix sort voor elk cijfer herhaalt.

Veelgestelde vragen

Hoe werkt counting sort?

Het telt hoe vaak elke waarde voorkomt, telt de aantallen op om te vinden waar de reeks van elke waarde begint, en zet dan elke waarde rechtstreeks op de volgende vrije plek in haar reeks. Het vergelijkt nooit twee waarden.

Wanneer gebruik je counting sort?

Als de waarden gehele getallen zijn, of ernaar om te zetten zijn, en het bereik van kleinste tot grootste niet veel groter is dan het aantal waarden: cijfers, leeftijden, korte codes. Dan kost het tijd evenredig met n + k.

Is counting sort stabiel?

Ja, als de waarden in lijstvolgorde naar de volgende vrije plek in hun reeks gaan, zoals hier. Daardoor kan radix sort het voor elk cijfer gebruiken.

Waarom niet gewoon elke waarde zo vaak opschrijven als ze geteld is?

Voor gewone getallen werkt dat, en het is zelfs eenvoudiger. Maar echte gegevens bevatten meestal meer dan de sleutel, zoals een naam bij elke score, en door alleen de getelde sleutels op te schrijven raak je dat kwijt. Door de items zelf te verplaatsen blijft alles erbij.

Worden mijn getallen ergens naartoe gestuurd?

Nee. Het sorteren gebeurt in je browser, en je laatste instellingen blijven in de lokale opslag van deze browser.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Ga naar Editor