Quick Sort lijkt veel op merge sort in de zin dat dit algoritme programmeurs helpt bij het verdelen en veroveren. Het kiest elementen als een spil, waarna het partities maakt in de array. Quick sort kent vele versies en elk van hen kiest de spil anders.

Het commando partition() is misschien wel het belangrijkste onderdeel van quick sort. Partition() ontvangt een matrix samen met een x matrixelement als spil. Je moet de x in de juiste positie plaatsen, dat is de gesorteerde array, die zal worden gevolgd door het plaatsen van elementen die kleiner zijn dan x ervoor. Tenslotte moet je elementen groter dan x erna plaatsen. Zorg ervoor dat je dit alles in lineaire tijd doet.

Het is ook de moeite waard om in gedachten te houden dat quick sort partities in arrays maakt, waarna het zichzelf twee keer in herhaling aanroept voor het sorteren van de subarrays die er uit voortkomen. Een algoritme als dit komt ongelooflijk van pas voor grote gegevensverzamelingen. Dit komt omdat O(n2) zijn worst-case complexiteit is. De twee initiële termen zijn er voor recursieve aanroepen, terwijl de laatste term van pas komt in het partitieproces. De elementen kleiner dan de spil worden voorgesteld door k.

De tijd die quick sort gewoonlijk in beslag neemt, hangt af van de partitiestrategie, samen met de input array.

De drie gevallen van Quick Sort

Net als diverse andere sorteeralgoritmen kent quick sort ook case-scenario’s. We bespreken ze hieronder:

Slechtste geval

Dit type geval doet zich voor wanneer het partitieproces het kleinste of grootste element als spil kiest. Gezien de eerder besproken partitiestrategie, waarbij telkens het laatste element als spil wordt gekozen, zal het slechtste scenario zich voordoen zodra de matrix in aflopende of oplopende volgorde wordt gesorteerd. De herhaling voor het slechtste geval is als volgt:

T(n) = T(0) + T(n-1) + (n)wat equivalent is met T(n) = T(n-1) + (n)

Beste geval

De beste plaats vindt plaats wanneer het partitieproces het middelste element als spil kiest. De herhaling voor het beste geval is als volgt:

T(n) = 2T(n/2) + (n)

Gemiddeld geval

Men moet elke matrixpermutatie beschouwen en de tijd berekenen die elke permutatie nodig heeft om een case-analyse uit te voeren. Dit proces kan natuurlijk behoorlijk ingewikkeld zijn, zelfs voor ervaren programmeurs. Als we echter het geval beschouwen waarin de partitie O(n/9) plaatst samen met O(9n/10) elementen, dan kunnen we een schatting maken van het gemiddelde geval. De herhaling van dit geval is als volgt.

T(n) = T(n/9) + T(9n/10) + (n)

Veel gestelde vragen over Quick Sort

Hoewel er veel vragen worden gesteld over quick sort, zijn de hieronder genoemde waarschijnlijk de meest voorkomende:

Is quick sort een stabiel algoritme?

Nou, de standaard implementatie van quick sort heeft geen stabiliteit. Dat gezegd hebbende, is het mogelijk om stabiliteit toe te voegen aan sorteeralgoritmen door de index te beschouwen als een parameter voor vergelijking.

Wat is drieweg quick sort?

Bij een regulier quick sort algoritme kiezen we een element om als spil te fungeren, maken een partitie in de array. Daarna maken we een recursie voor de subarrays die aan de rechter- en linkerkant van de pivot staan.

Is Quick Sort een in-place algoritme?

Volgens de brede definitie van het in-place algoritme, valt quick sort inderdaad onder dit type sorteeralgoritme. Dit komt omdat het extra ruimte gebruikt om recursieve functie-aanroepen op te slaan. De invoer wordt echter op geen enkele manier gemanipuleerd.

Sneller dan de meeste sorteeralgoritmen

Hoewel niet te ontkennen valt dat de worst-case tijdcomplexiteit van quick sort O(n2) is, meer dan heap sort, merge sort en talloze andere sorteeralgoritmen, is quick sort toevallig ongelooflijk snel. Een van de redenen hiervoor is dat je de binnenste lus efficiënt kunt implementeren in verschillende soorten echte wereldgegevens en -architecturen.
Bovendien kunt u quick sort op verschillende manieren implementeren, eenvoudig door de keuze van de spil te veranderen. Dit minimaliseert het optreden van worst-case voor elk gegevenstype. Dat gezegd hebbende, geven programmeurs over het algemeen de voorkeur aan merge sort als er te veel gegevens zijn, vooral als die zich in externe opslag bevinden.

Hoe zit het met het gebruik van Quick Sort in gekoppelde lijsten?

Bij gelinkte lijsten liggen de zaken heel anders vanwege de verschillen in de geheugentoewijzing van de array. Nodes van gelinkte lijsten zijn heel anders dan arrays en liggen vaak niet naast elkaar in het geheugen. Bovendien kun je in gelinkte lijsten items in het midden invoeren, iets wat in arrays niet mogelijk is. In dergelijke scenario’s geven programmeurs de voorkeur aan merge sort, omdat dit een betere optie is dan quick sort.

Waarom programmeurs de voorkeur geven aan Quick Sort om arrays te sorteren

In de kern is quick sort een eenvoudige in-place sort, wat betekent dat het geen extra opslagruimte nodig heeft. Aan de andere kant heeft merge sort O(N) extra opslagruimte nodig. Voor wie het zich afvraagt, de N staat voor de grootte van de array, die ongelofelijk groot kan zijn. Het de-alloceren en toewijzen van de extra ruimte die nodig is voor merge sort verhoogt de draaitijd van het algoritme.

Als we de gemiddelde complexiteit vergelijken, is het gemakkelijk te zien dat de gemiddelde complexiteit van beide sorteertypes O(NlogN) is. Hun constanten hebben echter de neiging te verschillen. Als het om arrays gaat, slaagt merge sort niet omdat het de extra O(N) opslagruimte gebruikt. De meest praktische quick sort implementaties maken gebruik van de gerandomiseerde versie. De gemiddelde tijd complexiteit van deze versie is O(nLogn). Het is ook de moeite waard om in gedachten te houden dat er een mogelijkheid is van een slechter geval met de gerandomiseerde versie. Dit doet zich echter niet voor bij specifieke patronen zoals gesorteerde arrays.

Het quick sort algoritme is heel cache-vriendelijk vanwege de uitstekende lokalisatie van verwijzing, vooral als je het gebruikt voor arrays. Bovendien is quick sort recursief, wat betekent dat je tail call optimalisaties moet uitvoeren.