AlgoI (09-10): reeks 1
Algoritmen I (2009-2010)
reeks 2: zoeken en rangschikken (intro)
Zoeken
Gegeven: stopwatch.h
Binair zoeken in een tabel of vector is natuurlijk sneller dan lineair zoeken, maar het vereist wel dat de gegevens gerangschikt zijn,
en dat rangschikken kost ook tijd.
De vraag stelt zich wanneer het de moeite loont om de gegevens eerst te rangschikken om daarna binair te kunnen zoeken.
Dat hangt natuurlijk af van de gegevens zelf, en van wat en hoe vaak er gezocht wordt.
Concreet: stel dat er k keer naar een willekeurig getal gezocht wordt in een vector van n willekeurige getallen.
Voor gegeven n, vanaf welke k loont het de moeite eerst te sorteren?
Gebruik functies uit de standard-library voor zoeken en sorteren.
Meet de uitvoeringstijden voor verschillende n, k (bv. exponentieel stijgend). Schrijf die naar een bestand. Importeer dat bestand in excel, en maak grafieken.
Interpreteer je resultaten.
Headers
Een groot deel van de cursus gaat over rangschikken.
Er zijn tal van implementaties mogelijk. Daarbij stelt zich telkens de vraag:
Hoe weet ik of mijn sorteermethode correct werkt?
Hoe weet ik of mijn sorteermethode stabiel is?
Hoe snel is mijn methode? Gemiddeld? Worst case? Best case?
Geamortiseerd?
Hoe veel (geheugen- of schijf-) ruimte gebruikt mijn methode?
Het zou interessant zijn een header-bestand te maken met
enkele nuttige functies i.v.m. rangschikken,
bv. onder de naam sortutil.h.
Lees eerst wat uitleg over C++-bibliotheken.
Implementeer volgende hulpmethodes (v is telkens een vector van T, een template-parameter; vi is een vector<int>).
Voor de meeste functies kun je gebruik maken van de standard library, en kan het zelfs in 1 lijntje!!
print(v): drukt de elementen af gescheiden door een spatie.
maak_range(n, vi): vult een vector vi op met getallen 0..n-1 in volgorde
is_range(n, vi): gaat na of vector vi de getallen 0..n-1 bevat
vul_random(v, min, max): vul v met random getallen tussen min en max. Je kunt een versie voor int en voor double maken.
rnd_shuffle(v): random permutaties van de elementen van v. De methode van Knuth / Fisher-Yates / Durstenfeld is hier de standaard.
!! Let op voor de random-generator. Ga eens na hoe groot de getallen die rand() produceert kunnen worden !! Vind je andere random-generatoren op het internet?
is_stijgend(v): true indien v[i]<=v[j] als i<j
is_strikt_stijgend(v): true indien v[i]<v[j] als i<j
draai_om(v): verwisselt de volgorde van elementen in v
Implementeer insertion sort en selection sort.
Ga na of de methodes correct werken, bv. door een range te maken,
random te 'shufflen', vervolgens te sorteren en dan te controleren of de oorspronkelijke range hersteld is.
Meet bij elke methode de performantie voor
willekeurige getallen
reeds gerangschikte gegevens
omgekeerd gerangschikte gegevens
Maak voor elke geval een grafiek in excel voor stijgende n.
| 
Algemeen