Resume
J1 S1 Samenvatting CCSA
- Établissement
- Hogeschool Gent (HoGent)
Alle te kennen leerstof
[Montrer plus]
Aperçu du contenu
H1: Zoeken en sorteren1.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.
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur BiggieBerto. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €5,49. Vous n'êtes lié à rien après votre achat.
Peut-on faire confiance à Stuvia ?
4.6 étoiles sur Google & Trustpilot (+1000 avis)
62555 résumés ont été vendus ces 30 derniers jours
Fondée en 2010, la référence pour acheter des résumés depuis déjà 14 ans