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
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 Suniht. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $9.72. You're not tied to anything after your purchase.
