Quicksort

Quicksort is een van de meest gebruikte sorteeralgoritmen. Het kiest een pivot, splitst de lijst in de waarden die kleiner zijn dan de pivot en de rest, en sorteert beide kanten op dezelfde manier. Het is in de praktijk snel en heeft geen extra lijst nodig, maar hoe snel hangt af van de pivot.

Staven gepartitioneerd rond een pivotstaaf: kleinere staven aan de ene kant, grotere aan de andere, de pivot ertussen
Staven gepartitioneerd rond een pivotstaaf: kleinere staven aan de ene kant, grotere aan de andere, de pivot ertussen

Het idee

Kies één waarde als pivot. Herschik de lijst zodat elke waarde die kleiner is dan de pivot ervoor komt en elke andere waarde erachter. Dat herschikken heet een partitie, en daarna staat de pivot precies waar hij in de gesorteerde lijst hoort. De twee kanten zijn nu losse problemen: sorteer elk ervan met quicksort. Een kant met één waarde of geen is al gesorteerd.

De partitie, stap voor stap

De app gebruikt de Lomuto-partitie. De pivot gaat naar het eind van het deel. Een markering begint aan het begin: alles ervoor is kleiner dan de pivot. Elke andere waarde wordt met de pivot vergeleken; is die kleiner, dan wordt ze naar de markering verwisseld en schuift de markering één plek op. Aan het eind wordt de pivot naar de markering verwisseld. Neem 5, 1, 4, 2, 8 met de laatste waarde als pivot: alle vier de waarden zijn kleiner dan 8, dus 8 blijft aan het eind. Het deel 5, 1, 4, 2 wordt gepartitioneerd rond 2, wat 1, 2, 4, 5 geeft, en 4, 5 rond 5. Dat zijn 8 vergelijkingen, 2 verwisselingen en 3 partities.

Goede en slechte pivots

Als elke pivot in het midden uitkwam, zou elke partitie het probleem halveren en zou het sorteren ongeveer n log₂ n vergelijkingen kosten. Op een willekeurige lijst zijn de pivots zelden perfect maar meestal goed genoeg: voor 40 willekeurige waarden telt de app ongeveer 190 vergelijkingen. Het slechtste geval ontstaat als de pivot steeds de kleinste of grootste waarde is. Met de laatste waarde als pivot gebeurt precies dat bij een lijst die al gesorteerd of omgekeerd is: elke partitie haalt alleen de pivot weg, en het sorteren kost n(n − 1)/2 vergelijkingen, 780 voor 40 waarden.

De pivot kiezen

Een willekeurige pivot maakt het slechtste geval voor elke invoer uiterst onwaarschijnlijk, omdat geen enkele volgorde hem kan misleiden. De mediaan van drie, de middelste waarde van het eerste, middelste en laatste element, is goedkoop en gaat goed om met gesorteerde en omgekeerde lijsten. Probeer beide op een gesorteerde lijst in de app en de vergelijkingen dalen van 780 naar ongeveer 150. Veel gelijke waarden zijn een ander probleem: ze komen allemaal aan één kant van de pivot. Een driewegpartitie, die de waarden gelijk aan de pivot in een middendeel houdt, lost dat op.

Geschiedenis en gebruik

Tony Hoare bedacht quicksort in 1959 en publiceerde het in 1961. Zijn eigen partitie zoekt vanaf beide kanten en doet minder verwisselingen; de eenvoudigere Lomuto-versie die hier te zien is, werd populair via studieboeken. Quicksort sorteert in-place en de binnenste lus is heel kort, dus het is in de praktijk meestal sneller dan mergesort, al is het niet stabiel. Introsort, het sorteeralgoritme achter de standaardbibliotheek van C++, draait quicksort en schakelt over op heapsort als de partities te ongelijk worden, zodat het slechtste geval n log n blijft.

Tony Hoare, die in 1959 quicksort bedacht en het in 1961 publiceerde.
Tony Hoare, die in 1959 quicksort bedacht en het in 1961 publiceerde.

Probeer het zelf

Open de app en druk op Stap. Het deel dat gepartitioneerd wordt is gearceerd, de pivot heeft een eigen kleur, en de stippellijn markeert het eind van het linkerdeel, de waarden die kleiner zijn dan de pivot. Elke pivot wordt groen als hij zijn definitieve plek bereikt. Kies een gesorteerde lijst en de laatste waarde als pivot, schakel dan over naar de mediaan van drie, en vergelijk de tellers.

Veelgestelde vragen

Wat is de tijdcomplexiteit van quicksort?

O(n log n) gemiddeld en met goede pivots, O(n²) in het slechtste geval. Het sorteert in-place; de recursie heeft O(log n) extra geheugen nodig als de kleinere kant eerst gesorteerd wordt.

Wat is het verschil tussen de Lomuto- en de Hoare-partitie?

Lomuto houdt één markering bij en loopt van links naar rechts, wat makkelijk te volgen is en wat deze app laat zien. Hoare loopt vanaf beide kanten naar elkaar toe en verwisselt paren die aan de verkeerde kant staan, wat gemiddeld ongeveer drie keer minder verwisselingen oplevert.

Waarom is quicksort traag als veel waarden gelijk zijn?

Waarden gelijk aan de pivot gaan allemaal naar dezelfde kant, dus een lijst met weinig verschillende waarden splitst ongelijk, en een lijst van gelijke waarden is net zo slecht als het slechtste geval. Een driewegpartitie die de waarden gelijk aan de pivot in het midden verzamelt, voorkomt dat.

Is quicksort stabiel?

Nee. Verwisselingen tijdens een partitie verplaatsen waarden over grote afstanden, dus gelijke waarden kunnen van volgorde veranderen.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Probeer quicksort