Opdracht 2: Algoritme runtime analyse.

© Harry Broeders.

In het onderstaande voorbeeldprogramma is de class StopWatch opgenomen. Deze class kan gebruikt worden om tijd te meten. In het voorbeeldprogramma wordt de tijd gemeten die het bubble_sort algoritme nodig heeft om een array met N elementen te sorteren.

Er zijn 3 versies van het programma. De eerste versie kan op elk operating systeem gebruikt worden maar is niet zo nauwkeurig. De tweede versie is nauwkeuriger maar kan alleen voor Windows XP worden gebruikt, de derde versie is ook nauwkeuriger dan de eerste versie en kan ook op Windows 7 worden gebruikt.

• timedsort.cpp
• timedsortWinXP.cpp
• timedsortWin7.cpp

Op mijn machine was de tijd die nodig is om 15000 getallen te sorteren ongeveer 1 seconde.

Een meerderheidselement in een array van N elementen is een element dat meer dan N/2 keer in de array voorkomt.
De array: 3, 3, 4, 2, 4, 4, 5, 4, 4 heeft als meerderheidselement de waarde 4.
De array: 3, 3, 4, 2, 4, 4, 5, 4, 3 heeft geen meerderheidselement.

Er zijn verschillende algoritmen om het meerderheidselement van een array te vinden:

• Methode 1:
  Tel hoe vaak het eerste element voorkomt. Als dit element N/2+1 keer voorkomt is dit het meerderheidselement. Zo niet, tel dan hoe vaak het tweede element voorkomt. Als dit element N/2+1 keer voorkomt is dit het meerderheidselement. Enzovoort totdat je geteld hebt hoe vaak element N/2+1 voorkomt. Als je dan nog steeds geen meerderheidselement hebt gevonden dan is het er ook niet.
• Methode 2:
  Sorteer de array en tel steeds het aantal elementen met dezelfde waarde (die dan achter elkaar staan). Zodra je N/2+1 elementen met dezelfde waarde vindt heb je het meerderheidselement gevonden.
• Methode 3:
  Bij deze methode gaan we er (in eerste instantie) vanuit dat er een meerderheidselement is. Als er een meerderheidselement is dan kun je dat vinden door steeds twee verschillende waarden uit de array te verwijderen. Totdat de array nog maar één waarde bevat, deze waarde is dan het meerderheidselement.
  Dit "verwijderen" kan op een slimme manier gedaan worden door element voor element te "bekijken". Het element wat eventueel het meerderheidselement zou kunnen zijn noemen we de kandidaat. We houden ook in een teller bij hoe vaak we de kandidaat hebben gezien. We gaan nu 1 voor 1 de elementen van de array af. Bij het "bekijken" van een element zijn er een twee mogelijkheden.
  • De teller is 0
    We hebben nog geen kandidaat dus we kiezen dit element als kandidaat en zetten de teller op 1.
  • De teller is >0
    Als het element gelijk is aan de kandidaat verhogen we de teller met 1 en anders verlagen we de teller met 1.

  Als we alle elementen hebben "bekeken" blijft er een kandidaat over (teller > 0) of niet (teller == 0). Omdat we er (in eerste instantie) vanuit gegaan zijn dat de array een meerderheidselement heeft moet je nu, als er een kandidaat is, nog wel even controlleren of dit het meerderheidselement is door te tellen hoe vaak de kandidaat in de array voorkomt.
  Uitleg:
  Als de teller 0 wordt hebben we net zoveel elementen gehad die gelijk waren aan de kandidaat (telkens +1) als elementen die ongelijk waren aan de kandidaat (-1). Deze elementen vormen dus paartjes van ongelijke elementen en die kunnen we dus allemaal uit de array verwijderen. Als er een meerderheidselement was in de oorspronkelijke array dan heeft de resterende rij hetzelfde meerderheidselement! (Dit zou wel of niet de vorige kandidaat kunnen zijn maar dat maakt niets uit!)
  Deze methode is bedacht door Moore en Boyer. Zie http://www.cs.utexas.edu/users/moore/best-ideas/mjrty/index.html voor een eenvoudige uitleg en een stap voor stap demo. Zie http://www.cs.utexas.edu/users/boyer/mjrty.pdf voor een uitgebreide uitleg.

bool zoekMeerderheidsElement(int& resultaat, int* begin, int* end);

Verder met opgave 3...