AlgoI (09-10): reeks 9
Algoritmen I (2009-2010)
reeks 9: quicksort
Eenvoudige versie
Implementeer het quicksort algoritme zoals in de cursus, waarbij
het spilelement telkens het meest linkse van de partitie is.
Hoe kun je testen of je methode werkt?
Meet de performantie van het algoritme voor verschillende vectoren:
een vector met willekeurige elementen
een reeds gesorteerde vector
een omgekeerd gesorteerde vector
Hier kun je gebruik maken van
perform.h
stopwatch.h
Random spil
Maak een nieuwe versie waarbij je als spil (pivot) een
element op een willekeurige plaats in de partitie neemt.
Tip: Kopieer de eerste versie in een nieuwe namespace.
Meet de performanties en vergelijk met je eerste versie.
Driewegvariant
Een variant van quicksort bestaat erin drie partities te maken. De derde
(middelste) partitie bevat alle elementen die gelijk zijn aan het spilelement.
Meestal gebeurt dit als volgt:
Bij het doorlopen van links naar rechts worden duplicaten van de spil naar
links verplaatst. En vice versa voor rechts. Schematisch:
| gelijk | kleiner | groter | gelijk |
Op het einde worden de twee duplicatenpartities naar het midden verplaatst:
Maak een implementatie.
| 
Algemeen