AlgoI (09-10): reeks 10
Algoritmen I (2009-2010)
reeks 10: tel- en radixsorteren
Telsorteren
Maak een stabiele implementatie van telsorteren. Declaratie:
template <typename T, typename CONVFUNC>
void counting_sort(const std::vector<T> &v, const CONVFUNC &convfunc, uint k, std::vector<uint> &hulp, std::vector<T> &w);
Hierbij is v de te sorteren vector. Het resultaat komt terecht in w.
convfunc is een conversie- of selectiefunctie die een element van het type T omzet in een getal (uint staat voor unsigned int) in het interval [0, k[. Dat kan bv. de ASCII-waarde van de i-de letter van een string zijn.
hulp is een hulpvector.
De functie mag zowel hulp als w herdimensioneren (resize) naar believen.
Je kunt dit bv. testen door als conversiefunctie de identiteit voor uint te nemen:
uint ident(uint i) { return i; }
Radix-sort
Implementeer nu, gebruik makend van counting_sort, een stabiel radix-sort-algoritme voor string-sleutels van gelijke lengte.
Behandel de karakters van rechts naar links.
Kun je onnodige kopiëren van vectoren (v en w) vermijden?
| 
Algemeen