QuikSort
Het algoritme van QuickSort lijkt op dat van MergeSort. Ook QuickSort maakt gebruik van de divide-and-conquermethode. Toch zijn er enkele belangrijke verschillen. Daardoor pakt onder andere het worstcasescenario van QuickSort minder slecht uit dan dat van MergeSort.
Hieronder zie je een voorbeeld van QuickSort. Een lijst van zes getallen wordt van klein naar groot gesorteerd:
Het QuickSort algoritme werkt als volgt:
- Kies een willekeurig element uit de lijst. Dit element wordt de pivot genoemd.
- Verplaats de elementen als volgt:
- Elementen met een waarde kleiner of gelijk aan de pivot komen links van de pivot.
- Elementen met een waarde groter dan de pivot komen rechts van de pivot.
(Deze stap wordt ook wel het partitioneren genoemd.)
- Voer stappen 1 en 2 uit op de deellijsten links en rechts van de pivot.
- Herhaal stap 3 totdat alles gesorteerd is.
Maak jouw eigen website met JouwWeb