Hurtig sortering er en meget effektiv sorteringsalgoritme og er baseret på partitionering af matrix af data i mindre arrays. Et stort array er opdelt i to arrays, hvoraf den ene indeholder værdier, der er mindre end den angivne værdi, f.eks. Drejning, baseret på hvilken partitionen er lavet, og en anden array holder værdier, der er større end pivotværdien.
Quicksort-partitioner en array og kalder sig derefter rekursivt to gange for at sortere de to resulterende underarrays. Denne algoritme er ret effektiv til store datasæt, da dens gennemsnitlige og worst-case kompleksitet er henholdsvis O (n2).
Partition i hurtig sortering
Efter animeret repræsentation forklares, hvordan for at finde pivotværdien i en matrix.
Pivotværdien opdeler listen i to dele. Og rekursivt finder vi omdrejningspunktet for hver underliste, indtil alle lister kun indeholder et element.
Hurtig sortering Pivotalgoritme
Baseret på vores forståelse af partitionering i hurtig sortering vil vi prøv nu at skrive en algoritme til 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
Hurtig sortering Pivot Pseudocode
Pseudokoden til ovenstående algoritme kan udledes som –
Hurtig sorteringsalgoritme
Ved hjælp af pivotalgoritme rekursivt ender vi med mindre mulige partitioner. Hver partition behandles derefter til hurtig sortering. Vi definerer rekursiv algoritme for quicksort 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
Hurtig sortering af pseudokode
For at få mere ind i det, lad os se pseudokoden for hurtig sorteringsalgoritme –
Hvis du vil vide om hurtig sorteringsimplementering i C-programmeringssprog, skal du klikke her.