6

6.2. Sortarea rapid.

Vom discuta acum un algoritm de sortare bazat pe operaia de interschimbare. Am dori s mbuntim performana sortrii prin interschimbare direct, comparnd i interschimbnd ntre ele, dac e cazul, componentele aflate la distane mai mari n vector. Algoritmul care urmeaz i se datoreaz lui C. A. R. Hoare i poart numele de sortare rapid (Quick Sort).

Operaia de baz a acestui algoritm se numete operaia de partiionare a unui vector A[1..n] cu ajutorul unei valori numit pivot i este descris n continuare.

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

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

(2) (a) Se parcurge de la stnga la dreapta vectorul lsnd pe loc componentele cu proprietatea A[i] < x, pn la primul indice i pentru care A[i] ( x.(b) Se parcurge de la dreapta la stnga vectorul, lsnd pe loc componentele cu proprietatea A[j] > x, pn la primul indice j pentru care A[j] ( x.

(3) Dac i < j atunci se interschimb A[i] cu A[j] i avanseaz indicii pentru parcurgeri (i:=i+1; j:=j-1).

Se repet paii 2 i 3 pn cnd cele dou parcurgeri se ntlnesc, adic i > j.

In urma aplicrii algoritmului de mai sus vectorul A este acum mprit n doi subvectori: unul conine valori mai mici dect valoarea pivot x, iar cellalt doar valori mai mari dect x. Mai precis, avem:

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

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

i, de asemenea, i relaiile care rezult din cele precedente:

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

Presupunem dat o procedur care interschimb dou valori date, u i v:

procedure Interschimb(u,v);

var w:(acelai tip ca u i v((locaia suplimentar(begin

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

end

Procedura de partiionare care implementeaz algoritmul descris mai sus pe subvectorul A[Left..Right] este urmtoarea:

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

{iLeft=indicele curent pentru parcurgerea (2a)}

{iRight=indicele curent pentru parcurgerea (2b)}

{iniializarea indicilor cureni pentru parcurgeri}

iLeft:=Left; iRight=Right;

{algerea pivotului n poziie median}

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

{partitia}

repeat

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

iLeft:= iLeft+1;

endwhile

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

iRight:= iRight - 1;

endwhile

(3) if iLeft iRight)

endproc{Partition}

Deoarece valoarea pivot x a acionat ca un separator, putem acum s sortm in situ n mod independent cei doi subvectori obinui prin partiionare, cci valorile lor nu se mai amestec, iar concatenarea rezultatelor va duce la obinerea vectorului A sortat. Ce metod s aplicm pe subvectorii obinui prin partiionare? Putem aplica fiecruia procedura de partiionare, apoi nc odat subvectorilor rezultati, i aa mai departe, pn ajungem la subvectori de lungime 1 care sunt gata sortai. Aceasta este ideea algoritmului QuickSort, care folosete partiionarea pentru a sorta.

Vom avea mai multe versiuni ale algoritmului de sortare rapid n funcie de alegerea pivotului i n funcie de metoda de prelucrare a subvectorilor rezultai din partiii. In ceea ce privete alegerea valorii pivot, putem opta ntre: valoarea aflat pe componenta median, o valoare aleas n mod aleator de pe una din componente, sau o valoare aflat la una din extremitile vectorului. Prezentm deocamdat algoritmul bazat pe alegerea valorii mediene ca pivot. Schimbri semnificative n procedura de partiionare apar doar la alegerea pivotului la o extremitate.

In ceea ce privete modul de prelucrare al subvectorilor obinui din partiionare avem de optat ntre: (a) a folosi recursia, fcnd cte un apel pentru fiecare subvector rezultat; (b) o versiune iterativ, n care s meninem ntr-o stiv capetele subvectorilor ce ramn de procesat; (c) combinaii ntre prelucrri iterative i prelucrri cu apeluri recursive. Alegerea unui tip de prelucrare sau al altuia depinde de considerente legate de spaiu, cci stiva, fie cea gestionat explicit n program, ct i cea implicit gestionat de recursie ocup spaiu suplimentar, o caracteristic a acestui tip de sortare ce trebuie luat n considerare.

Dm n continuare o procedur QuickSortRec care implementeaz algoritmul de sortare rapid. Ea utilizeaz procedura recursiv QSortRec care face partiionarea pe subvectorul A[Left..Right] i apoi folosete 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);

{apeluri recursive pentru subvectorii rezultai}

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

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

endproc{QSortRec}

begin {corpul principal al lui QuickSortRec(A)}

QSortRec(1,n)

endproc{ QuickSortRec }

Dm in continuare, schematic, structura unei versiuni iterative a algoritmului de sortare rapid. Presupunem dat o stiv Stack, capabil s menin perechi de capete de intervale, mpreun cu procedurile Push(Stack, l, r), care introduce perechea (l, r) n stiva Stack i Pop(Stack, l, r), care extrage din stiva Stack perechea de valori (l, r). Presupunem de asemenea c procedura de partiionare este modularizat, adic, Partition(Left, Right, iLeft, iRight) face partiionarea pe subvectorul A[Left..Right] i returneaz capetele subvectorului ce rmn de procesat n variabilele iLeft i iRight.

procedure QuickSortIter(A);

Push(Stack,1,n); {iniializarea stivei}

repeat

Pop(Stack, Left, Right);

Partition(Left, Right, iLeft, iRight);

{introducem n stiv capetele intervalelor ce rmn de prelucrat}

if Left < iRight then

Push(Stack, Left, iRight);

endif

if iLeft < Right then

Push(Stack, iLeft, Right);

endif

until Stack = (endproc {QuickSortIter}

S observm c la aceast versiune efectum multe operaii n plus pe stiv: introducerea n stiv la sfritul ciclului repeat, urmat imediat, la reluarea ciclului, de extrageri din stiv. Am putea elimina aceste operaii n plus, prin introducerea a nc unui ciclu repetitiv, care s reia la prelucrare direct, o parte din intervale. Noua versiune iterativ, care are printre avantaje i pe acela al unei dimensiuni mai sczute a stivei, arat n felul urmtor:

procedure QuickSortIter1(A);

Push(Stack, 1, n);

repeat

Pop(Stack, Left, Right);

repeat

{noul ciclu repetitiv n care se aplic partiia pe A[Left..Right]}

Partition(Left, Right, i, j);

{introducem n stiva Stack intervalele din dreapta}

if i < Right then

Push(Stack, i, Right);

endif

{redefinim extrema dreapt a intervalului din stnga care este reluat la prelucrare iterativ}

Right := j;

until Left >= Right

until Stack = (endproc {QuickSortIter1}

O alt alegere a pivotului pentru sortarea rapid.

Pn acum am ales ca pivot valoarea median din vectorul pe care facem partiia. Ce se ntmpl dac alegem o valoare situat la una dintre extremiti?

S presupunem c, pentru partiionarea vectorului A[Left..Right] alegem x=A[Left]. Atunci pasul (2a) din algoritmul de partiionare (parcurgerea de la stnga la dreapta a vectorului pn la primul indice i pentru care A[i] ( x) nu mai are sens, cci acest indice este chiar Left. Executm (2b), adic parcurgem de la dreapta la stnga vectorul pn la primul indice j pentru care A[j] ( x.

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

Observm c valoarea pivot x = A[Left] a participat la interschimbare, i se afl acum plasat n extremitatea dreapt a subvectorului A[Left..j]. Relum acum parcurgerea de tip (2a) de la stnga la dreapta. Parcurgerea de tip (2b) nu mai are sens. La sfrit interschimbm. Observm c valoarea pivot particip din nou la interschimbare. Procedeul continu pn cnd cele dou parcurgeri se ntlnesc, adic atta timp ct mai exist componente n vector care nu au fost comparate cu pivotul. La sfrit obinem valoarea pivot x plasat la locul ei final n vector. Fie loc indicele lui A ce va conine pe x. Avem atunci:

A[k] ( x pentru orice k( [1..loc-1]

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

deci subintervalele ce trebuie procesate n continuare sunt A[1..loc-1] i A[loc+1..n].Dm mai jos noua procedur de partiionare. La parcurgeri ea va lsa pe loc valorile egale cu pivotul. Indicele loc ine minte tot timpul componenta pe care se afl valoarea pivot, iar la sfrit o transmite procedurii apelante pentru a putea fi calculate noile capete ale subvectorilor rezultai.

procedure Partition2 (Left, Right: indice, var loc:indice){loc este indicele pe care se va plasa n final valoarea x = A[Left]}

{iniializarea indicilor i i j pentru parcurgerile de la stnga la dreapta, respectiv de la dreapta la stnga}

i:= Left; j:= Right;

loc:= Left {iniializarea indicelui loc}

while i < j do

{parcurgerea de la dreapta la stnga, urmat de interschimbare}

while (A[loc] A[j] then

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

loc:= j

end if

{parcurgerea de la stnga la dreapta, urmat de interschimbare}

while (A[i] A[loc] then

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

loc:= i

end if

end while

end {Partition2}

O versiune recursiv a sortrii rapide ce folosete procedura Partition2, analoag lui QSortRec, este urmtoarea:

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{QSortRec2}

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

Complexitatea sortrii rapide.

Vom evalua complexitatea acestui algoritm n funcie de timpul de rulare care depinde in mod esenial de numrul de comparaii, i n funcie de necesitile de spaiu n plus.

Pentru fiecare alegere a unei valori pivot x facem la procedura de partiionare un numr de n comparaii. Numrul acesta rmne constant la fiecare pas a algoritmului. Mai departe performana lui depinde de numrul de sub-intervale pe care le genereaz partiionarea.

Dac fiecare partiionare njumtete intervalul pe care se aplic (cazul cel mai favorabil), atunci vom avea un numr total de log2n subintervale de procesat, deci numrul total de comparaii este de ordinul lui O(nlog2n). Tot aceasta este performana i n cazul mediu.

Putem avea i cazul cel mai nefavorabil, cnd fiecare pivot ales x este maximul sau minimul din subinterval. Atunci, la fiecare partiionare se genereaz un subinterval de lungime 1 i altul de lungime n-1, deci avem un numr total de n intervale de prelucrat. Numrul total de comparaii va fi n acest caz de ordinul lui O(n2), exact ca i performana algoritmilor direci.

O alt caracteristic a acestui algoritm este faptul c necesit spaiu n plus pentru meninerea subintervalelor. Att versiunile iterative, care gestioneaz explicit stiva ce menine intervalele, ct i cele recursive, au nevoie de acest spaiu suplimentar.

Aplicaie a procedurii de partiionare la gsirea medianei.

Mediana unui vector este acea valoare dintre componentele sale care este mai mare dect jumtate dintre componente i mai mic dect cealalt jumtate. Dac am sorta nti vectorul, atunci mediana s-ar gsi la mijlocul vectorului. Vrem s gsim ns aceast valoare fr a sorta ntregul vector.

Problema se generalizeaz la gsirea valorii a k-a dintr-un vector, cea care este mai mare dect k-1 componente i mai mic dect n-k componente, pe scurt, cea care ar ocupa locaia A[k] n vectorul sortat, fr a sorta ntregul vector.

C. A. R. Hoare a propus un algoritm care se bazeaz pe procedura de partiionare a sortrii rapide. Se aplic procedura de partiionare pe ntregul vector, deci Left=1 i Right=n, cu valoarea pivot x = A[k]. Indicii i i j cu care se termin partiia au proprietile:

i > j (cele dou parcurgeri s-au ntlnit)

A[s] x, pentru orice s < i

A[s] x, pentru orice s > j . Avem trei cazuri posibile pentru indicele k n raport cu indicii i i j:

Procedura de partiionare se reia pe subintervalele ce conin indicele k pn cnd se ajunge n cazul (3). Procedura Find implementeaz algoritmul descris mai sus, presupunnd c procedura Partition (Left, Right, i, j) este complet modularizat i funcioneaz ca cea descris la sortarea rapid.

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; {se continu pe subvectorul din dreapta}

if k< i then Right:= j endif {se continu pe subvectorul din stnga}

endwhile

endproc {Find}

O modificare a algoritmului de mai sus se poate face n felul urmtor: n loc s ateptm ca cele dou parcurgeri s se ntlneasc (i>j), s vedem cnd una dintre parcurgeri depete indicele k i s relum partiionarea pe subintervalul corespunztor cu noua valoare pivot x=A[k]. Mai precis:

1. dac k i < j relum partiionarea pe A[Left..j] cu noul pivot;

2. dac i< j k reluam partiionarea pe A[i..Right] cu noul pivot;

Procedura Find2 implementeaz aceast idee.

procedure Find2 (A: vector, k: indice)

Left:= 1; Right:= n;

while Left< Right do

x:= A[k]

i:= Left; j:= Right

while (i