Quicksort is een efficiënt sorteeralgoritme dat gebruikmaakt van de techniek van “verdeel en heers”. Het sorteert een lijst door deze te verdelen in twee kleinere sublijsten rondom een zogenaamd “pivot”-element. Daarna worden de sublijsten afzonderlijk gesorteerd.

Hier is een basisstappenplan voor Quicksort:

1. Kies een pivot: Kies een element uit de lijst, het pivot-element. Dit kan op verschillende manieren worden gedaan, zoals het eerste element, het laatste element of een willekeurig element.
2. Partitioneer de lijst: Herorden de lijst zodanig dat alle elementen die kleiner zijn dan het pivot-element links van het pivot komen te staan, en alle elementen die groter zijn rechts van het pivot.
3. Recursief sorteren: Herhaal dit proces recursief voor de sublijsten aan de linker- en rechterkant van het pivot-element.
4. Combineer de resultaten: De gesorteerde sublijsten worden samengevoegd om de uiteindelijke gesorteerde lijst te verkrijgen.

Het cruciale onderdeel van Quicksort is het partitioneren van de lijst rondom het pivot-element. Dit wordt vaak gedaan met behulp van twee pointers die vanaf beide uiteinden van de lijst naar elkaar toe bewegen. Elementen die aan de verkeerde kant van het pivot staan worden verwisseld, totdat alle elementen kleiner dan het pivot links staan en alle elementen groter dan het pivot rechts.

Quicksort heeft een gemiddelde tijdscomplexiteit van O(n log n), wat het een van de snelste sorteeralgoritmes maakt. In het slechtste geval kan het echter O(n^2) tijd kosten, maar dit komt zelden voor als de keuze van het pivot-element goed wordt beheerd, bijvoorbeeld door willekeurig te kiezen.

Schrijf een functie quicksort met een lijst van getallen als parameter die een gesorteerde lijst als returnwaarde heeft.

>>> quicksort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]
>>> quicksort([73, 41, 74, 72, 8, 10, 57, 84, 68, 21])
[8, 10, 21, 41, 57, 68, 72, 73, 74, 84]