* Om `i> =j` är partitioneringen klar. Byt pivoten med `arr [j]`. Pivoten är nu i sin sorterade position.
3. rekursion: Algoritmen kallar sig rekursivt på de två under arrays:
* Under-array till * vänster * på den (nu sorterade) pivoten.
* Sub-array till * höger * för den (nu sorterade) pivoten.
Exempel:
Låt oss säga att vi har matrisen:`[7, 2, 1, 6, 8, 5, 3, 4]`
1. pivotval: Pivot =`7` (första elementet)
2. partitionering:
* Inledande:`[7, 2, 1, 6, 8, 5, 3, 4]`
* `Jag börjar vid 2,` J` börjar vid 4.
* `Jag flyttar tills den hittar 8 (vilket är> 7).
* `J` rör sig tills den hittar 4 (vilket är <=7).
* Byt 8 och 4:`[7, 2, 1, 6, 4, 5, 3, 8]`
* `Jag flyttar tills den hittar 5.
* `J` rör sig tills den hittar 3.
* Byt 5 och 3:`[7, 2, 1, 6, 4, 3, 5, 8]`
* `Jag flyttar tills den hittar 5.
* `J` rör sig tills den hittar 3 (igen).
* i> =j. Swap Pivot (7) med arr [J] (3):`[3, 2, 1, 6, 4, 7, 5, 8]`
* Pivot (7) är nu i rätt position.
3. rekursion:
* Quicksort kallas på `[3, 2, 1, 6, 4]`
* Quicksort kallas på `[5, 8]`
Visualiseringsöverväganden:
Visualiseringen skulle behöva visa:
* Markera pivot: Ange tydligt vilket element som för närvarande är valt som pivot. En färgförändring eller en visuell etikett är vanligt.
* Pointer Movement: Visuellt visa "jag" och "j" -pekarna som rör sig genom matrisen. Använd pilar, olika färger eller andra indikatorer.
* swappar: Animera byte av element. Till exempel kan de två elementen som byts ut "flytta" till varandras positioner.
* Partitioneringsprocess: Betona hur elementen omorganiseras runt pivoten. Detta kan involvera färgelement som är kända för att vara mindre eller större än pivoten.
* Rekursiva samtal: Visa hur matrisen delas upp i under arrays och hur algoritmen tillämpas på varje under-array rekursivt. Detta kan göras genom att visuellt "häcka" arrayrepresentationerna. Kanske använda olika bakgrunder för varje rekursionsnivå.
* sorterade element: Ange vilka element som har placerats i sina slutliga sorterade positioner. Använd en distinkt färg eller en visuell markör.
* steg-för-steg-exekvering: Låt användaren gå igenom algoritmen ett steg åt gången, så att de tydligt kan se varje åtgärd.
* state Information: Visa de aktuella värdena på `i ',` j` och andra relevanta variabler.
Visualiseringstekniker:
* javascript &html5 canvas: Ett populärt val för webbaserade visualiseringar. Bibliotek som d3.js eller p5.js kan hjälpa till med de visuella elementen.
* python (med bibliotek som pygame eller matplotlib): För skrivbordsapplikationer.
* Andra grafikbibliotek: Beroende på miljö kan andra bibliotek som bearbetning, QT eller OpenGL användas.
Problemet med första elementets val av pivot
Även om det är enkelt att implementera, väljer alltid det första elementet eftersom pivoten har en betydande nackdel:
* Worst-Case-scenario: Om matrisen redan är sorterad (eller nästan sorterad) i stigande eller fallande ordning, degenererar algoritmen till O (n^2) tidskomplexitet. Detta beror på att varje partition bara tar bort * ett * element från underordningen, vilket leder till mycket obalanserade partitioner.
Exempel på det värsta fallet:
Om matrisen är `[1, 2, 3, 4, 5]` och 1 är alltid pivot:
1. Pivot =1. Uppdelning resulterar i `[1, 2, 3, 4, 5]` (1 är på rätt plats).
2. Rekursivt sortera `[2, 3, 4, 5]`
3. Pivot =2. Partitionering resulterar i `[2, 3, 4, 5]` (2 är på rätt plats).
4. Rekursivt sortera `[3, 4, 5]`
... och så vidare.
Algoritmen blir i huvudsak ett mycket ineffektivt urvalssortering.
Hur visualisering hjälper:
Visualiseringen visar tydligt detta värsta fall. Du kommer att se partitionsprocessen ta lång tid att flytta element och de rekursiva samtalen som skapar mycket obalanserade underarrayer. Detta gör det mycket uppenbart varför denna enkla strategi för val av pivot ofta inte är det bästa valet i praktiken. Visualiseringen kan också visa hur andra metoder för val av pivot (som att välja ett slumpmässigt element) kan undvika detta värsta fall.
