Scribd
Încărcați
69 vizualizări22 pagini

Quick Sort

Algoritmul de sortare rapidă (QuickSort) utilizează metoda divide et impera și partionarea pentru a sorta un tablou de valori. Se alege un element pivot și se rearanjează elementele astfel încât toate valorile mai mari decât pivotul să fie la dreapta sa, iar cele mai mici la stânga. Se aplică recursiv algoritmul asupra celor două părți rezultate până când tabloul este complet sortat.

Încărcat de

Catalina Alexandra Bran
Drepturi de autor
© All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca PPT, PDF, TXT sau citiți online pe Scribd
69 vizualizări22 pagini

Quick Sort

Algoritmul de sortare rapidă (QuickSort) utilizează metoda divide et impera și partionarea pentru a sorta un tablou de valori. Se alege un element pivot și se rearanjează elementele astfel încât toate valorile mai mari decât pivotul să fie la dreapta sa, iar cele mai mici la stânga. Se aplică recursiv algoritmul asupra celor două părți rezultate până când tabloul este complet sortat.

Încărcat de

Catalina Alexandra Bran
Drepturi de autor
© All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca PPT, PDF, TXT sau citiți online pe Scribd

Sortarea rapid (QuickSort)

Descriere
Metoda Divide et Impera este utilizat n sortarea rapid.
Ideea algoritmului:
1. Se alege o valoare pivot. Se ia valoarea elementului din mijloc
ca valoare pivot, dar poate fi oricare alt valoare, care este n
intervalul valorilor sortate, chiar dac nu este prezent n tablou.
2. Partiionare. Se rearanjeaz elementele n aa fel nct, toate
elementele care sunt mai mari dect pivotul merg n partea dreapt
a tabloului. Valorile egale cu pivotul pot sta n orice parte a
tabloului. n plus, tabloul poate fi mprit n pri care nu au
aceeai dimensiune (nu sunt egale).
3. Se sorteaz amndou [Link] aplic recursiv algoritmul de
sortare rapid n partea stng i n partea dreapt.

Algoritmul de partiie n detaliu.


Exist 2 indici i i j, i la nceputul algoritmului de
partiionare i indic primul element al tabloului iar j indic
ultimul element din tablou. La pasul urmtor algoritmul mut i
nainte, pna cnd un element cu o valoare mai mare sau
egal cu pivotul este gsit. Indicele j este mutat napoi, pna
cnd un element cu valoare mai mic sau egal cu pivotul
este gsit. Dac i<=j atunci i merge pe poziia i+1 iar j merge
pe poziia j-1. Algoritmul se oprete, cnd i > j
Exemplu dorim s sortm irul {1, 13, 7, 28, 10, 16, 3, 10, 2}
folosind sortarea rapid.

Nesortat

13 7

28 10 16 3

10 2

Valoarea pivot =10; i=1; j=9.

13 7

28 10 16 3

10 2

13>=10>=2 interschimbm 13 cu 2 crete i, scade j

13 7

28 10 16 3

10 2

28>=10>=10 interschimbam 28 cu 10; crete i, scade j

28 10 16 3

10 13

10>=10>=3 interschimbm 10 cu 3; crete i scade j

10 10 16 3

28 13

i>j se oprete partiionarea

10 3

16 10 28 13

se aplic din nou algoritmul pentru


(1, 2, 7, 10, 3 ) i 1(6, 10, 28, 13)

10 3

16 10 28 13

Pivot=7; i=1, j=5

10 3

16 10 28 13

1<7 crete i

10 3

16 10 28 13

2<7 crete i

10 3

16 10 28 13

7>3 interschimbam 7 cu 3
crete i scade j

10 3

16 10 28 13

10>7 interschimbm 10 cu 7
crete i scade j; i>j - stop

10 7

16 10 28 13

Se aplic algoritmul pentru


partea dreapt Pivot=10

Parte sortat

10

16 10 28 13

16>=10>=13
interschimbm 16 cu 13
crete i scade j

10

16 10 28 13

10>=10 se interschimb
10 cu 10 crete i scade j
i>j se continu
partiionarea

10

13 10 28 16

Se aplica algoritmul pentru


(13 10 ) i (28 16)

10

13 10 28 16

13>=10 se
interschimb 13 cu 10

10

13 10

28 16

28>=16 se
interschimb 28 cu 16

10

10 13

28 16

Vector sortat
1

10 10 13 16 28

Algoritm descris n pseudocod:


quickSort(V,st,dr);
pivotv[(st+dr) div 2)];
ct timp i<=j execut
ct timp v[i] <pivot execut
ii+1;
dac i<=j atunci
auxv[i];
v[i]v[j];
v[j]aux;
ii+1;
jj-1;
dac st<j atunci
quikSort(v,st,j);
dac i<dr atunci
quikSort(v,i,dr);

S-ar putea să vă placă și