Sortarea rapida

Vom discuta acum un algoritm de sortare bazat pe operatia de interschimbare. Am dori sa imbunatatim performanta sortarii prin interschimbare directa, comparand si interschimband intre ele, daca e cazul, componentele aflate la distante mai mari in vector. Algoritmul care urmeaza i se datoreaza lui C. A. R. Hoare si poarta numele de sortare rapida (Quick Sort).

Operatia de baza a acestui algoritm se numeste operatia de partitionare a unui vector A[1..n] cu ajutorul unei valori numita pivot si este descrisa in continuare.

Algoritmul de partitionare al vectorului A[1..n]

Se alege o valoare x din vectorul A[1..n]

(a) Se parcurge de la stanga la dreapta vectorul lasand pe loc componentele cu proprietatea A[i] < x, pana la primul indice i pentru care A[i] ³ x.

(b) Se parcurge de la dreapta la stanga vectorul, lasand pe loc componentele cu proprietatea A[j] > x, pana la primul indice j pentru care A[j] £ x.

Daca i < j atunci se interschimba A[i] cu A[j] si avanseaza indicii pentru parcurgeri (i:=i+1; j:=j-1).

Se repeta pasii 2 si 3 pana cand cele doua parcurgeri se intalnesc, adica i > j.

In urma aplicarii algoritmului de mai sus vectorul A este acum impartit in doi subvectori: unul contine valori mai mici decat valoarea pivot x, iar celalalt doar valori mai mari decat x. Mai precis, avem:

A[k] £ x, pentru orice k I [1..i-1]

A[k] ³ x, pentru orice k I [j+1..n]

si, de asemenea, si relatiile care rezulta din cele precedente:

A[k] = x, pentru orice k I [j+1..i-1].

Presupunem data o procedura care interschimba doua valori date, u si v:

procedure Interschimba(u,v);

var w:

begin

w:=u; u:=v; v:=w;

end

Procedura de partitionare care implementeaza algoritmul descris mai sus pe subvectorul A[Left..Right] este urmatoarea:

procedure Partition(Left, Right,iLeft,iRight: indici);

iLeft:=Left; iRight=Right;

x:=A[(Left+Right)div 2];

repeat

(2a) while A[iLeft] < x do

iLeft:= iLeft+1;

endwhile

(2b) while A[iRight] > x do

iRight:= iRight - 1;

endwhile

if iLeft <= iRight then

Interschimba(A[iLeft], A[iRight]);

iLeft:= iLeft+1;

iRight:= iRight-1;

endif

until (iLeft > iRight)

endproc

Deoarece valoarea pivot x a actionat ca un separator, putem acum sa sortam in situ in mod independent cei doi subvectori obtinuti prin partitionare, caci valorile lor nu se mai amesteca, iar concatenarea rezultatelor va duce la obtinerea vectorului A sortat. Ce metoda sa aplicam pe subvectorii obtinuti prin partitionare? Putem aplica fiecaruia procedura de partitionare, apoi inca odata subvectorilor rezultati, si asa mai departe, pana ajungem la subvectori de lungime 1 care sunt gata sortati. Aceasta este ideea algoritmului QuickSort, care foloseste partitionarea pentru a sorta.

Vom avea mai multe versiuni ale algoritmului de sortare rapida in functie de alegerea pivotului si in functie de metoda de prelucrare a subvectorilor rezultati din partitii. In ceea ce priveste alegerea valorii pivot, putem opta intre: valoarea aflata pe componenta mediana, o valoare aleasa in mod aleator de pe una din componente, sau o valoare aflata la una din extremitatile vectorului. Prezentam deocamdata algoritmul bazat pe alegerea valorii mediene ca pivot. Schimbari semnificative in procedura de partitionare apar doar la alegerea pivotului la o extremitate.

In ceea ce priveste modul de prelucrare al subvectorilor obtinuti din partitionare avem de optat intre: (a) a folosi recursia, facand cate un apel pentru fiecare subvector rezultat; (b) o versiune iterativa, in care sa mentinem intr-o stiva capetele subvectorilor ce raman de procesat; (c) combinatii intre prelucrari iterative si prelucrari cu apeluri recursive. Alegerea unui tip de prelucrare sau al altuia depinde de considerente legate de spatiu, caci stiva, fie cea gestionata explicit in program, cat si cea implicita gestionata de recursie ocupa spatiu suplimentar, o caracteristica a acestui tip de sortare ce trebuie luata in considerare.

Dam in continuare o procedura QuickSortRec care implementeaza algoritmul de sortare rapida. Ea utilizeaza procedura recursiva QSortRec care face partitionarea pe subvectorul A[Left..Right] si apoi foloseste apeluri recursive pentru prelucrarea subintervalelor rezultate. In corpul principal al procedurii QuickSortRec avem un singur apel, QSortRec(1,n).

procedure QuickSortRec(A);

procedure QSortRec(Left, Right: indici)

partition(Left,Right,i,j);

if Left < j then QSortRec(Left, j);

if i < Right then QSortRec(i, Right);

endproc

begin

QSortRec(1,n)

endproc

Dam in continuare, schematic, structura unei versiuni iterative a algoritmului de sortare rapida. Presupunem data o stiva Stack, capabila sa mentina perechi de capete de intervale, impreuna cu procedurile Push(Stack, l, r), care introduce perechea (l, r) in stiva Stack si Pop(Stack, l, r), care extrage din stiva Stack perechea de valori (l, r). Presupunem de asemenea ca procedura de partitionare este modularizata, adica, Partition(Left, Right, iLeft, iRight) face partitionarea pe subvectorul A[Left..Right] si returneaza capetele subvectorului ce raman de procesat in variabilele iLeft si iRight.

procedure QuickSortIter(A);

Push(Stack,1,n);

repeat

Pop(Stack, Left, Right);

Partition(Left, Right, iLeft, iRight);

if Left < iRight then

Push(Stack, Left, iRight);

endif

if iLeft < Right then

Push(Stack, iLeft, Right);

endif

until Stack = Æ

endproc

Sa observam ca la aceasta versiune efectuam multe operatii in plus pe stiva: introducerea in stiva la sfarsitul ciclului repeat, urmata imediat, la reluarea ciclului, de extrageri din stiva. Am putea elimina aceste operatii in plus, prin introducerea a inca unui ciclu repetitiv, care sa reia la prelucrare directa, o parte din intervale. Noua versiune iterativa, care are printre avantaje si pe acela al unei dimensiuni mai scazute a stivei, arata in felul urmator:

procedure QuickSortIter1(A);

Push(Stack, 1, n);

repeat

Pop(Stack, Left, Right);

repeat

Partition(Left, Right, i, j);

if i < Right then

Push(Stack, i, Right);

endif

Right := j;

until Left >= Right

until Stack = Æ

endproc

O alta alegere a pivotului pentru sortarea rapida.

Pana acum am ales ca pivot valoarea mediana din vectorul pe care facem partitia. Ce se intampla daca alegem o valoare situata la una dintre extremitati?

Sa presupunem ca, pentru partitionarea vectorului A[Left..Right] alegem x=A[Left]. Atunci pasul (2a) din algoritmul de partitionare (parcurgerea de la stanga la dreapta a vectorului pana la primul indice i pentru care A[i] ³ x) nu mai are sens, caci acest indice este chiar Left. Executam (2b), adica parcurgem de la dreapta la stanga vectorul pana la primul indice j pentru care A[j] £ x.

Pasul (3) devine: daca Left < j, atunci interschimba A[Left] cu A[j].

Observam ca valoarea pivot x = A[Left] a participat la interschimbare, si se afla acum plasata in extremitatea dreapta a subvectorului A[Left..j]. Reluam acum parcurgerea de tip (2a) de la stanga la dreapta. Parcurgerea de tip (2b) nu mai are sens. La sfarsit interschimbam. Observam ca valoarea pivot participa din nou la interschimbare. Procedeul continua pana cand cele doua parcurgeri se intalnesc, adica atata timp cat mai exista componente in vector care nu au fost comparate cu pivotul. La sfarsit obtinem valoarea pivot x plasata la locul ei final in vector. Fie loc indicele lui A ce va contine pe x. Avem atunci:

A[k] £ x pentru orice kI [1..loc-1]

A[k] ³ x pentru orice kI [loc+1..n]

deci subintervalele ce trebuie procesate in continuare sunt A[1..loc-1] si A[loc+1..n].

Dam mai jos noua procedura de partitionare. La parcurgeri ea va lasa pe loc valorile egale cu pivotul. Indicele loc tine minte tot timpul componenta pe care se afla valoarea pivot, iar la sfarsit o transmite procedurii apelante pentru a putea fi calculate noile capete ale subvectorilor rezultati.

procedure Partition2 (Left, Right: indice, var loc:indice)

i:= Left; j:= Right;

loc:= Left

while i < j do

while (A[loc] <= A[j]) and (j <> loc) do

j:= j-1

end while

if A[loc] > A[j] then

Interschimba(A[loc], A[j])

loc:= j

end if

while (A[i] <= A[loc]) and (i <> loc) do

i:= i +1

end while

if A[i] > A[loc] then

Interschimba (A[loc], A[i])

loc:= i

end if

end while

end

O versiune recursiva a sortarii rapide ce foloseste procedura Partition2, analoaga lui QSortRec, este urmatoarea:

Procedure QSortRec2(Left, Right)

Partition2(Left, Right, loc);

if Left < (loc-1) then QSortRec2 (Left, loc-1) endif;

if (loc+1) < Right then QSortRec2(loc+1, Right) endif

endproc

Pentru a sorta vectorul A se face apelul QSortRec2(1,n).

Complexitatea sortarii rapide.

Vom evalua complexitatea acestui algoritm in functie de timpul de rulare care depinde in mod esential de numarul de comparatii, si in functie de necesitatile de spatiu in plus.

Pentru fiecare alegere a unei valori pivot x facem la procedura de partitionare un numar de n comparatii. Numarul acesta ramane constant la fiecare pasa a algoritmului. Mai departe performanta lui depinde de numarul de sub-intervale pe care le genereaza partitionarea.

Daca fiecare partitionare injumatateste intervalul pe care se aplica (cazul cel mai favorabil), atunci vom avea un numar total de log₂n subintervale de procesat, deci numarul total de comparatii este de ordinul lui O(nlog₂n). Tot aceasta este performanta si in cazul mediu.

Putem avea si cazul cel mai nefavorabil, cand fiecare pivot ales x este maximul sau minimul din subinterval. Atunci, la fiecare partitionare se genereaza un subinterval de lungime 1 si altul de lungime n-1, deci avem un numar total de n intervale de prelucrat. Numarul total de comparatii va fi in acest caz de ordinul lui O(n²), exact ca si performanta algoritmilor directi.

O alta caracteristica a acestui algoritm este faptul ca necesita spatiu in plus pentru mentinerea subintervalelor. Atat versiunile iterative, care gestioneaza explicit stiva ce mentine intervalele, cat si cele recursive, au nevoie de acest spatiu suplimentar.

Aplicatie a procedurii de partitionare la gasirea medianei.

Mediana unui vector este acea valoare dintre componentele sale care este mai mare decat jumatate dintre componente si mai mica decat cealalta jumatate. Daca am sorta intai vectorul, atunci mediana s-ar gasi la mijlocul vectorului. Vrem sa gasim insa aceasta valoare fara a sorta intregul vector.

Problema se generalizeaza la gasirea valorii a k-a dintr-un vector, cea care este mai mare decat k-1 componente si mai mica decat n-k componente, pe scurt, cea care ar ocupa locatia A[k] in vectorul sortat, fara a sorta intregul vector.

C. A. R. Hoare a propus un algoritm care se bazeaza pe procedura de partitionare a sortarii rapide. Se aplica procedura de partitionare pe intregul vector, deci Left=1 si Right=n, cu valoarea pivot x = A[k]. Indicii i si j cu care se termina partitia au proprietatile:

i > j (cele doua parcurgeri s-au intalnit)

A[s] x, pentru orice s < i

A[s] x, pentru orice s > j .

Avem trei cazuri posibile pentru indicele k in raport cu indicii i si j:

Procedura de partitionare se reia pe subintervalele ce contin indicele k pana cand se ajunge in cazul (3). Procedura Find implementeaza algoritmul descris mai sus, presupunand ca procedura Partition (Left, Right, i, j) este complet modularizata si functioneaza ca cea descrisa la sortarea rapida.

procedure Find (A: vector, k: indice) ;

Left:=1; Right:= n;

while Left< Right do

x:= A[k];

Partition (Left, Right, i, j);

if j< k then Left:= i endif;

if k< i then Right:= j endif

endwhile

endproc

O modificare a algoritmului de mai sus se poate face in felul urmator: in loc sa asteptam ca cele doua parcurgeri sa se intalneasca (i>j), sa vedem cand una dintre parcurgeri depaseste indicele k si sa reluam partitionarea pe subintervalul corespunzator cu noua valoare pivot x=A[k]. Mai precis:

daca k i < j reluam partitionarea pe A[Left..j] cu noul pivot;

daca i< j k reluam partitionarea pe A[i..Right] cu noul pivot;

Procedura Find2 implementeaza aceasta idee.

procedure Find2 (A: vector, k: indice)

Left:= 1; Right:= n;

while Left< Right do

x:= A[k]

i:= Left; j:= Right

while (i<= k) and (k<= j) do

while A[i]< x do i:= i+1;

while x< A[j] do j:= j-1;

if i <=j then

Interschimba (A[i], A[j]);

i:= i+1; j:= j-1

endif

endwhile

if (k< i) and (k<> j) then Right:= j;

if (j< k) and (k<> i) then Left:= i;

endwhile

endproc