H1: Zoeken en sorteren
1.1 Zoeken in een array
Zoekalgoritme wordt gebruikt om een bepaald element te zoeken in een gegeven array = om positie
van dat element te bepalen. Of de array gestorteerd is of niet kan een invloed hebben op de te
gebruiken methode
1.1.1 Sequentieel zoeken
Lineair/sequentieel zoeken: in een array met namen van 5000 studenten alle namen één voor één
afgaan tot je de gewenste naam gevonden hebt
Pseudocode
Elementen worden één voor één vergeleken met de op te sporen waarde zoekItem, het algoritme
stopt wanneer het item gevonden is of het einde van de array bereikt is. Als return waarde wordt de
index van zoekItem teruggegeven. Indien de index van zoekItem niet voorkomt in de array wordt er -
1 teruggegeven
1.1.2 Binair zoeken
In een gesorteerde array wordt het middelste item bekeken. Als dit kleiner is dan het gezochte item,
wordt er verder gezocht in de rechterhelft van de array, als het groter is de linkerhelft.
Op het einde van dit proces blijft er een element over waarna de iteratie stopt. Door het vergelijken
van dit element met het gezochte element weten we direct of het element voorkomt in de array
Het idee dat het zoekproces in de oorspronkelijke array wordt herleid naar een zoekproces half zo
groot, laat toe dit probleem op te lossen met recursie, maar uiteraard kan het algoritme ook iteratief
worden geïmplementeerd
,Pseudocode
Recursieve implementatie van binair zoeken
,1.1.3 Sequentieel vs binair zoeken
Binair zoeken = ingewikkelder dan sequentieel zoeken
Binair zoeken is beter?
Focus op uitvoeringstijd en geheugengebruik
We concentreren ons voornamelijk op de tijd die nodig is om het algoritme uit te voeren. Bij de
analyse van de zoekalgoritmen zien we dat de asymptotische uitvoeringstijd bepaald wordt door het
aantal vergelijkingen dat wordt uitgevoerd
Aantal vergelijkingen bij sequentieel zoeken
Bij sequentieel zoeken kunnen we ons afvragen hoeveel keer de vergelijking rij[i] ≠ zoekItem
Beste geval: het te zoeken element staat helemaal vooraan de array
Slechtse geval: het te zoeken element staat helemaal achteraan de array
Gemiddeld gezien staat het te zoeken element ergens in het midden, zodat we verwachten ongeveer
n/2 vergelijkingen uit te voeren
We zie dat de uitvoeringstijd verdubbelt wanneer de lengte van de invoerrij wordt verdubbeld. De
tijdscomplexiteit is lineair of van de orde n
Aantal vergelijkingen bij binair zoeken
Bij binair zoeken tellen we hoeveel keer de vergelijking wordt uitgevoerd
Voor de eenvoud van de analyse nemen we aan dat de lengte van de array een macht van twee is of
n = 2k waarbij k een natuurlijk getal is
Wanneer k = 0 dan is de lengte van de rij gelijk aan 1 en wordt de vergelijking geen enkele keer
uitgevoerd
Wanneer k = 3 (maw lengte van rij = 8) dan zal na de eerste uitvoering van vergelijking (1.1) de lengte
van de deelrij gereduceerd worden tot 4. In dit geval zijn er dus 1 + 2 = 3 uitvoeringen van de
vergelijking (1.1). Op deze manier zien we dat wanneer n = 2 k er precies k uitvoeringen zullen zijn van
de vergelijking (1.1)
Verband gegeven door:
Dit noemen we logaritmische tijdscomplexiteit:
, Merk op dat voor kleine
waarden van n, die
uitvoeringstijd van de twee
methoden niet significant van
elkaar verschillen. Het
verschil in gedrag
manifesteert zich wanneer de
rijen waarin moet gezocht
worden iets langer zijn
1.2 Sorteren van een array
We hebben gezien dat het doorzoeken van een array veel efficiënter gaat wanneer deze gesorteerd
is. In deze sectie bekijken we een drietal algoritmen om een array te sorteren
1.2.1 Sorteren door selectie
Het basisidee van sorteren door selectie kan eenvoudig samengevat worden:
Zoek het grootste element en plaats het achteraan
Sorteer de rest van de array
Pseudocode
In de te sorteren array gaan we op zoek naar het grootste element. Indien dit element niet achteraan
staat in de rij, moet dit element verwisseld worden met het element op de laatste plaats. Zo staat het
grootste element achteraan de rij. De n-1 overige elementen moeten nu gesorteerd worden.
Complexiteitsanalyse
De uitvoeringstijd wordt bepaald door het aantal keer dat de vergelijking a[j] > max, dit aantal komt
overeen met het aantal keer dat de teller j van waarde wijzigt.
1.1 Zoeken in een array
Zoekalgoritme wordt gebruikt om een bepaald element te zoeken in een gegeven array = om positie
van dat element te bepalen. Of de array gestorteerd is of niet kan een invloed hebben op de te
gebruiken methode
1.1.1 Sequentieel zoeken
Lineair/sequentieel zoeken: in een array met namen van 5000 studenten alle namen één voor één
afgaan tot je de gewenste naam gevonden hebt
Pseudocode
Elementen worden één voor één vergeleken met de op te sporen waarde zoekItem, het algoritme
stopt wanneer het item gevonden is of het einde van de array bereikt is. Als return waarde wordt de
index van zoekItem teruggegeven. Indien de index van zoekItem niet voorkomt in de array wordt er -
1 teruggegeven
1.1.2 Binair zoeken
In een gesorteerde array wordt het middelste item bekeken. Als dit kleiner is dan het gezochte item,
wordt er verder gezocht in de rechterhelft van de array, als het groter is de linkerhelft.
Op het einde van dit proces blijft er een element over waarna de iteratie stopt. Door het vergelijken
van dit element met het gezochte element weten we direct of het element voorkomt in de array
Het idee dat het zoekproces in de oorspronkelijke array wordt herleid naar een zoekproces half zo
groot, laat toe dit probleem op te lossen met recursie, maar uiteraard kan het algoritme ook iteratief
worden geïmplementeerd
,Pseudocode
Recursieve implementatie van binair zoeken
,1.1.3 Sequentieel vs binair zoeken
Binair zoeken = ingewikkelder dan sequentieel zoeken
Binair zoeken is beter?
Focus op uitvoeringstijd en geheugengebruik
We concentreren ons voornamelijk op de tijd die nodig is om het algoritme uit te voeren. Bij de
analyse van de zoekalgoritmen zien we dat de asymptotische uitvoeringstijd bepaald wordt door het
aantal vergelijkingen dat wordt uitgevoerd
Aantal vergelijkingen bij sequentieel zoeken
Bij sequentieel zoeken kunnen we ons afvragen hoeveel keer de vergelijking rij[i] ≠ zoekItem
Beste geval: het te zoeken element staat helemaal vooraan de array
Slechtse geval: het te zoeken element staat helemaal achteraan de array
Gemiddeld gezien staat het te zoeken element ergens in het midden, zodat we verwachten ongeveer
n/2 vergelijkingen uit te voeren
We zie dat de uitvoeringstijd verdubbelt wanneer de lengte van de invoerrij wordt verdubbeld. De
tijdscomplexiteit is lineair of van de orde n
Aantal vergelijkingen bij binair zoeken
Bij binair zoeken tellen we hoeveel keer de vergelijking wordt uitgevoerd
Voor de eenvoud van de analyse nemen we aan dat de lengte van de array een macht van twee is of
n = 2k waarbij k een natuurlijk getal is
Wanneer k = 0 dan is de lengte van de rij gelijk aan 1 en wordt de vergelijking geen enkele keer
uitgevoerd
Wanneer k = 3 (maw lengte van rij = 8) dan zal na de eerste uitvoering van vergelijking (1.1) de lengte
van de deelrij gereduceerd worden tot 4. In dit geval zijn er dus 1 + 2 = 3 uitvoeringen van de
vergelijking (1.1). Op deze manier zien we dat wanneer n = 2 k er precies k uitvoeringen zullen zijn van
de vergelijking (1.1)
Verband gegeven door:
Dit noemen we logaritmische tijdscomplexiteit:
, Merk op dat voor kleine
waarden van n, die
uitvoeringstijd van de twee
methoden niet significant van
elkaar verschillen. Het
verschil in gedrag
manifesteert zich wanneer de
rijen waarin moet gezocht
worden iets langer zijn
1.2 Sorteren van een array
We hebben gezien dat het doorzoeken van een array veel efficiënter gaat wanneer deze gesorteerd
is. In deze sectie bekijken we een drietal algoritmen om een array te sorteren
1.2.1 Sorteren door selectie
Het basisidee van sorteren door selectie kan eenvoudig samengevat worden:
Zoek het grootste element en plaats het achteraan
Sorteer de rest van de array
Pseudocode
In de te sorteren array gaan we op zoek naar het grootste element. Indien dit element niet achteraan
staat in de rij, moet dit element verwisseld worden met het element op de laatste plaats. Zo staat het
grootste element achteraan de rij. De n-1 overige elementen moeten nu gesorteerd worden.
Complexiteitsanalyse
De uitvoeringstijd wordt bepaald door het aantal keer dat de vergelijking a[j] > max, dit aantal komt
overeen met het aantal keer dat de teller j van waarde wijzigt.
