Page 30 - MATINF Nr. 7

30 C. B˘alc˘au

– se compar˘a apoi din nou x = a u cu elementele neanalizate din stˆanga (marginea
opus˘a) a p+1 , a p+2 , . . . , iar cˆand se ajunge la un nou element a p cu a p > a u atunci din
nou se interschimb˘a x = a u cu noul a p ;
– se continu˘a acest procedeu cˆat timp subsecvent , a (a p , . . . , a u ) format˘a din x, care este
a p sau a u , s , i elemente r˘amase neanalizate verific˘a inegalitatea p < u, adic˘a are cel
put , in dou˘a elemente;
– la final se ajunge ca p = u s , i astfel x = a p = a u , deci k = p = u este pozit , ia pivotului
x s , i procedeul de partit , ionare (determinarea pozit , iei pivotului s , i astfel a celor dou˘a
partit , ii ˆın care acesta ˆımparte vectorul) este ˆıncheiat.

• Se sorteaz˘a cresc˘ator cele dou˘a partit , ii (a 1 , . . . , a k−1 ) s , i (a k+1 , . . . , a n ), prin acelas , i procedeu,
dac˘a au cel put , in dou˘a elemente. Partit , iile vide s , i cele care au un singur element sunt,
bineˆınt , eles, deja sortate.

Observat ,ia 1. Spre deosebire de algoritmul mergesort, unde ˆımp˘art , irea vectorului ˆın doi sub-
vectori (etapa ,,Divide” din strategia Divide et Impera) se realiza instantaneu prin intermediul
elementului median, la sortarea rapid˘a aceast˘a etap˘a necesit˘a rearanjarea elementelor pentru
a obt , ine pivotul a k s , i cele dou˘a partit , ii. Pe de alt˘a parte, dup˘a sortarea independent˘a a celor
dou˘a partit , ii vectorul A va fi acum sortat, spre deosebire de algoritmul mergesort, unde dup˘a
sortarea celor doi subvectori urma interclasarea lor (etapa ,,Combin˘a” din strategia Divide et
Impera, care astfel nu mai este necesar˘a la algoritmul quicksort).

Descrierea ˆın pseudocod a algoritmului are urm˘atoarea form˘a.
QUICKSORT(A, p, u) : // sortarea secvent , ei (a p , . . . , a u )
if p < u then
k ←PIVOT(A, p, u); // se determin˘ a, rearanjˆ and elementele,
// pozit , ia k a pivotului
QUICKSORT(A, p, k − 1); // sortarea partit , iei (a p , . . . , a k−1 )
QUICKSORT(A, k + 1, u); // sortarea partit , iei (a k+1 , . . . , a u )

unde procedura de partit , ionare este:
PIVOT(A, p, u) :
d ← 0; // d = pasul de deplasare spre dreapta a lui p
// 1 − d = pasul de deplasare spre stˆ anga a lui u
// d = 0 corespunde deplas˘ arii lui u (marginea din dreapta), iar
// d = 1 corespunde deplas˘ arii lui p (marginea din stˆ anga)
while p < u do
if A[p] > A[u] then
A[p] ↔ A[u]; // interschimbare
d ← 1 − d; // se comut˘ a marginea unde se face deplasarea
p ← p + d; u ← u − 1 + d; // deplasarea marginii corespunz˘ atoare

// s-a ajuns la p = u = pozit , ia pivotului
return p;

Apel:

QUICKSORT(A, 1, n) // pentru sortarea ˆ ıntregului vector A = (a 1 , . . . , a n ).