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 CountingSort gebruiken, waarbij we telkens de score van de studenten vergelijken.

Implementeer dit algoritme in de Python-functie sorteer(studenten: list, max: int). Deze functie neemt een (ongesorteerde) lijst studenten en een bovengrens van de scores uit de lijst als input. De functie moet een lijst gesorteerd op scores teruggeven. Een student wordt voorgesteld als een tuple tuple(naam, score) met als eerste argument de naam en als tweede de score.

Voorbeeld

>>> sorteer([("Ruben", 20), ("Tobiah", 2), ("Seppe", 18), ("Pieter", 10)], 20)
[('Tobiah', 2), ('Pieter', 10), ('Seppe', 18), ('Ruben', 20)]
>>> sorteer([ ("Tobiah", 2), ("Seppe", 18), ("Pieter", 10), ("Ruben", 20), ('Femke', 12)], 20)
[('Tobiah', 2), ('Pieter', 10), ('Femke', 12), ('Seppe', 18), ('Ruben', 20)]
>>> sorteer([], 10)
[]