Ontdek de essentie van klassieke computerwetenschappelijke algoritmen met deze uitgebreide samenvatting. Leer de fundamenten van algoritmen zoals sorteren, zoeken en grafentheorie, met duidelijke uitleg en geïllustreerde voorbeelden (samen met cursustekst bekijken). Deze samenvatting biedt een waa...
01-CCSA-Zoeken-en-Sorteren:
1.1 Zoeken in een Array
Een zoekalgoritme wordt gebruikt om een bepaald element te zoeken in een gegeven array,
beter gezegd de positie van dat element in de array te achterhalen. Wanneer de array bij
aanvang van het zoekproces al gesorteerd is, zou dit invloed kunnen hebben op de te
gebruiken methode. In een gesorteerde lijst kan men efficiënter zoeken als in een
ongesorteerde lijst (dit valt te vergelijken met het zoeken in een woordenboek ->
gesorteerd). We gaan ervan uit dat het zoeken naar een element in een array op een
willekeurige plaats in een constante tijd op te halen is. Dit houdt in dat we verwachten dat
het ophalen van het eerste, laatste of middelste element even lang zou duren. We zullen
hiervoor nu twee verschillende algoritmen gaan bekijken.
1.1.1 Sequentieel zoeken (= Lineair zoeken)
Sequentieel zoeken kunnen we eenvoudig gaan vergelijken met het zoeken naar jouw naam
in een lijst van 5000 namen dat niet gesorteerd is. De enige manier om erachter te gaan
komen of jouw naam zich in de lijst bevindt is elke naam af te gaan in de lijst (van voor naar
achter) en kijken of jouw naam voorkomt. Deze manier van werken heet LINEAR ZOEKEN of
SEQUENTIEEL ZOEKEN.
Lineair zoeken kan je makkelijk implementeren. In volgend algoritme gaan we op zoek naar
één specifiek item, “zoekItem” in een array van items. Alle elementen van de array worden
één voor één vergeleken met de op te sporen waarde “zoekItem”. Wanneer er een match
gevonden wordt of het einde van de array wordt bereikt zal het algoritme stoppen met
zoeken. De methode “zoekSequentieel” verwacht 2 inputwaarden, namelijk de waarde
“zoekItem” en een array “rij” van lengte n. Deze methode zal de index van “zoekItem” gaan
retourneren, wanneer “zoekItem” niet gevonden werd zal -1 geretourneerd worden. Het zal
ook het eerste voorkomen van “zoekItem” zijn waarvan de index zal worden geretourneerd.
,Opmerking 1.1: “Zoeken” is een proces, onafhankelijk van het type v/d elementen in de
array. In deze code wordt gewoon verondersteld dat je de elementen kunt vergelijken.
Opmerking 1.2 (Assignatie en vergelijken): In de pseudocode wordt a b gebruikt om de
waarde b toe te kennen aan (Assignatie) a en wordt a = b gebruikt om de twee waarden te
vergelijken.
1.1.2 Binair Zoeken
We hebben dus gezien dat lineair of sequentieel zoeken zeer eenvoudig te implementeren is
en uiteraard ook werkt of de array nu gesorteerd is of niet. Anderzijds is het wel meteen
duidelijk dat er een “betere” manier moet bestaan om te zoeken in een gesorteerde array.
Als we nu nog eens denken aan een woordenboek als voorbeeld dan kunnen we zelf ook als
snel bedenken dat dit een zeer eenvoudigere manier is om iets te gaan zoeken door het feit
dat alles gesorteerd is waardoor enkele problemen al snel zullen verdwijnen.
BINAIR ZOEKEN gaat op dezelfde manier te werk als het zoeken in een woordenboek, mar
dan heel systematisch. In een gesorteerde array wordt het middelste item bekeken, wanneer
dit item kleiner is dan het gezochte item zal er worden verder gezocht in de rechterhelft van
de array. In het andere geval zal er worden verder gezocht in de linkerhelft van de array.
Hetgeen dat essentieel is voor de performantie van binair zoeken is dat de array bij elke stap
in (bijna) twee gelijke delen wordt verdeeld. Op het einde van dit proces blijft er precies één
element over waarna de iteratie stopt. Door dit overgebleven element te gaan vergelijken
met het gezochte element weten we of het element voorkomt in de array of niet.
Met het idee dat het zoekproces in de oorspronkelijke array wordt herleid naar een
zoekproces in een array half zo groot, laat ons toe dit probleem op te gaan lossen met
recursie, maar uiteraard kan het algoritme ook iteratief worden geïmplementeerd. Deze 2
mogelijke oplossingsmethodes zullen allebei besproken worden.
Opmerking 1.3: Bij lineair zoeken was de enige vereiste aan het type van de elementen dat
er kan beslist worden of de elementen gelijk zijn of niet. Bij binair zoeken weten we nu dat
de array reeds gesorteerd is (van klein naar groot) waardoor we naast het controleren of de
elementen gelijk zijn aan elkaar ook zullen moeten kunnen nagaan welke de grootste is van
de twee wanneer ze niet gelijk zijn. In de pseudocode schrijven we dit als x < y. De in- en
uitvoer is voor beiden algoritmen natuurlijk hetzelfde.
Opmerking 1.4: Bij de implementatie van binair zoeken zullen we wel aandacht gaan
besteden aan het feit dat de index van het eerste voorkomen wordt geretourneerd, zodat we
steeds dezelfde uitvoer zullen gaan krijgen als bij het sequentieel zoeken. Dit zullen we gaan
doen aangezien er ook implementaties mogelijk zijn die dit niet garanderen.
Om bij te kunnen houden welk deel van de array onderzocht moet worden, introduceren we
de gehele variabele l voor de positie links en r voor de positie rechts. Bij aanvang moet de
volledige array natuurlijk onderzocht worden waardoor we de variabelen l en r zullen
,moeten gaan initialiseren als volgt: l 0 en r n – 1 waarbij n de lengte van de array
voorstelt.
Vervolgens wordt dan steeds van het te onderzoeken deel het midden bepaald en wordt de
index van dit midden wordt bijgehouden in de gehele variabele m. Wanneer het aantal
elementen in een rij oneven is, dan is het middelste element onmiddellijk duidelijk.
Anderzijds wanneer het aantal elementen in de array even is zullen er 2 middelste
elementen zijn. Wij zullen er in dit geval voor kiezen om het kleinste van deze twee
elementen als het middelste element aan te duiden. Bijgevolg kunnen we m in beide
gevallen als volgt gaan bepalen: m = [(l + r) / 2]. Door de manier waarop m werd
gedefinieerd geldt steeds: l <= m < r. Het zou dus kunnen dat m gelijk is aan l, maar m is
steeds strikt kleiner dan r, wanneer l < r.
In volgend algoritme vinden we de iteratieve implementatie van het algoritme voor binair
zoeken. We zouden dit zoekalgoritme ook recursief kunnen implementeren, dit zou dan
steeds een selectiestructuur gaan bevatten. Deze selectiestructuur beschrijft dan wat er zou
moeten gebeuren in het basisgeval en in de recursieve stap. Basisstap: de te onderzoeken
array bevat slechts één element, dit element wordt vergeleken met de inputwaarde
zoekItem. Recursieve stap: de rij wordt gehalveerd, de functie wordt opnieuw aangeroepen
op een deelrij half zo groot als de oorspronkelijke array.
In
onderstaand algoritme vinden we de recursieve implementatie, er is een “driver”- functie
, genaamd zoekBinair. Deze functie wordt opgeroepen wanneer men een array wenst te
sorteren. Dan hebben we nog de functie zoekRecursief, deze wordt opgeroepen door deze
driver-functie en is de eigenlijke recursieve functie die het zoekproces implementeert.
Opmerking 1.5 (Het eerste voorkomen): De implementatie zal er gaan voor zorgen dat het
algoritme steeds het eerste voorkomen van een element vindt in de array. Deze garantie
verdwijnt natuurlijk wanneer men de iteratie of recursie vroegtijdig zou afbreken wanneer
het gezochte element (voor de eerste maal) ontmoet.
1.1.3 Sequentieel vs. Binair Zoeken
We zijn het er over eens dat het algoritme voor binair zoeken ingewikkelder te
implementeren is dan het algoritme voor sequentieel zoeken. Hierdoor hopen we natuurlijk
dat het algoritme voor binair zoeken “beter” zal gaan zijn dan het algoritme voor sequentieel
zoeken. Bij het analyseren van een algoritme zal men naar 2 zaken gaan kijken.
1. De tijd die het algoritme nodig heeft wanneer het wordt uitgevoerd.
2. De hoeveelheid hoofdgeheugen (RAM) die het algoritme nodig heeft bij uitvoering.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller aronvandaele1. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $9.75. You're not tied to anything after your purchase.
