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 2 versies van het programma. De eerste versie kan op elk operating systeem gebruikt worden maar is niet zo nauwkeurig. De tweede versie maakt is nauwkeuriger maar kan alleen voor Windows-XP worden gebruikt.

• timedsort.cpp
• timedsortXP.cpp

Opdracht 2a. Start het voorbeeldprogramma en zoek een waarde van N waarbij het sorteren ongeveer 1 seconde duurt. Voer deze waarde 10 maal in en vergelijk de resultaten. Maak een grafiekje met behulp van Excel. De tijd die nodig is om N getallen te sorteren is niet constant! Kun je dat verklaren?

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

Geef N (of Ctrl+C om te stoppen): 10000
Tijdsduur: 0.80 sec
Geef N (of Ctrl+C om te stoppen): 10000
Tijdsduur: 0.84 sec
Geef N (of Ctrl+C om te stoppen): 10000
Tijdsduur: 0.81 sec
Geef N (of Ctrl+C om te stoppen): 10000
Tijdsduur: 0.80 sec
Geef N (of Ctrl+C om te stoppen): 10000
Tijdsduur: 0.80 sec
Geef N (of Ctrl+C om te stoppen): 10000
Tijdsduur: 0.84 sec
Geef N (of Ctrl+C om te stoppen): 10000
Tijdsduur: 0.83 sec
Geef N (of Ctrl+C om te stoppen): 10000
Tijdsduur: 0.81 sec
Geef N (of Ctrl+C om te stoppen): 10000
Tijdsduur: 0.77 sec
Geef N (of Ctrl+C om te stoppen): 10000
Tijdsduur: 0.84 sec
Geef N (of Ctrl+C om te stoppen):

Opdracht 2b. Probeer nu de orde van het algoritme vast te stellen door de benodigde tijd te meten voor verschillende waarden van N. Maak een grafiek met behulp van Excel.

Op mijn machine heb ik het volgende gemeten:

Geef N (of Ctrl+C om te stoppen): 5000
Tijdsduur: 0.38 sec
Geef N (of Ctrl+C om te stoppen): 10000
Tijdsduur: 1.55 sec
Geef N (of Ctrl+C om te stoppen): 15000
Tijdsduur: 3.44 sec
Geef N (of Ctrl+C om te stoppen): 20000
Tijdsduur: 6.11 sec
Geef N (of Ctrl+C om te stoppen): 25000
Tijdsduur: 9.53 sec
Geef N (of Ctrl+C om te stoppen): 30000
Tijdsduur: 13.64 sec
Geef N (of Ctrl+C om te stoppen): 35000
Tijdsduur: 19.33 sec
Geef N (of Ctrl+C om te stoppen): 40000
Tijdsduur: 29.67 sec
Geef N (of Ctrl+C om te stoppen): 45000
Tijdsduur: 38.30 sec
Geef N (of Ctrl+C om te stoppen):

Opdracht 2c. De C++ standaard functie sort is veel efficiënter. Vervang de aanroep naar de (door mij) zelfgemaakte bubble_sort door een aanroep van de standaard functie sort. Bepaal eerst een waarde van N waarbij de tijd die nodig is om te sorteren ongeveer 1 seconde is. Probeer de orde van de C++ standaard sort te bepalen door de benodigde tijd te meten voor verschillende waarden van N. Maak een grafiek met behulp van Excel.

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.

Opdracht 2d. Schrijf een functie die kan bepalen of een array een meerderheidselement heeft (met één van de drie hierboven beschreven methoden). Als de array een meerderheidselement heeft dan moet de functie dit element ook teruggeven. Het prototype van de functie is als volgt: bool zoekMeerderheidsElement(int& resultaat, int* begin, int* end); De parameter begin moet wijzen naar het eerste element van de array en de parameter end moet wijzen 1 positie voorbij het laatste element van de array. De functie geeft false terug als geen meerderheidselement gevonden is. De functie geeft true terug als wel een meerderheidselement gevonden is. Dit meerderheidselement wordt dan opgeslagen in de variabele waar de parameter resultaat naar refereert. Gebruik het programma timedzme.cpp of timedzmeXP.cpp om je programma te testen en om de orde van het door jou geïmplementeerde algoritme te bepalen.

Verder met opgave 3...