Sortarea rapidă este un algoritm de sortare extrem de eficient și se bazează pe partiționarea matricei de date în matrici mai mici. O matrice mare este partiționată în două matrice dintre care una conține valori mai mici decât valoarea specificată, să spunem pivot, pe baza căreia este făcută partiția și o altă matrice deține valori mai mari decât valoarea pivotului.
partițiile Quicksort și array și apoi se numește recursiv de două ori pentru a sorta cele două subarrayuri rezultate. Acest algoritm este destul de eficient pentru seturile de date de dimensiuni mari, deoarece complexitatea sa medie și cea mai gravă sunt O (n2), respectiv.
Partiția în sortare rapidă
Următoarea reprezentare animată explică cum pentru a găsi valoarea pivotului într-o matrice.
Valoarea pivotului împarte lista în două părți. Și recursiv, găsim pivotul pentru fiecare sub-listă până când toate listele conțin un singur element.
Algoritmul de pivotare a sortării rapide
Pe baza înțelegerii noastre despre partiționarea în sortare rapidă, vom acum încercați să scrieți un algoritm pentru acesta, care este după cum urmează.
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
Pseudocod pivot de sortare rapidă
Pseudocodul pentru algoritmul de mai sus poate fi derivat ca –
Algoritm de sortare rapidă
Folosind algoritmul pivot recursiv, ajungem cu partiții posibile mai mici. Fiecare partiție este apoi procesată pentru sortare rapidă. Definim algoritmul recursiv pentru quicksort după cum urmează –
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
Pseudocod de sortare rapidă
Pentru a intra mai mult în el, să vedem pseudocodul pentru algoritm de sortare –
Pentru a afla despre implementarea rapidă de sortare în limbajul de programare C, faceți clic aici.