Rask sortering er en svært effektiv sorteringsalgoritme og er basert på partisjonering av datautvalg i mindre matriser. En stor matrise er delt inn i to matriser, hvorav den ene har verdier som er mindre enn den angitte verdien, for eksempel pivot, basert på hvilken partisjonen er laget, og en annen matrise har verdier som er større enn pivotverdien.
Quicksort partisjoner en array og kaller seg deretter rekursivt to ganger for å sortere de to resulterende underarrayene. Denne algoritmen er ganske effektiv for store datasett, ettersom den gjennomsnittlige og verst-tilfeldige kompleksiteten er henholdsvis O (n2).
Partisjon i rask sortering
Følgende animerte representasjon forklarer hvordan for å finne pivotverdien i en matrise.
Pivotverdien deler listen i to deler. Og rekursivt, finner vi pivoten for hver underliste til alle lister inneholder bare ett element.
Rask sortering Pivot-algoritme
Basert på vår forståelse av partisjonering i rask sortering, vil vi prøv nå å skrive en algoritme for den, som er som følger.
Step 1 − Choose the highest index value has pivotStep 2 − Take two variables to point left and right of the list excluding pivotStep 3 − left points to the low indexStep 4 − right points to the highStep 5 − while value at left is less than pivot move rightStep 6 − while value at right is greater than pivot move leftStep 7 − if both step 5 and step 6 does not match swap left and rightStep 8 − if left ≥ right, the point where they met is new pivot
Rask sortering Pivot Pseudokode
Pseudokoden for algoritmen ovenfor kan avledes som –
Rask sorteringsalgoritme
Ved å bruke pivotalgoritme rekursivt, ender vi opp med mindre mulige partisjoner. Hver partisjon blir deretter behandlet for rask sortering. Vi definerer rekursiv algoritme for kviksort som følger –
Step 1 − Make the right-most index value pivotStep 2 − partition the array using pivot valueStep 3 − quicksort left partition recursivelyStep 4 − quicksort right partition recursively
Rask sortering av pseudokode
For å få mer inn i det, la oss se pseudokoden for rask sorteringsalgoritme –
Hvis du vil vite om rask sorteringsimplementering i C-programmeringsspråk, kan du klikke her.