hoe Quicksort werkt
Quicksort (vooral in-place Quicksort) kan een beetje verwarrend zijn, dus laten we een voorbeeld doorlopen om te laten zien hoe dit sorteeralgoritme werkt.
Stel je voor dat we de volgende array te sorteren:
laten we Nu eens kiezen wat we noemen een “pivot point”., Het doel is om de array zodanig te herschikken dat alle elementen minder dan de pivot zijn naar links, en alle elementen groter dan de pivot zijn naar rechts. De keuze van het draaipunt is willekeurig; het kan het eerste element van de array zijn, het laatste element van de array, of zelfs een willekeurig element! Voor onze doeleinden echter, laten we het draaipunt kiezen om het laatste element in de array te zijn, 5.,
na het herschikken van de array rond het draaipunt 5, moeten we de volgende array verkrijgen:
We volgen dan recursief de bovenstaande procedure voor de subarrays links en rechts van het draaipunt.
De subarray links van het draaipunt is slechts één element. Het heeft geen zin om een array van lengte één te sorteren, dus er is hier niets te doen!,
aan de andere kant is de subarray rechts van het draaipunt niet zo triviaal. Na de hierboven beschreven procedure, laten we kiezen 7 om het nieuwe draaipunt voor deze subarray.,”>
Na het rangschikken van de elementen van de subarray rond het scharnierpunt, dan krijgen we het volgende:
Door te blijven recursief, en het samenvoegen van de links subarray met de pivot en de juiste subarray, een gesorteerd array geretourneerd.,
