Quicksort: definitie en werking van het snelle verdeel-en-heers sorteeralgoritme

Werking in eenvoudige stappen

1. Kies een pivot: selecteer één element uit de array (bijv. het eerste, laatste, middelste, of een willekeurig element).
2. Partitioneer: herschik de array zo dat alle elementen kleiner dan de pivot links staan en alle elementen groter dan de pivot rechts (elementen gelijk aan de pivot kunnen links, rechts of tussenin komen, afhankelijk van de partitiemethode).
3. Herhaal recursief: pas Quicksort toe op de linker- en rechterdeelarrays totdat elk deel triviaal (lengte 0 of 1) is.

Partitioneringsmethoden

Er bestaan meerdere varianten om te partitioneren. Twee veelgebruikte zijn:

• Lomuto-partitie (eenvoudig te implementeren, maar soms minder efficiënt): kiest vaak het laatste element als pivot en loopt met één index door de array om elementen kleiner dan de pivot naar links te verplaatsen.
• Hoare-partitie (origineel van Hoare): gebruikt twee aanwijzers van beide kanten en is doorgaans iets efficiënter en doet minder swaps in de praktijk.

Naast deze basismethoden bestaan er varianten zoals three-way partitioning (Dijkstra's Dutch National Flag) die handig is wanneer veel dubbele waarden aanwezig zijn: dan wordt in één stap verdeeld in kleiner, gelijk en groter dan pivot.

Voorbeeldpseudocode (kort)

Lomuto-partitie (vereenvoudigd):

 function partition(A, lo, hi):     pivot = A[hi]     i = lo     for j from lo to hi-1:         if A[j] <= pivot:             swap A[i], A[j]             i = i + 1     swap A[i], A[hi]     return i 

Quicksort (recursief):

 function quicksort(A, lo, hi):     if lo < hi:         p = partition(A, lo, hi)         quicksort(A, lo, p-1)         quicksort(A, p+1, hi) 

Tijd- en ruimtecomplexiteit

• Gemiddelde tijdcomplexiteit: O(n log n) — dit verklaart waarom Quicksort in de praktijk snel is.
• Beste geval: O(n log n) — wanneer partitionering steeds balans geeft.
• Worst case: O(n²) — bijvoorbeeld als je telkens de kleinste of grootste als pivot kiest op reeds gesorteerde input.
• Ruimtecomplexiteit: gemiddeld O(log n) extra ruimte door recursie (in-place variant gebruikt geen extra array). Slechtste geval O(n) recursiediepte zonder optimalisaties.
• Stabiliteit: Quicksort is van nature niet-stabiel (gelijke elementen kunnen van volgorde veranderen) tenzij speciale maatregelen worden genomen.

Praktische optimalisaties

• Randomized pivot: kies de pivot willekeurig om de kans op het worst case te verkleinen.
• Median-of-three: kies de pivot als de mediaan van bijvoorbeeld het eerste, middelste en laatste element om slechte partities te vermijden.
• Three-way partitioning: efficiente handelwijze bij veel gelijke elementen (verdeelt in <, =, > pivot).
• Gebruik insertion sort op kleine subarrays: voor kleine n is insertion sort vaak sneller; vaak wordt een drempel (bv. n < 10–20) gebruikt.
• Tail-recursion eliminatie / iteratieve implementatie: reduceert recursiediepte en voorkomt stapel-overloop; Quicksort kan gemodeerd worden met een expliciete stack of door altijd de kleinere helft recursief te verwerken en de grotere iteratief.
• Introsort: combineer Quicksort met Heapsort als de recursiediepte te groot wordt, zodat je gegarandeerd O(n log n) worst-case krijgt.

Wanneer Quicksort gebruiken?

Quicksort wordt vaak gebruikt in bibliotheken en toepassingen omdat het in de praktijk doorgaans sneller is dan andere O(n log n) algoritmen door lage constante factoren en goede cachelocaliteit. Als stabiliteit vereist is of je gegarandeerd O(n log n) in het slechtste geval nodig hebt, zijn respectievelijk mergesort of heapsort (of introsort) betere keuzes.

Kort samengevat: Quicksort is een snelle, in-place, niet-stabiele sorteermethode gebaseerd op verdeel-en-heers. Met slimme pivotkeuze en optimalisaties is het in veel praktische situaties de beste keuze.