Page 29 - MATINF Nr. 7

˘
ARTICOLE SI NOTE DE INFORMATICA
,

Complexitatea algoritmului de sortare rapid˘a (quicksort)

Costel B˘alc˘au 1

Algoritmul de sortare rapid˘a (quicksort), inventat de c˘atre celebrul informatician britanic
Sir Charles Antony Richard Hoare ˆın anul 1959, este considerat - ˆın urma experient , ei practice -
ca fiind cel mai performant algoritm de sortare.
ˆ
In articolul de fat , ˘a vom analiza complexitatea s , i optimalitatea acestui algoritm, utilizˆand
rezultate din teoria algoritmilor privind ordinele de complexitate s , i complexitatea algoritmilor
de sortare prezentate ˆın [2], [3], [4] s , i tehnici matematice de rezolvare a relat , iilor de recurent , ˘a.

Descrierea algoritmului

Pentru a sorta cresc˘ator un vector dat A = (a 1 , a 2 , . . . , a n ), n ≥ 1, algoritmul de sortare
rapid˘a (quicksort) utilizeaz˘a urm˘atorul procedeu specific metodei de programare Divide et
Impera:

• Se alege un element, de exemplu x = a 1 , care se duce, prin interschimb˘ari succesive, pe o
pozit , ie k, astfel ˆıncˆat dup˘a aceast˘a etap˘a s˘a avem a k = x s , i

a i ≤ a k ≤ a j , ∀ i, j cu 1 ≤ i < k < j ≤ n.
Acest element, devenit acum elementul a k , se numes , te pivot s , i are proprietatea c˘a a ajuns
pe pozit , ia sa final˘a ˆın vectorul sortat, deoarece subvectorul (a 1 , . . . , a k−1 ) al elementelor
din stˆanga sa cont , ine doar elemente mai mici sau egale cu el, iar subvectorul (a k+1 , . . . , a n )
al elementelor din dreapta sa cont , ine doar elemente mai mari sau egale cu el. Aces , ti doi
subvectori se numesc partit , iile ˆın care pivotul a k ˆımparte vectorul.
Pentru realizarea acestei etape putem proceda astfel:

– se compar˘a succesiv elementul ales, x = a 1 , cu elementele din dreapta (marginea
opus˘a) a n , a n−1 , . . . , iar cˆand se ajunge la un element a u cu a 1 > a u atunci se
interschimb˘a x = a 1 cu a u ;
– se compar˘a apoi succesiv x = a u cu elementele neanalizate din stˆanga (marginea opus˘a)
a 2 , a 3 , . . . , iar cˆand se ajunge la un element a p cu a p > a u atunci se interschimb˘a
x = a u cu a p ;
– se compar˘a apoi din nou x = a p cu elementele neanalizate din dreapta (marginea
opus˘a) a u−1 , a u−2 , . . . , iar cˆand se ajunge la un nou element a u cu a p > a u atunci se
interschimb˘a x = a p cu noul a u ;
1
Conf. univ. dr., Universitatea din Pites , ti, cbalcau@yahoo.com

29