Alle stof van het vak Datastructuren (INFODS), duidelijk en gestructureerd samengevat. Gebaseerd op de hoorcolleges en het boek Introduction to Algorithms, Third Edition (ISBN: 978-0-262-53305-8). Disclaimer: de verschillende sorteeralgoritmen zijn wel inbegrepen, maar niet uitgebreid uitgelegd in ...
,Binary Search
Array organisatie
- Ongesorteerde array
- Toevoegen van elementen kan in constante tijd
- Zoeken van elementen kan in lineaire tijd, O(n)
- Gesorteerde array
- Toevoegen van elementen tijdrovend
- Zoeken kan heel snel met behulp van binary search in O(log(n))
Invariant Predikaat over je variabelen en data, waarvoor je zorgt dat die true is vóór en na
elke slag van de loop
Variant Predikaat dat er op een gegeven moment voor zorgt dat de loop terminated wordt
Sorting
Insertion Sort
- Begint vooraan in input en elk element wordt op de juiste positie gezet door alles
beneden de positie (links ervan) van het betreffende element naar rechts op te schuiven
zolang het groter dan of gelijk aan de waarde van het element is
- Invariant: A[0 .. i] is gesorteerd (en bestaat uit dezelfde keys als input)
- Binary search helpt om het aantal vergelijkingen te reduceren, maar het aantal
elementen dat je moet opschuiven blijft gelijk
- 2 keer zoveel keys betekent 4 keer zoveel tijd, want je moet niet alleen 2 keer meer
keys invoegen, maar het duurt ook 2 keer zo lang, dus O(n2)
- Insertion Sort kan worden gebruikt bij weinig elementen of bij presorted keys, als de lijst
al ongeveer op de goede volgorde staat, bijvoorbeeld door random waarschijnlijkheid
- Kan in O(n) tijd als de rang van A[i] tussen i - x en i + x (als x < n) zonder iets aan te
passen, elk element hoeft hoogstens x plekken opgeschoven te worden
Selection Sort
- Begin vooraan in output en zet op plek A[i] de kleinste waarde uit A[i .. n]
- Invariant: A[0 .. i] is gesorteerd (en bestaat uit de i kleinste keys)
- Profiteert niet van gunstige input volgorde, altijd O(n2)
- Slechts O(n) data verplaatsingen, wat wel gunstig kan zijn
- Kan in O(n) tijd als de rang van A[i] tussen i - x en i + x ligt (als x < n) door alleen maar
te zoeken in de eerste x elementen van het ongesorteerde deel
QuickSort
- Pak een random key als pivot en vergelijk de rest met de pivot om twee groepen te
vormen (Partition/Split) die nu apart van elkaar gesorteerd kunnen worden, omdat het
eerste blok altijd <= pivot en tweede blok >= pivot
- Kan ongunstig uitpakken met random key, dus bijvoorbeeld 3 random keys en daarvan
de middelste gebruiken
- Kan als pivot ook eerste, achterste of middelste element pakken, maar succes
hiervan is afhankelijk van de input volgorde
- Parameters: array om te sorteren en gebied daarbinnen om te sorteren
1
, - Eerste plek en lengte: QS(A, 4, 4)
- Eerste plek en laatste: QS(A, 4, 7)
- Eerste en eerste niet-meetellende: QS(A, 4, 8) (aantal elementen is 8 - 4)
- Invariant voor Split methode:
- p <= i < r : A[i] <= pivot
- i = r : A[i] = pivot
- s < i < q : A[i] > pivot
- Omvang van onbekende stuk is (s - r), dus variant
- Snelheid
- Bij weinig keys is insertion sort sneller, dus in de QS methode kun je daar een
check voor toevoegen
- Hoe vaak doet een bepaalde key mee met een split?
- Een Split i is snel als de omvang van het block ¾ van het vorige blok is
en anders langzaam
- X doet hoogstens mee in 4/3log n snelle splits
- Elke split heft kans >= ½ om snel te zijn (vier kwartielen)
- Per key verwachten we 4/3log n / ½ = 4,8 lg n nodig
- In totaal dus n・4,8・lg n = O(n・lg n)
Bernoulli: het verwachte aantal pogingen tot het Se succes bij slaagkans p is S / p
- 10 lampen nodig, 50% kans om uit de bak een goede lamp te pakken, dan is de
verwachting .5 = 20 pogingen tot je 10 goede lampen hebt
In situ/In-place Een algoritme is in situ als het de array sorteert zonder extra tijdelijk
geheugenruimte nodig te hebben om de data op te slaan
- Zoals Selection, Insertion, BubbleSort, ShellSort, QuickSort en HeapSort
- Maar niet Counting Sort, BucketSort en MergeSort
Counting sort
- Aanname: keys komen uit (kleine) verzameling van M elementen
- Extra geheugen nodig om counters bij te houden
- Totale tijd: O(n) voor het tellen, O(M) voor de cumulatief en O(n) voor het omstapelen,
dus O(n + M), want je weet niet welke van n of M de grootste is
- Stabiele sorteermethode, maar extra array nodig
Radix sort
- Aanname: elke key bestaat uit een vast aantal stukjes, waarop een lexicografische
ordening bestaat
- Sorteert in fases, waarbij elke fase op één van de stukjes (dag/maand/eeuw/jaar)
sorteert, beginnend bij het minst-significante stukje (dag)
- In combinatie met Counting Sort
Bucket sort
- Aanname: keys zijn uniform verdeeld over een bekend interval
2
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 Suniht. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €8,99. Vous n'êtes lié à rien après votre achat.
