AlgoI (09-10): reeks 6
Algoritmen I (2009-2010)
reeks 6: stabiliteit
Merge-sort
Implementeer de eenvoudige versie van merge-sort
(top down, recursief, met kopie van volledige mergetabel).
Zorg ervoor dat je algoritme stabiel is.
Gegeven interface: mergesort_interface.h
Gebruik geen andere dan de gegeven headers.
De algoritmen zijn gedeclareerd als statische methodes - de bedoeling is om eventuele
hulpfuncties private (en ook static) te maken zodat je geen onnodige namespace pollution krijgt.
Om te testen:
mergesorttest.h
main.cpp
unittest.h
Inversies tellen
Je kunt het aantal inversies (paren elementen die niet in volgorde staan)
in een gegeven vector tellen door alle paren een voor een te controleren.
Wat is de complexiteit van deze methode?
Er bestaat een snellere variant die lijkt op merge-sort. Kun je bedenken hoe?
Implementeer beide methodes en vergelijk de performantie (bv. met FakeInt).
| 
Algemeen