Algoritmen I (2009-2010)

reeks 5: stabiliteit

Berichten rangschikken

Een sorteeralgoritme is stabiel als het "gelijke" sleutels in de oorspronkelijke volgorde laat staan. Bij het sorteren van getallen heeft dit geen belang, maar bij complexe gegevens wel. In zo'n geval kan "gelijkheid" bv. afhangen van één van de attributen.
Als je bv. e-mailberichten rangschikt volgens datum, en daarna volgens afzender, dan blijft de datum-rangschikking behouden per afzender.

Gegeven berichten.cpp. Voeg code toe zodat de berichten gerangschikt worden volgens datum, maar gegroepeerd per afzender. Gebruik hiervoor std::stable_sort.

Stabiliteit testen

Bedenk een (of meerdere) tests om na te gaan of een bepaald sorteeralgoritme (dat gegevens van het type T rangschikt) stabiel is, door een bepaalde collectie gegevens te rangschikken en achteraf te controleren of gelijke sleutels verwisseld werden.

Opm.: het is onmogelijk om een geparametrizeerde functie mee te geven als argument aan een andere functie. Bv. als

	template <typename T>
	void mijn_sort(vector<T> &v) { ... }

	template <typename SORTFUNC>
	bool is_stabiel(SORTFUNC &f) { ... }

	int main() {
		if (is_stabiel(mijn_sort)) // GAAT NIET: mijn_sort<??>
			...
	}

Stabiel maken

Elk (niet-stabiel) sorteeralgoritme kan stabiel gemaakt worden (zonder aan het oorspronkelijk algoritme te sleutelen!), door het sorteercriterium op een slimme manier aan te passen: als twee elementen gelijk zijn moet je de positie in de oorspronkelijke tabel vergelijken!

Implementeer een algoritme dat std::sort stabiel maakt.