Hoe snel sorteren werkt:

1. Verdelen: Kies een pivot-element uit de array (vaak het laatste element).

2. Partitie: Herschik de array zodanig dat alle elementen kleiner dan het draaipunt zich links van het draaipunt bevinden, en alle elementen groter dan het draaipunt rechts. Het draaielement bevindt zich in de uiteindelijke gesorteerde positie.

3. Recursie: Herhaal de bovenstaande twee stappen voor de linker en rechter subarrays, waarbij u ze recursief opsplitst totdat elke subarray slechts één element bevat.

Voorbeeld 1:

Beschouw de array [5, 3, 8, 2, 1, 4].

A. Verdelen:Kies het laatste element, 1 als draaipunt.

B. Partitie:

- Herschik de array:[3, 2, 1, 5, 4, 8] (1 bevindt zich in de gesorteerde positie).

C. Recursief:

- Linker subarray:[3, 2, 1] (al gesorteerd)

- Rechter subarray:[5, 4, 8] (Quick Sort recursief toepassen)

Nadat Quick Sort op beide subarrays is toegepast, is de uiteindelijk gesorteerde array:[1, 2, 3, 4, 5, 8].

Voorbeeld 2:

Een grotere array sorteren

Beschouw een array [7, 2, 9, 5, 3, 4, 1, 8, 6].

A. Verdelen:Kies het laatste element, 6, als draaipunt.

B. Partitie:

- Herschik de array:[2, 5, 3, 4, 1, 7, 9, 6] (6 bevindt zich in de gesorteerde positie).

C. Recursief:

- Linker subarray:[2, 5, 3, 4, 1] (Quick Sort recursief toepassen)

- Rechter subarray:[7, 9] (reeds gesorteerd)

Na het voltooien van de recursieve aanroepen is de gesorteerde array:[1, 2, 3, 4, 5, 6, 7, 8, 9].

Tijdcomplexiteit:

- Beste geval:O(n log n)

- Gemiddeld geval:O(n log n)

- Worst-Case:O(n^2) (treedt op wanneer de array al is gesorteerd of omgekeerd is gesorteerd)

Over het geheel genomen biedt het Quick Sort-algoritme een efficiënte sorteeroplossing met een goede gemiddelde tijdscomplexiteit van O(n log n). Door zijn eenvoud en veelzijdigheid is het een populair algoritme geworden voor het sorteren van taken in verschillende programmeertalen.