5 Quicksort (sortarea rapida)
Algoritmul de sortare quicksort, inventat de Hoare in 1962, se bazeaza de asemenea pe
principiul divide et impera. Spre deosebire de mergesort, partea nerecursiva a algoritmului este dedicata
construirii subcazurilor si nu combinarii solutiilor lor.
Ca prim pas, algoritmul alege un element pivot din tabloul care trebuie
sortat. Tabloul este apoi partitionat in doua subtablouri, alcatuite de-o parte
si de alta a acestui pivot in urmatorul mod: elementele mai mari decat pivotul
sunt mutate in dreapta pivotului, iar celelalte elemente sunt mutate in stanga
pivotului. Acest mod de partitionare este numit pivotare. In continuare,
cele doua subtablouri sunt sortate in mod independent prin apeluri recursive
ale algoritmului. Rezultatul este tabloul complet sortat; nu mai este necesara
nici o interclasare. Pentru a echilibra marimea celor doua subtablouri care
se obtin la fiecare partitionare, ar fi ideal sa alegem ca pivot elementul median.
Intuitiv, mediana unui tablou T este elementul m din T,
astfel incat numarul elementelor din T mai mici decat m este egal
cu numarul celor mai mari decat m (o definitie riguroasa a medianei unui
tablou este data in Sectiunea 7.6). Din pacate, gasirea medianei necesita mai
mult timp decat merita. De aceea, putem pur si simplu sa folosim ca pivot primul
element al tabloului. Iata cum arata acest algoritm:
procedure quicksort(T[i .. j])
{sorteaza in ordine crescatoare
tabloul T[i .. j]}
if
j-i este mic
then insert(T[i .. j])
else pivot(T[i .. j], l)
{dupa pivotare, avem:
i k <
l T[k] T[l]
l < k j
T[k] > T[l]}
quicksort(T[i .. l-1])
quicksort(T[l+1 .. j])
Mai ramane sa concepem un algoritm de
pivotare cu timp liniar, care sa parcurga tabloul T o singura data. Putem folosi urmatoarea tehnica de pivotare:
parcurgem tabloul T o singura data,
pornind insa din ambele capete. Incercati sa intelegeti cum functioneaza acest
algoritm de pivotare, in care p = T[i]
este elementul pivot:
procedure pivot(T[i .. j], l)
{permuta elementele din T[i .. j] astfel incat, in final,
elementele lui T[i .. l-1] sunt p,
T[l] = p,
iar elementele lui T[l+1 .. j] sunt > p}
p
T[i]
k
i; l j+1
repeat k
k+1 until T[k]
> p or k j
repeat l
l-1 until T[l]
p
while
k < l do
interschimba T[k]
si T[l]
repeat k k+1 until
T[k]
> p
repeat l l-1 until
T[l]
p
{pivotul este mutat in pozitia lui
finala}
interschimba T[i] si T[l]
Intuitiv, ne dam seama ca algoritmul quicksort este ineficient, daca se intampla
in mod sistematic ca subcazurile T[i .. l-1] si T[l+1 .. j] sa fie puternic neechilibrate. Ne
propunem in continuare sa analizam aceasta situatie in mod riguros.
Operatia de pivotare necesita un timp in Q(n). Fie constanta n0, astfel incat, in cazul cel mai
nefavorabil, timpul pentru a sorta
n > n0 elemente prin
quicksort sa fie
t(n) Q(n) + max{t(i)+t(n-i-1) | 0 i n-1}
Folosim metoda inductiei constructive
pentru a demonstra independent ca t O(n2) si t W(n2).
Putem considera ca exista o constanta reala
pozitiva c, astfel incat t(i) ci2+c/2 pentru 0 i n0. Prin ipoteza
inductiei specificate partial, presupunem ca t(i) ci2+c/2 pentru orice 0 i < n. Demonstram ca proprietatea este
adevarata si pentru n. Avem
t(n) dn + c + c max{i2+(n-i-1)2 | 0 i n-1}
d fiind o alta constanta. Expresia i2+(n-i-1)2 isi atinge maximul atunci cand i
este 0 sau n-1. Deci,
t(n) dn + c + c(n-1)2 = cn2+ c/2 + n(d-2c) + 3c/2
Daca luam c 2d, obtinem
t(n) cn2+c/2.
Am aratat ca, daca c este suficient de mare, atunci t(n) cn2+c/2
pentru orice n 0, adica, t O(n2).
Analog se arata ca t W(n2).
Am aratat, totodata, care este cel mai
nefavorabil caz: atunci cand, la fiecare nivel de recursivitate, procedura pivot este apelata o singura data. Daca
elementele lui T sunt distincte,
cazul cel mai nefavorabil este atunci cand initial tabloul este ordonat
crescator sau descrescator, fiecare partitionare fiind total neechilibrata.
Pentru acest cel mai nefavorabil caz, am aratat ca algoritmul quicksort necesita un timp in Q(n2).
Ce se intampla insa in cazul mediu? Intuim
faptul ca, in acest caz, subcazurile sunt suficient de echilibrate. Pentru a
demonstra aceasta proprietate, vom arata ca timpul necesar este in ordinul lui n log n, ca si in cazul cel mai favorabil.
Presupunem ca avem de sortat n elemente distincte si ca initial ele
pot sa apara cu probabilitate egala in oricare din cele n! permutari posibile. Operatia de pivotare necesita un timp
liniar. Apelarea procedurii pivot
poate pozitiona primul element cu probabilitatea 1/n in oricare din cele n
pozitii. Timpul mediu pentru quicksort
verifica relatia
| t(n) Q(n) + 1/n |
Mai precis, fie n0 si d doua constante
astfel incat pentru orice n > n0, avem
| t(n) dn + 1/n |
= dn + 2/n |
Prin analogie cu mergesort, este rezonabil sa presupunem
ca t O(n log n)
si sa aplicam tehnica inductiei constructive, cautand o constanta c,
astfel incat t(n) cn lg n.
Deoarece i lg i este o
functie nedescrescatoare, avem
src="http://www.cwu.edu/~andonie/Cartea%20de%20algoritmi/images/cap7/cap7_6.gif" v:shapes="_x0000_i1030">
pentru n0 1.
Tinand cont de aceasta margine superioara
pentru
src="http://www.cwu.edu/~andonie/Cartea%20de%20algoritmi/images/cap7/cap7_7.gif" v:shapes="_x0000_i1031">
puteti demonstra prin inductie matematica
ca t(n) cn lg n pentru orice
n > n0 1, unde
src="http://www.cwu.edu/~andonie/Cartea%20de%20algoritmi/images/cap7/cap7_8.gif" v:shapes="_x0000_i1032">
Rezulta ca timpul mediu pentru quicksort este in O(n log n). Pe langa ordinul timpului, un
rol foarte important il are constanta multiplicativa. Practic, constanta
multiplicativa pentru quicksort este
mai mica decat pentru heapsort sau mergesort. Daca pentru cazul cel mai
nefavorabil se accepta o executie ceva mai lenta, atunci, dintre tehnicile de
sortare prezentate, quicksort este
algoritmul preferabil.
Pentru a minimiza sansa unui timp de
executie in W(n2), putem alege
ca pivot mediana sirului T[i], T[(i+j) div 2], T[ j]. Pretul platit pentru aceasta
modificare este o usoara crestere a constantei multiplicative.
