CountingSort is een sorteeralgoritme waarbij er wordt gebruik gemaakt van specifieke kennis over de input. Meer specifiek kan een rij \((a_1,a_2,...,a_n)\), waarbij \(a_i \in [0,k]\), heel efficiënt gesorteerd worden voor niet te grote waarden van \(k\). Voor dit algoritme is het belangrijk dat de waarde voor \(k\) gekend is bij de start. De tijdscomplexiteit van CountingSort bedraagt \(\mathcal{O}(n+k)\).

In het algoritme wordt geteld hoe vaak elk element in de lijst voorkomt. Aan de hand van deze informatie wordt dan bepaald hoeveel elementen kleiner zijn dan een gegeven element en vervolgens kan zo de gesorteerde lijst worden bepaald. Hieronder is de pseudocode weergegeven.

function CountingSort(a[1,..,n], max)

   for j from 0 to max do
      c[j] = 0
   for i from 1 to n do
      c[a[i]] = c[a[i]] + 1
   for j from 1 to max do
      c[j] = c[j] + c[j-1]
   for i from n to 1 do
      b[c[a[i]]] = a[i]
      c[a[i]] = c[a[i]] - 1
   for i from 1 to n do
      a[i] = b[i]

Stel nu dat we een lijst studenten hebben gegeven, waarbij elke student een naam heeft en een bepaalde score. We willen deze studenten sorteren in stijgende volgorde van resultaat. Hiervoor kunnen we opnieuw counting sort gebruiken, waarbij we telkens de score van de studenten vergelijken.

Implementeer dit algoritme in de methode public void sort(List<Student> studenten, int max) in de klasse CountingScoreBord, die een implementatie is van de interface ScoreBord¹. Deze methode neemt een (ongesorteerde) lijst studenten en een bovengrens van de scores uit de lijst als input. De inputlijst moet worden aangepast zodat deze na uitvoering van het algoritme gesorteerd is. Een object van de klasse Student² bevat een naam en een score.

Gebruik eventueel de testklasse SimpleTest³ om je oplossing lokaal te testen. Hierin zijn al enkele kleine tests aanwezig en je kan eenvoudig extra testgevallen toevoegen.