Rick van der Zwet, Universiteit Leiden
StudentID: 0433373
Version: $Id: opdracht-1.txt 561 2008-04-12 13:55:24Z rick $
Complexiteit 2008 --- opdracht 1

a. Ga na hoe het algoritme werkt voor het array 5,6,1,2,3,4. Laat zien
hoe het array eruit ziet _elke_ keer nadat regel (10) is uitgevoerd.
N.B: Buurt 0 is de beginstand

B:       Array      -   Indexgetal
0:   5.6.1.2.3.4    -   6
1:   5.6.1.4.3.2    -   6
2:   5.2.1.4.3.6    -   6
3:   5.2.1.4.3.6    -   6
4:   5.2.3.4.1.6    -   5
5:   1.2.3.4.5.6    -   5
6:   1.2.3.4.5.6    -   5
7:   1.2.3.4.5.6    -   4
8:   1.2.3.4.5.6    -   3
9:   1.2.3.4.5.6    -   2



b. Toon aan dat vergelijken van array-elementen in regel (7) een goede
basisoperatie is ,als n >= 0, in orde van grootte.

#08 <= #07
#09 == #07
#06 == #07 + 1
#05 <= #06
#10 <= #06
#11 == #10
#12 <= #11
#04 == #05 + 1
#03 <= #04
#13 <= #04
#12 == #13 + 1
#01  == 1



c. Regel (10) kan maximaal 2n - 2 keer worden uitgevoerd. Leg uit
waarom. Gebruik dit resultaat om een redelijke bovengrens te bepalen
voor het aantal vergelijkingen tussen array elementen (regel (7)).

Voor het goede resultaat zal eerst de worst case bepaald moeten worden
als gekeken wordt naar regel (10). Hierbij is het verwisselingen dat toe
moet passen als alle getallen verkeerd staan n - 1 (het laatste getal
staat automatisch goed). Verder moet er nog n - 1 gewisseld worden,
hierbij gaat het echter om de 'controle' wissel en zal deze wissel
wezelijk dus niets veranderen het rijtje. Bij elkaar opgeteld is 2n - 2
dus de eindscore.

Om dit resultaat naar het aantal array vergelijkingen te vertalen is het
slechte geval het meest aantrekkelijk. Hierbij worden in de 'eerste'
index getal (n) de verwisselingen gedaan, dit levert dan telkens n - 1
verwisselingen op, subtotaal n^2 - n De controle verwisselingen kosten telkens 1 minder en
leveren zo de reeks (n - 1) + (n - 2) +  ... + (n - (n -1)) + (n - n) =
0.5n^2 - 0.5n
Dit gesommeerd levert op 1.5n^2 - 1.5n



d. Best case, met in het antwoord aantal vergelijkingen

De best case is een oplopend gesorteerd rijtje, alle getallen staan al
op de goede plek,  welke enkele de controle vergelijkingen nodig heeft.
Dit is 0.5n^2 - 0.5n (zie c.). Tijdens n = 1 worden er 0 vergelijkingen
uitgevoerd.



e. Worst case, met in het antwoord aantal vergelijkingen

De worst case is een rijtje waarbij in de grootste index alle
verwisselen gedaan moeten worden (en dus allen verkeerd staan). Zoeen
rijtje heeft bijvoorbeeld de vorm 6.0.1.2.3.4.5. Aantal vergelijkingen
dat gedaan moet worden is 1.5n^2 - 1.5n (zie e)