Garantie de satisfaction à 100% Disponible immédiatement après paiement En ligne et en PDF Tu n'es attaché à rien
logo-home
J1 S1 Samenvatting CCSA €5,49   Ajouter au panier

Resume

J1 S1 Samenvatting CCSA

 24 vues  0 fois vendu

Alle te kennen leerstof

Aperçu 4 sur 72  pages

  • 21 décembre 2022
  • 72
  • 2022/2023
  • Resume
Tous les documents sur ce sujet (5)
avatar-seller
BiggieBerto
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.

Les avantages d'acheter des résumés chez Stuvia:

Qualité garantie par les avis des clients

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

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

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)

78834 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

Commencez à vendre!
€5,49
  • (0)
  Ajouter