* Als `i>=j`, is de partitie voltooid. Verwissel het draaipunt met `arr[j]`. Het draaipunt bevindt zich nu in de gesorteerde positie.
3. Recursie: Het algoritme roept zichzelf recursief aan op de twee subarrays:
* De subarray *links* van het (nu gesorteerde) draaipunt.
* De subarray *rechts* van het (nu gesorteerde) draaipunt.
Voorbeeld:
Laten we zeggen dat we de array hebben:`[7, 2, 1, 6, 8, 5, 3, 4]`
1. Draaiselectie: Draaipunt =`7` (eerste element)
2. Partitionering:
* Initieel:`[7, 2, 1, 6, 8, 5, 3, 4]`
* `i` begint bij 2, `j` begint bij 4.
* `i` beweegt totdat hij 8 vindt (wat> 7 is).
* `j` beweegt totdat hij 4 vindt (wat <=7 is).
* Wissel 8 en 4 om:`[7, 2, 1, 6, 4, 5, 3, 8]`
* `i` beweegt totdat hij 5 vindt.
* `j` beweegt totdat hij 3 vindt.
* Wissel 5 en 3 om:`[7, 2, 1, 6, 4, 3, 5, 8]`
* `i` beweegt totdat hij 5 vindt.
* `j` beweegt totdat hij (opnieuw) 3 vindt.
* ik>=j. Verwissel draaipunt (7) met arr[j] (3):`[3, 2, 1, 6, 4, 7, 5, 8]`
* Draaipunt (7) staat nu in de juiste positie.
3. Recursie:
* Quicksort wordt aangeroepen op `[3, 2, 1, 6, 4]`
* Quicksort wordt aangeroepen op `[5, 8]`
Visualisatieoverwegingen:
De visualisatie zou moeten laten zien:
* De draaipunt markeren: Geef duidelijk aan welk element momenteel als spil is geselecteerd. Een kleurverandering of een visueel label is gebruikelijk.
* Aanwijzerbeweging: Laat visueel zien dat de 'i'- en 'j'-aanwijzers door de array bewegen. Gebruik pijlen, verschillende kleuren of andere indicatoren.
* Wisselen: Animeer het verwisselen van elementen. De twee elementen die worden verwisseld, kunnen bijvoorbeeld naar elkaars posities "bewegen".
* Partitioneringsproces: Benadruk hoe de elementen rond het draaipunt worden herschikt. Het kan daarbij gaan om kleurelementen waarvan bekend is dat ze kleiner of groter zijn dan het draaipunt.
* Recursieve oproepen: Laat zien hoe de array in subarrays wordt verdeeld en hoe het algoritme recursief op elke subarray wordt toegepast. Dit kan worden gedaan door de arrayrepresentaties visueel te "nesten". Gebruik eventueel verschillende achtergronden voor elk recursieniveau.
* Gesorteerde elementen: Geef aan welke elementen op hun uiteindelijke gesorteerde positie zijn geplaatst. Gebruik een aparte kleur of een visuele markering.
* Stapsgewijze uitvoering: Laat de gebruiker het algoritme stap voor stap doorlopen, zodat hij elke actie duidelijk kan zien.
* Statusinformatie: Geef de huidige waarden van `i`, `j` en andere relevante variabelen weer.
Visualisatietechnologieën:
* JavaScript en HTML5 Canvas: Een populaire keuze voor webgebaseerde visualisaties. Bibliotheken zoals D3.js of p5.js kunnen helpen met de visuele elementen.
* Python (met bibliotheken zoals Pygame of Matplotlib): Voor desktoptoepassingen.
* Andere grafische bibliotheken: Afhankelijk van de omgeving kunnen andere bibliotheken zoals Processing, Qt of OpenGL worden gebruikt.
Het probleem met de selectie van draaipunten in het eerste element
Hoewel eenvoudig te implementeren, heeft het altijd kiezen van het eerste element als draaipunt een aanzienlijk nadeel:
* Worstcasescenario: Als de array al (of bijna) in oplopende of aflopende volgorde is gesorteerd, degenereert het algoritme naar O(n^2) tijdscomplexiteit. Dit komt omdat elke partitie slechts *één* element uit de subarray verwijdert, wat leidt tot zeer ongebalanceerde partities.
Voorbeeld van het ergste geval:
Als de array `[1, 2, 3, 4, 5]` is, en 1 altijd het draaipunt is:
1. Pivot =1. Partitioneren resulteert in `[1, 2, 3, 4, 5]` (1 staat op de juiste plaats).
2. Sorteer recursief `[2, 3, 4, 5]`
3. Pivot =2. Partitioneren resulteert in `[2, 3, 4, 5]` (2 staat op de juiste plaats).
4. Sorteer recursief `[3, 4, 5]`
... enzovoort.
Het algoritme wordt in wezen een zeer inefficiënte selectiesoort.
Hoe visualisatie helpt:
De visualisatie laat dit worstcasegedrag duidelijk zien. Je zult zien dat het partitieproces veel tijd nodig heeft om elementen te verplaatsen, en dat de recursieve aanroepen zeer onevenwichtige subarrays creëren. Dit maakt het heel duidelijk waarom deze eenvoudige strategie voor het selecteren van draaipunten in de praktijk vaak niet de beste keuze is. De visualisatie kan ook laten zien hoe andere methoden voor het selecteren van een draaipunt (zoals het kiezen van een willekeurig element) dit worstcasescenario kunnen vermijden.
