🚀 go-pugleaf

"Dieter D'Hoker" <webmaster@neverseenbefore.com> wrote in message
news:3ddd4ca5$0$46603$e4fe514c@news.xs4all.nl...
> a)
> elke persoon vergelijkt met zijn buurman links van hem als ie hoger is
doet
> hij niks ,
> als hij lager is dan verwisselen ze van plaats ...

Als je deze lus blijft uitvoeren totdat er niemand meer veplaatst wordt, dan
gaat ze in een oneindige lus [aangezien de mensen in een cirkel staan; als
ze in een rij zouden staan had dit wel gewerkt].

> b)
> Men zoekt de laagste waarde tussen de personen ,
> dit is de beginpersoon ...
> Dan zoekt men telkens de persoon die daar op volgt ,
> en die vcerplaatst zich dan ...

Deze methode [selection sort] heeft een gemiddelde complexiteit van
O((n-1)(n-2)...(1)) = O(n(n+1)/2) = O(n^2).

> Iemand een idee ? En een formule in functie van n (n = aantal personen =
> aantal plaatsen in de cirkel) om dit te onderbouwen ?

Persoonlijk zou ik eerst het hoogste [of het laagste] element zoeken in je
rij [O(n)] en dan een aangepaste bubble sort doen [methode a].
De complexiteit van het slechtste geval is nog steeds O(n^2), maar in het
gemiddelde geval gaat die veel beter uitkomen dan een selection sort.
Aangezien de complexiteit van je sorteer algoritme hoger is dan O(n) maakt
die eerste zoek operatie van het hoogste/laagste element niets uit.

Trouwens, als je eens wil _zien_ hoe snel de verschillende sorteer methodes
zijn, raad ik je aan de volgende pagina eens te bezoeken:
http://www.cs.kuleuven.ac.be/~kdv/mi0001/hoorcolleges/SORTING/AllFlat/sortin
g-demo.html

Mvg,
Pieter Philippaerts