Page 31 - MATINF Nr. 7

Complexitatea algoritmului de sortare rapid˘a (quicksort) 31

ˆ
Observat ,ia 2. In procedura de partit , ionare PIVOT(A, p, u), elementul ales pentru a deveni
pivot este cel situat init , ial la marginea din stˆanga, a p . Dac˘a init , ializarea d ← 0 se ˆınlocuies , te cu
d ← 1, atunci elementul ce va deveni pivot este cel situat init , ial la marginea din dreapta, a u .
ˆ
Exemplul 1. In figura urm˘atoare este reprezentat arborele extins de sortare asociat algoritmului
de sortare rapid˘a pentru n = 3. Observ˘am c˘a algoritmul nu cont , ine comparat , ii de chei
redundante.

1?3

≤ >
1?2 1?2

≤ > ≤ >

2?3 (2,1,3) (3,1,2) 2?3
≤ > ≤ >

(1,2,3) (1,3,2) (2,3,1) (3,2,1)

Complexitatea algoritmului

Teorema 1 (complexitatea algoritmului de sortare rapid˘a). Algoritmul de sortare rapid˘a
a unui vector cu n componente are complexitatea

 2
Θ(n ), pentru timpul de execut ,ie ˆın cazul cel mai defavorabil,

Θ(n log n), pentru timpul de execut ,ie ˆın cazul cel mai favorabil,
2
Θ(n log n), pentru timpul mediu de execut ,ie.

2
Demonstrat¸ie. Vom evalua doar num˘arul de comparat , ie de chei (comparat , ii ˆın care intervin
elemente ale vectorului), celelalte operat , ii nedep˘as , ind ordinul de cres , tere al acestora.

Fie N(n) num˘arul de comparat , ii de chei efectuate de algoritm pentru un vector cu n
componente.
ˆ
In procedura PIVOT(A, p, u) se efectueaz˘a u − p comparat , ii de chei.
Conform descrierii recursive a algoritmului, rezult˘a c˘a numerele N(n) verific˘a relat , ia de
recurent , ˘a §
0, dac˘a n ∈ {0, 1},
N(n) = (1)
N(k − 1) + N(n − k) + n − 1, dac˘a n ≥ 2,
unde k este indicele pivotului, k ∈ {1, 2, . . . , n}.

Analiz˘am ˆıntˆai cazurile extreme, ˆın raport cu diferent , a absolut˘a a dimensiunilor celor dou˘a
partit , ii rezultate dup˘a fixarea pivotului. Aceast˘a diferent , ˘a este

|(n − k) − (k − 1)| = |n + 1 − 2k|.

+
Cazul 1) Not˘am cu N (n) num˘arul de comparat , ii de chei efectuate de algoritm ˆın cazul
ˆın care la fiecare partit , ionare cele dou˘a partit , ii obt , inute sunt cˆat mai ,,neechilibrate”, adic˘a