Metoda Quicksort metoda de sortare a unui vector a=(a1,,an). Va fi aplicata tot metoda Divide et Impera. Si de aceasta data fiecare problema va fi descompusa in doua subprobleme mai mici de aceeasi natura, dar nu va mai fi necesara combinarea (asamblarea) rezultatelor rezolvarii subproblemelor.
Fie (ap,,au) secventa curenta care trebuie sortata. Vom pozitiona pe ap in secventa (ap,,au), adica printr-o permutare a elementelor secventei:
§ x=ap va trece pe o pozitie k;
§ toate elementele aflate la stanga pozitiei k vor fi mai mici decat x;
§ toate elementele aflate la dreapta pozitiei k vor fi mai mari decat x.
In acest mod ap va aparea pe pozitia sa finala, ramanand apoi sa ordonam crescator elementele aflate la stanga sa, precum si pe cele aflate la dreapta sa.
Fie poz functia cu parametrii p,u care intoarce indicele k pe care va fi pozitionat ap in cadrul secventei (ap,,au).
Atunci sortarea se realizeaza prin apelul QuickSort(1,n), unde procedura QuickSort are forma:
procedure QuickSort(p,u)
if p=u
then
else k ¬ poz(p,u); QuickSort(p,k-1); QuickSort(k+1,n)
end
Functia poz lucreaza astfel:
function poz(p,u)
i¬p; j¬u; ii¬0; jj¬-1
while i<j
if ai<aj
then
else ai<aj; (ii,jj) ¬ (-ii,-jj)
i¬i+ii; j¬j+jj (*)
poz ← i
end
Sa urmarim cum decurg calculele pentru secventa:
(a4,,a11)=(6,3,2,5,8,1,9,7)
§ se compara 6 cu a11,a10, pana cand gasim un element mai mic. Acesta este a9=1. Se interschimba 6 cu 1. Acum secventa este(1,3,2,5,8,6,9,7) si vom lucra in continuare pe subsecventa (3,2,5,8,6), schimband directia de comparare conform (*);
§ 6 va fi comparat succesiv cu 3,2, pana cand gasim un element mai mare. Acesta este a8=8. Se interschimba 6 cu 8.
Se obtine astfel (1,3,2,5,6,8,9,7), in care la stanga lui 6 apar valori mai mici, iar la dreapta lui 6 apar valori mai mari, deci l-am pozitionat pe 6pe pozitia 8, valoare intoarsa de functia poz.
Observatie. Cazul cel mai defavorabil pentru metoda Quicksort este cel in care vectorul este deja ordonat crescator: se compara a1 cu a2,,anrezultand ca el se afla pe pozitia finala, apoi se compara a2 cu a3,,an rezultand ca el se afla pe pozitia finala etc.
Trecem la calculul timpul mediu de executare al algoritmului Quicksort. Vom numara cate comparari se efectueaza (componentele vectorului nu sunt neaparat numere, ci elemente dintr-o multime ordonata oarecare). Timpul mediu este dat de formulele:
deoarece:
§ in cazul cel mai defavorabil a1 se compara cu celelalte n-1 elemente;
§ a1 poate fi pozitionat pe oricare dintre pozitiile k=1,2,,n; consideram aceste cazuri echiprobabile;
§ T(k-1) este timpul (numarul de comparari) necesar ordonarii elementelor aflate la stanga pozitiei k, iar T(n-k) este timpul necesar ordonarii elementelor aflate la dreapta pozitiei k.
nT(n) = n(n-1)+2[T(0) +T(1)+….+T(n-1)]
(n-1)T(n-1) = (n-1)(n-2)+2[T(0)+….+T(n-2)]
Scazand cele doua reltii obtinem:
nT(n)–(n-1)T(n-1) = 2(n-1)+ 2T(n-1), dci:
nT(n) = (n+1)T(n-1)+2(n-1).
Impart cu n(n+1):
Prin adunarea relatiilor de mai sus obtinem:
Cum suma ultimilor doi termeni este negativa, rezulta:
≤ 2 ln(n+1)
(am folosit o inegalitate bazata pe sumele Rieman pentru functia f(x)=ln x).
Deci T(n)=0(n.log n).
Sursa:http://www.scrigroup.com
