Scribd
Încărcați
143 vizualizări4 pagini

Sortare Rapida QuickSort

Algoritmul sortării rapide (quicksort) împarte tabloul în două părți folosind o valoare pivot, apoi sortează recursiv fiecare parte. Se alege un pivot, se rearanjează elementele astfel încât cele mai mari decât pivotul să fie în dreapta și cele mai mici în stânga, iar apoi se aplică recursiv algoritmul pe cele două părți.

Încărcat de

pmax007
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 PPTX, PDF, TXT sau citiți online pe Scribd
143 vizualizări4 pagini

Sortare Rapida QuickSort

Algoritmul sortării rapide (quicksort) împarte tabloul în două părți folosind o valoare pivot, apoi sortează recursiv fiecare parte. Se alege un pivot, se rearanjează elementele astfel încât cele mai mari decât pivotul să fie în dreapta și cele mai mici în stânga, iar apoi se aplică recursiv algoritmul pe cele două părți.

Încărcat de

pmax007
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 PPTX, PDF, TXT sau citiți online pe Scribd

SORTAREA RAPIDĂ

(QUICKSORT)
(tablouri unidimensionale)
Descriere
Metoda divide et impera este utilizată în sortarea rapidă (varianta recursivă):
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. Partiționare. Se rearanjează elementele în așa fel încât, toate elementele care sunt mai mari
decât pivotul se transferă în partea dreaptă a tabloului. Valorile egale cu pivotul pot sta în orice
parte a tabloului. În plus, tabloul poate fi împărțit în părți care nu au aceeași dimensiune (nu
sunt egale).
3. Se sortează amândouă părțile. Se aplică recursiv algoritmul de sortare rapidă în partea
stângă şi în partea dreaptă.
Algoritmul de partiție în detaliu.

Există 2 indici i şi j, şi la începutul algoritmului de partiționare i indică primul


element al tabloului, iar j indică ultimul element din tablou (i<j).
La pasul următor algoritmul mută i înainte, până când un element cu o valoare
mai mare sau egală cu pivotul este găsită. Indicele j este mutat înapoi, până când
un element cu valoare mai mică sau egală cu pivotul este găsită.
Dacă i<=j atunci i merge pe poziția i+1, iar j merge pe poziția j-1.
Algoritmul se oprește când i >j.
procedure quickSort (var v : vector; st, dr : integer);
var pivot, i, j, aux, m : integer;
begin
i:=st; j:=dr; m:=(st+dr) div 2;
pivot:=v[m];
while i<=j do begin
while v[i] < pivot do i:=i+1;
while v[j] > pivot do j:=j-1;
if i<=j then begin
aux:=v[i]; v[i] :=v[j]; v[j] :=aux;
i:=i+1;
j:=j-1;
end;
end;
if st<j then quickSort (v, st, j);
if i<dr then quickSort (v, i, dr);
end;

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