Algoritmen I (2009-2010)

reeks 7: indirect sorteren

Als de kost om T te kopiëren groot is (t.o.v. pakweg een int), dan loont het de moeite om een collectie van elementen T indirect te sorteren. Dat betekent dat men niet de elementen zelf maar "handles" naar de elementen sorteert. Deze handles kunnen indexen of pointers zijn die verwijzen naar de oorspronkelijke element. Er wordt ondersteld dat de kost om elementen te vergelijken, om handles te vergelijken en om handles te kopiëren relatief klein is.

Achteraf moet men de oorspronkelijke elementen nog op hun juiste plaats zetten (zoals aangegeven door de handles). En dat blijkt in lineaire tijd (O(N)) te kunnen! Kun je een algoritme verzinnen dat dit verwezenlijkt?

Voor de aardigheid definiëren we ons algoritme in een namespace IndirectSort. De functie mag dan gewoon sort heten:

	sort(vector<T> &v);

indirectsorttest.h is een testprogramma dat gebruik maakt van unittest.h en fakeint.h om na te gaan of je algoritme daadwerkelijk sorteert en niet teveel elementen verplaatst.