Lucrare de licent a [605826]

UNIVERSITATEA “ALEXANDRU IOAN CUZA”DIN IAS¸I
FACULTATEA DE MATEMATIC ˘A
ANALIZA ALGORITMILOR DE
SORTARE
Lucrare de licent ¸˘ a
Conduc˘ ator ¸ stiint ¸ific:
Lect. dr. A NA- M ARIA MOS¸NEAGU
Candidat: [anonimizat], 2019
Ias ¸i

Cuprins
Introducere 2
1 Analiza algoritmilor de sortare elementari 4
1.1 Metoda prin Select ¸ie (Select Sort) . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Metoda prin select ¸ie elementului minim . . . . . . . . . . . . . 4
1.1.2 Metoda prin select ¸ie elementului maxim . . . . . . . . . . . . 6
1.1.3 Verificarea corectitudinii . . . . . . . . . . . . . . . . . . . . . . 7
1.1.4 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Metoda prin Insert ¸ie (Insert Sort ) . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Metoda prin insert ¸ie direct ˘a . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Metoda prin insert ¸ie cu pas variabil (shellsort) . . . . . . . . . 10
1.2.3 Verificarea corectitudinii . . . . . . . . . . . . . . . . . . . . . . 13
1.2.4 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Metoda prin Interschimbare(Bubble Sort) . . . . . . . . . . . . . . . . 14
1.3.1 Verificarea corectitudinii . . . . . . . . . . . . . . . . . . . . . . 17
1.3.2 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4 Metoda Counting Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4.1 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5 Metoda Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5.1 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 23
2 Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 24
2.1 Metoda Mergesort (prin interschimbare) . . . . . . . . . . . . . . . . . 25
2.1.1 Verificarea corectitudini . . . . . . . . . . . . . . . . . . . . . . 28
2.1.2 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2 Metoda Quicksort (rapid ˘a) . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2.1 Verificarea corectitudinii . . . . . . . . . . . . . . . . . . . . . . 33
2.2.2 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 34
Bibliografie 36
1

Introducere
Aceast ˘a lucrare urm ˘ares ¸te analiza din punct de vedere teoretic, c ˆat s ¸i din punct de
vedere practic a unei categorie de algoritmi de sortare, ˆın diferite situat ¸ii.
Elementele unei liste sunt aranjate ˆıntr-o anumit ˘a ordine cu ajutorul unui algo-
ritm de sortare.
Aces ¸ti algoritmi sunt folosit ¸i pentru a sorta at ˆat liste de tip numeric, c ˆat s ¸i liste
de tip alfabetic. ˆInc˘a de la ˆınceputurile informaticii, algoritmii de sortare au atras
un num ˘ar mare de studii ˆın domeniu.
Des ¸i ideea de baz ˘a a lor este aparent simpl ˘a s ¸i oarecum familiar ˘a, complexitatea
rezolv ˘arii eficiente a sort ˘arii este mare.
Existent ¸a unor algoritmi de sortare eficient ¸i este esent ¸ial ˘a pentru utilizarea op-
tim˘a a altor algoritmi, cum ar fi cei de c ˘autare, sau cei de interclasare.
Pentru a considera un algoritm ca fiind de sortare, datele acestuia de ies ¸ire tre-
buie s ˘aˆındeplineasc ˘a dou ˘a condit ¸ii:
ordinea elementelor din datele de ies ¸ire trebuie s ˘a fie ori cresc ˘atoare, ori des-
cresc ˘atoare
datele de ies ¸ire trebuie s ˘a fie o rearanjare/permutare a celor de intrare, nu o
alterare a acestora.
ˆIn continuare, vom prezenta unele dintre cele mai cunoscute metode de sortare.
Metodele de sortare cele mai frecvent folosite se pot clasifica ˆın dou ˘a marii ca-
tegorii: metode directe s ¸i metode avansate.
IMetodele directe se bazeaz ˘a pe algoritmi de dificultate redus ˘a, us ¸or de g ˘asit
s ¸i de ˆınt ¸eles. ˆIn aceast ˘a categorie se reg ˘ases ¸te:
Analiza algoritmilor de sortare elementari care la r ˆandul lor sunt clasificat ¸i
ˆın:
(a) Metoda prin Select ¸ie
(b) Metoda prin Insert ¸ie
(c) Metoda prin Interschimbare
2

Cuprins 3
(d) Metoda Counting Sort
(e) Metoda Radix Sort
IIMetodele avansate se bazeaz ˘a pe algoritmi put ¸in mai complicat ¸i, dar care nu
necesit ˘a cunos ¸tint ¸e avansate de algoritmic ˘a. Aici se reg ˘ases ¸te:
Analiza algoritmilor de sortare bazat ¸i pe metoda Divide-et-Impera care la r ˆandul
lor cuprind:
(a) Metoda MergeSort
(b) Metoda QuickSort
Orice programator trebuie s ˘a cunoasc ˘a metodele de sortare s ¸i s ˘a aleag ˘a folosirea
unei metode, ˆın funct ¸ie de criteriul de eficient ¸ ˘a urm ˘arit. Eficient ¸a metodelor de
sortare, dup ˘a cum am precizat mai sus pentru algoritmi ˆın general, se m ˘asoar ˘a
dup ˘a tipul de execut ¸ie s ¸i memoria folosit ˘a.
Doresc s ˘a-i mult ¸umesc doamnei Lect. Dr. Ana-Maria Mo¸ sneagu pentru sprijinul
acordat ˆın vederea realiz ˘arii acestei lucr ˘ari, pentru r ˘abdarea de care a dat dovad ˘a
ca s ¸i coordonator s ¸i pentru atent ¸ia s ¸i timpul atribuite corect ˘arii.

Capitolul 1
Analiza algoritmilor de sortare
elementari
ˆIn acest capitol vom presupune o secvent ¸ ˘a finit ˘a format ˘a din nelemente a0; a1; :::; a n1,
rearanjat ˘a cresc ˘ator. Limbajul formal pentru sortarea cresc ˘atoare este de forma.
Aces ¸tia sunt:
Input: O secvent ¸ ˘a de n numere [a0; a1; :::; a n1].
Output: O permutarea a secvent ¸ei de intrare, [a00; a01: : : ; a0n1], cua00a01: : :a0n1.
Vom introduce ˆın acest capitol c ˆat ¸iva algoritmi elementari de sortare, bazat ¸i
pe compararea elementelor secvent ¸ei de sortat, ˆın general cu performant ¸e sc ˘azute
pentru tablouri de dimensiune mare :
I Metoda prin Select ¸ie
II Metoda prin Insert ¸ie
III Metoda prin Interschimbare
IV Metoda Counting Sort
V Metoda Radix Sort.
1.1 Metoda prin Select ¸ie (Select Sort)
Este o metod ˘a de sortare pentru a afla cel mai mic element sau cel mai mare element
dintr-o anumit ˘a list ˘a stabilit ˘a init ¸ial la ˆınceputul problemei dezb ˘atute. Aceast ˘a me-
tod˘a este simpl ˘a de utilizat. Fiecare element este mutat cel put ¸in o data.
1.1.1 Metoda prin select ¸ie elementului minim
Prima dat ˘a, metoda presupune determinarea celui mai mic element dintr-un ta-
blou, notat cu mdenumit s ¸i indice astfel ˆıncˆata[i]> a[m];8i= 0;1; : : : ; n1:ˆIn
4

Capitolul 1. Analiza algoritmilor de sortare elementari 5
acest caz, cel mai mic element este plasat pe prima pozit ¸ie ˆın s ¸irul sortat. Se repet ˘a
aceeas ¸i operat ¸ie p ˆan˘a cˆand ram ˆane doar un singur element sau s ¸irul este aranjat
cresc ˘ator.
Algoritmul de sortarea prin select ¸ie elementului minim scris sub form ˘a unui
cod in C++ este urm ˘atorul:
1#include <iostream>
2using namespace std;
3int sort(int a[],int n) {
4int i, min, k, j, temp;
5for (i = 1; i<n; i++)
6{
7 min = a[i];
8 k = i;
9 for (j = i + 1; j <= n; j++)
10 if (a[j]<min)
11 {
12 min = a[j];
13 k = j;
14 }
15 temp = a[i];
16 a[i] = a[k];
17 a[k] = temp;
18}
19return 1;
20}
21int main()
22{
23int a[20], n, i;
24cout << "Introduceti dimensiunea vectorului: n=";cin >> n;
25cout << "Introduceti elementele vectorului:" << endl;
26for (i = 1; i <= n; i++)
27{
28 cout << "a[" << i << "]=";
29 cin >> a[i];
30}
31sort(a, n);
32cout << "Dupa sortarea prin selectie, vectorul este: ";
33for (i = 1; i <= n; i++)

Capitolul 1. Analiza algoritmilor de sortare elementari 6
34cout << a[i] << " ";
35return 0;
36}
Vom ar ˘ata un exemplu pentru a ˆıntelege mai bine codul de mai sus. Consider ˘am
urm ˘atorul s ¸ir pe care ne propunem s ˘a-l sort ˘am cresc ˘ator:
10, 91, 2, 6, 11, 56, 23, 15, 19, 0.
Pas 1: Se determin ˘a indicele elementului minim, m = 9 s ¸i se interschimb ˘a ele-
mentele a[0] s ¸i a[9].
S ¸irul devine: 0, 91, 2, 6, 15, 56, 23, 11, 19, 10.
Pas 2: Se determin ˘a indicele elementului minim din subs ¸irul a[1..9], m = 2 s ¸i se
interschimb ˘a elementele a[1] s ¸i a[2].
S ¸irul este acum: 0, 2, 91, 6, 15, 56, 23, 11, 19, 10.
Pas 3: Se determin ˘a indicele elementului minim din subs ¸irul a[2..9], m = 3 s ¸i se
interschimb ˘a elementele a[2] s ¸i a[3].
S ¸irul este acum: 0, 2, 6, 91, 15, 56, 23, 11, 19, 10.
Pas 4: Se determin ˘a indicele elementului minim din subs ¸irul a[3..9], m = 3 s ¸i se
interschimb ˘a elementele a[3] s ¸i a[9].
S ¸irul este acum: 0, 2, 6, 10, 15, 56, 23, 11, 19, 91.
Pas 5: Se determin ˘a indicele elementului minim din subs ¸irul a[4..9], m = 3 s ¸i se
interschimb ˘a elementele a[4] s ¸i a[7].
S ¸irul este acum: 0, 2, 6, 10, 11, 56, 23, 15, 19, 91.
Pas 6: Se determin ˘a indicele elementului minim din subs ¸irul a[5..9], m = 7 s ¸i se
interschimb ˘a elementele a[5] s ¸i a[7].
S ¸irul este acum: 0, 2, 6, 10, 11, 15, 23, 56, 19, 91.
Pas 7: Se determin ˘a indicele elementului minim din subs ¸irul a[6..9], m = 8 s ¸i se
interschimb ˘a elementele a[6] s ¸i a[9].
S ¸irul este acum: 0, 2, 6, 10, 11, 15, 19, 56, 23, 91.
Pas 8: Se determin ˘a indicele elementului minim din subs ¸irul a[7..9], m = 8 s ¸i se
interschimb ˘a elementele a[7] s ¸i a[8].
S ¸irul este acum: 0, 2, 6, 10, 11, 15, 19, 23, 56, 91, care este complet sortat cresc ˘ator.
1.1.2 Metoda prin select ¸ie elementului maxim
Aceast ˘a metoda este similar ˘a cu sortarea prin select ¸ie elementului minim, doar c ˘a
acum vom determina elementul maxim al tabloului, deci a indicelui M pentru care
a[i]< a[M],8i= 0;1; :::; n1. Apoi sunt interschimbate elementele a[n-1] s ¸i a[M]
(elementul maxim este plasat pe ultima pozit ¸ie ˆın s ¸ir). Procedeul se repet ˘a pentru

Capitolul 1. Analiza algoritmilor de sortare elementari 7
subs ¸irul format din elementele a[0], a[1],…, a[n-2]. Se caut ˘a elementul cel mai mare
din acest subs ¸ir s ¸i se interschimb ˘a cu a[n-2] s ¸.a.m.d., p ˆan˘a cˆand subs ¸irul va cont ¸ine
un singur element.
1.1.3 Verificarea corectitudinii
S˘a ar˘at˘am c ˘a proprietatea
Inv1 =fa[0]a[1]: : :a[i1]s ¸ia[i1]a[j];8j=i; : : : ; n1g
este invariant ˘a pentru ciclul fordup ˘ai. Init ¸ial, i= 0, deci Inv1este satisf ˘acut ˘a la
intrare ˆın structura repetitiv ˘a(s ¸irul sortat este vid). Pentru fiecare i,ˆın ciclul for j ,
se caut ˘a minimul elementelor a[i]; a[i+1]; : : : ; a [n1], care apoi se interschimb ˘a cu
elementul a[i]. Un invariant pentru ciclul interior este deci
Inv2 =fa[m]a[k]; k= 1; : : : ; j1g;
adev ˘arat la intrarea ˆın bucl ˘a, p˘astrat adev ˘arat pe parcursul iterat ¸iei, iar la ies ¸irea
din bucl ˘a,Inv2 =fa[m]a[k]; k=i; : : : ; n1g:As ¸adar,
a[0]a[1]: : :a[i]s ¸ia[i]a[j];8j=i+ 1; : : : ; n1:
Cum ieste incrementat la sf ˆars ¸itul fiec ˘arei iterat ¸ii, reg ˘asim proprietatea invariant ˘a.
La ies ¸irea din bucla for i , invariantul conduce la postcondit ¸ie, pentru c ˘a
i=n1s ¸ia[0]a[1]: : :a[n2]s ¸ia[n2]a[n1]:
Pentru fiecare dintre cele dou ˘a cicluri for, variabila contor de iterat ¸ie este in-
crementat ˘a la fiecare iterat ¸ie, deci pot fi identificate funct ¸ii de terminare cores-
punz ˘atoare. Pentru ciclul exterior, consider ˘am funct ¸ia de terminare t(k) =n
1ik, iar pentru ciclul interior, t(k) = njk. Deci, dup ˘a un num ˘ar finit de
iterat ¸ii condit ¸iile de contiunuare nu vor mai fi ˆındeplinite, execut ¸ia algoritmului
ˆıncheindu-se. Prin urmare, algoritmul se va termina ˆıntr-un num ˘ar finit de pas ¸i, de-
monstr ˆandu-se astfel total corectitudinea algoritmului. Asem ˘anator se realizeaz ˘a s ¸i
pentru elementul maxim.
1.1.4 Analiza complexit˘ at ¸ii
Num ˘arul de comparat ¸ii nu depinde de distribut ¸ia init ¸ial ˘a a elementelor, fiind egal
cu
TC(n) = (n1) + ( n2) +


+ 1 =n(n1)
2:

Capitolul 1. Analiza algoritmilor de sortare elementari 8
ˆIn schimb, num ˘arul mut ˘arilor depinde de repartizarea init ¸ial ˘a a elementelor ˆın
secvent ¸ ˘a, ca atare vom analiza cazurile extreme. ˆIn cazul cel mai favorabil, num ˘arul
interschimb ˘arilor este 0, deci TM(n) = 0 :ˆIn cazul cel mai defavorabil, la fiecare
iterat ¸ie ise efectueaz ˘a o interschimbare, deci TM(n) = 3( n1). As ¸adar,
0TM(n)3(n1):
Cum T(n) =TC(n) +TM(n), obt ¸inem c ˘a
n(n1)
2T(n)(n1)(n+ 6)
2;
s ¸i deci T(n)2(n2), deoarece T(n)2
(n2)s ¸iT(n)2O(n2).
1.2 Metoda prin Insert ¸ie (Insert Sort )
1.2.1 Metoda prin insert ¸ie direct˘ a
ˆIn aceast ˘a sect ¸iune, vom considera o aplicat ¸ie descrec ˘atoare p ¸ entru s ¸irul a[0]; a[1]; : : : ; a [i
1]. Presupunem c ˘a o problem ˘a de sortare a s ¸irului a[0]; a[1]; : : : ; a [i2]a fost
deja rezolvat ˘a pentru a putea rezolva s ¸i pentru s ¸irul de dimensiune i1avˆand:
a[0]6a[1]6


6a[i2]. Cum ne ajut ˘a aceast ˘a mic ˘a problem ˘a s˘a afl ˘am prin-
cipala problem ˘a adic ˘a a elementului a[i1]? Evident, c ˘autarea pozit ¸iei lui a[i]se
realizeaz ˘a folosind algoritmul de c ˘autare secvent ¸ial ˘a. Astfel, a[i]se compar ˘a cu
a[i1]; a[i2]; : : : , pˆan˘a cˆand se g ˘ases ¸te un element a[j],ˆın subs ¸irul deja ordonat,
astfel ˆıncˆata[j]6a[i]. Se insereaz ˘a elementul a[i]dup ˘aa[j], nuˆınainte de a deplasa
elementele a[i1]; a[i2]; : : : ; a [j+ 1] cu o pozit ¸ie la dreapta. Rezultatul acestui
algoritm se numes ¸te sortare prin insert ¸ie direct˘ a sau mai simplu spus sortare prin
insert ¸ie .
La acest tip de sortare prin insert ¸ie se bazeaz ˘a clar pe o idee recursiv ˘a, care este
mult mai eficient ˘a fat ¸ ˘a de ideea iterativ ˘a.
Algoritmul de sortarea prin insert ¸ie direct ˘a scris sub form ˘a unui cod in C++ este
urm ˘atorul:
1#include <iostream>
2using namespace std;
3void insert(int a[], int n)
4{
5 cout << "Introduceti vectorul:" << endl;
6 for (int i = 1; i <= n; i++)
7 {

Capitolul 1. Analiza algoritmilor de sortare elementari 9
8 cout << "a[" << i << "]= ";
9 cin >> a[i];
10 int j = i;
11 while (a[j]<a[j – 1] && j>1)
12 {
13 int aux = a[j];
14 a[j] = a[j – 1];
15 a[j – 1] = aux;
16 j–;
17 }
18 }
19}
20int main()
21{
22 int a[100], n, i;
23 cout << "Introduceti dimensiunea vectorului, n= ";
24 cin >> n;
25 insert(a, n);
26 cout << "Vectorul sortat este: ";
27 for (i = 1; i <= n; i++)
28 cout << a[i] << " ";
29 return 0;
30}
31
Presupunem c ˘a vrem s ˘a sort ˘am un s ¸ir de elemente cu numere ˆıntregi, care sunt
memorate ˆıntr-un tablou. Consider ˘am urm ˘atorul s ¸ir de elemente:
20, 7, 3, 5, 6, 2, 11, 10.
Lista de elemente sortate se va construi ˆın partea din st ˆanga a tabloului init ¸ial.
Laˆınceputul problemei suntem ˆın cazul ˆın care lista noastr ˘a de elemente este vid ˘a.
Algoritmul va alege c ˆate un element din s ¸irul init ¸ial s ¸i ˆıl va insera ˆın lista de
elemente sortate. Elementele din s ¸irul init ¸ial se aleg ˆın ordinea ˆın care apar ele ˆın
s ¸ir.ˆIn exemplul nostru le vom alege ˆın ordinea 20, 7, 3, 5, etc.
Pasul 1. Vom ˆıncepe cu elementul 20. Cum lista de elemente sortate este vid ˘a,
insert ¸ia lui va fi foarte simpl ˘a. Vom obt ¸ine:
20, 7, 3, 5, 6, 2, 11, 10.
Pasul 2. Dup ˘a urmeaz ˘a elementul 7. Vrem s ˘aˆıl inser ˘amˆın lista de elemente

Capitolul 1. Analiza algoritmilor de sortare elementari 10
sortate astfel ˆıncˆat ea s ˘a r˘amˆan˘a sortat ˘a. Asta ˆınseamn ˘a c˘a trebuie s ˘aˆıl inser ˘am
ˆınaintea lui 20. Pentru a folosi ˆın mod eficient spat ¸iul de memorie ˆıl vom aduce pe
20ˆın locul lui 7 s ¸i pe urm ˘aˆıl vom pune pe 7 ˆınaintea lui 20. Vom obt ¸ine:
7, 20, 3, 5, 6, 2, 11, 10.
Pasul 3. Apoi urmeaz ˘a 3. Pe 3 ar trebui s ˘aˆıl inser ˘amˆınaintea lui 7. Din nou,
pentru a folosi eficient spat ¸iul de memorie, deplas ˘am pe 7 s ¸i pe 20 spre dreapta cu
o pozit ¸ie, s ¸i pe urm ˘a punem pe 3 ˆınaintea lor. Vom obt ¸ine:
3, 7, 20, 5, 6, 2, 11, 10.
Pasul 4. Urmeaz ˘a elementul 5. Pe 5 trebuie s ˘aˆıl inser ˘amˆıntre 3 s ¸i 7. Vom
deplasa pe 7s ¸i 20 spre dreapta cu o pozit ¸ie. ˆIn felul acesta se va elibera o pozit ¸ie
ˆıntre 3 s ¸i 7, loc unde ˆıl vom pune pe 5. Obt ¸inem:
3, 5, 7, 20, 6, 2, 11, 10.
Pasul 5. Procedeul continu ˘aˆın mod similar p ˆan˘a cˆand s ¸i ultimul element din
s ¸irul original este plasat pe pozit ¸ia corect ˘aˆın s ¸irul ordonat.
Putem vedea cum s ¸irul ordonat se construies ¸te treptat peste s ¸irul sortat, ˆın
acelas ¸i spat ¸iu de memorie cu acesta.
Ideea de principiu este c ˘a la pasul k avem deja k-1 numere sortate s ¸i vrem s ˘a
plas ˘am elementul k pe pozit ¸ia corect ˘aˆıntre aceste k-1 numere sortate. Deplas ˘am
spre dreapta toate numerele care sunt mai mari dec ˆat elementul k. Astfel se va
elibera un loc ˆın tablou, loc ˆın care vom plasa elementul k. Cum toate numerele de
la dreapta lui sunt mai mari ca el s ¸i toate numerele de la st ˆanga lui sunt mai mici
ca el, rezult ˘a c˘a avem acum k numere sortate s ¸i putem trece la pasul k+1.
1.2.2 Metoda prin insert ¸ie cu pas variabil (shellsort)
Shellsort a fost invetat ˘a,ˆın anul 1959, de c ˘atre Donald Shell.
Shellsort este o extensie simpl ˘a a sortarei prin insert ¸ie s ¸i care se execut ˘a cu o
vitez ˘a mai mare, permit ¸ ˆand schimburi de elemente care sunt foarte ˆındep ˘artate.
Ideea este de a rearanja un vector pe grupe s ¸i fiecare grup ˘a av ˆand elementele
distant ¸ate la un anumit pas h. Acest lucru poart ˘a numele de h-sortare .
Ideea principal ˘a acestui timp de sortare este aceea de a face ˆın mod repetat
sortarea prin insert ¸ie pe toate elementele la distant ¸e fixe: h1; h2; : : : ; h k= 1 s ¸i
hi+1< hi . Exist ˘a mai multe modalit ˘at ¸i de increment ¸ii, de alegerea acestora depinde
de performant ¸a algoritmului. Alegerea increment ˘arilor se dovedes ¸te a fi foarte im-
portant ˘a. Increment ¸ii pot fi ales ¸i dup ˘a o putere a lui 2 sau putem folosi un tablou
de increment ¸i cu valori descresc ˘atoare, ultima dintre acestea fiind obligatoriu 1.
Pentru aumite alegeri ale secvent ¸ei de increment ¸i se pot obt ¸ine algoritmi de com-
plexitate mai mic ˘a dec ˆat cea a algoritmului de sortare prin insert ¸ie direct ˘a. Un astfel

Capitolul 1. Analiza algoritmilor de sortare elementari 11
de s ¸ir de increment ¸i este
1;3;7;15;31;63;127;255;511; : : : ; (2k1;k1);
pentru care s-a demonstrat c ˘a,ˆın cazul cel mai defavorabil, T(n)2O(n3=2). D. E.
Knuth recomand ˘a urm ˘atorul s ¸ir de increment ¸i, deoarece este us ¸or de implementat
(are aceeas ¸i complexitate ˆın cel mai defavorabil caz):
1;4;13;40;121;364;1093;3280; : : :
As ¸adar, dup ˘a cum se observ ˘a, cel de-al i-lea increment este egal cu de 3 ori in-
crementul al (i1)lea+1. Sunt multe alte secvent ¸e de increment ¸i care pot conduce
la algoritmi de sortare mai efcient ¸i. De exemplu, Sedgewick propune secvent ¸a
1;8;23;77;281; : : : ; (4k+1+ 32k+ 1;k0;la care se adaug ˘a incrementul 1):
Algoritmul corespunz ˘ator are o performant ¸ ˘a de O(n4=3),ˆın cazul cel mai de-
favorabil. Anumite secvent ¸e de increment ¸i ar trebui evitate, av ˆand performant ¸e
slabe. Un exemplu de astfel de secvent ¸ ˘a este
1;2;4;8;16;32;64;128;256; : : :(puterile lui 2 );
deoarece elementele de pe pozit ¸iile pare nu sunt comparate cu cele de pe pozit ¸iile
impare p ˆan˘a la pasul final.
Exemplu 1. Sortat ¸i 19, 5, 2, 1.
I . shellsort cu pasul h=2: 1 s ¸i 3, 2 s ¸i 4
)19, 5, 2, 1
2, 1, 19, 5
II . shellsort cu pasul h=1:
)2, 1, 19, 5
1, 2, 19, 5
1, 2, 19 , 5
1, 2, 5, 19
Algoritmul de sortarea prin insert ¸ie cu pas variabil (shellsort) scris sub form ˘a
unui cod in C++ este urm ˘atorul:

Capitolul 1. Analiza algoritmilor de sortare elementari 12
1#include <iostream>
2using namespace std;
3int shellSort(int arr[], int n)
4{
5for (int gap = n/2; gap > 0; gap /= 2)
6{
7 for (int i = gap; i < n; i += 1)
8 {
9 int temp = arr[i];
10 int j;
11 for (j= i; j >= gap && arr[j-gap] > temp; j-=gap)
12 arr[j] = arr[j -gap];
13 arr[j] = temp;
14 }
15}
16return 0;
17}
18void printArray(int arr[], int n)
19{
20for (int i=0; i<n; i++)
21 cout << arr[i] << " ";
22}
23int main()
24{
25int arr[] = {12, 34, 54, 2, 3}, i;
26int n = sizeof(arr)/sizeof(arr[0]);
27cout << "Sirul inainte de sortare:"<<endl;
28printArray(arr, n);
29shellSort(arr, n);
30cout <<"Sirul dupa sortare:"<<endl;
31printArray(arr, n);
32return 0;
33}
34Output:
35Sirul inainte de sortare:
3612 34 54 2 3
37Sirul dupa sortare:

Capitolul 1. Analiza algoritmilor de sortare elementari 13
382 3 12 34 54
Avantajul metodei const ˘aˆın faptul c ˘a elementele sunt mutate mai repede mai aproape
de pozit ¸iile lor corecte, sortarea realiz ˆandu-se la distant ¸e mai mari.
1.2.3 Verificarea corectitudinii
S˘a ar˘at˘am c ˘a
Inv1 =fa[0]a[1]: : :a[i1]g
este inavariant pentru ciclul fordup ˘ai(elementele s ¸irului sortat, a[0]; : : : ; a [i1],
sunt elementele s ¸irului original de la 0lai1, permutate). Init ¸ial, i= 1, deci
precondit ¸ia implic ˘a faptul c ˘a s ¸irul format dintr-un singur element poate fi consi-
derat sortat cresc ˘ator. S ˘a ar˘at˘am c ˘a proprietatea r ˘amˆane adev ˘arat˘a prin execut ¸ia
prelucr ˘arilor din ciclul for.
Fie proprietatea
Inv2 =fa[0]a[1]: : :a[j]s ¸iauxa[j+ 1] = a[j+ 2]: : :a[i]g:
Vom ar ˘ata c ˘a aceasta este o proprietate invariant ˘a pentru structura repetitiv ˘awhile .
La intarea ˆın ciclu, j=i1; aux =a[i] =a[j+1], iar s ¸irul a[0]a[1]: : :a[i1]
este deja ordonat, deci proprietatea este adev ˘arat˘a la intrarea ˆın ciclu. Apoi, daca
aux < a [j], din a[j+ 1] = a[j]rezult ˘a c˘aaux < a [j] =a[j+ 1]: : :a[i]. Dup ˘a
execut ¸ie prelucr ˘ariij=j1; a[0]a[1]: : :a[j]s ¸iaux < a [j+ 1] = a[j+ 2]
: : :a[i]. Deci, Inv2este un invariant pentru ciclul while .
La sf ˆars ¸itul buclei while este adev ˘arat˘a una dintre relat ¸iile:
a[0]: : :a[j]auxa[j+ 1] = a[j+ 2]: : :a[i];
dac˘a ciclul s-a ˆıncheiat deoarece auxa[j]sau
auxa[0] = a[1]: : :a[i];
dac˘a ciclul s-a ˆıncheiat deoarece j=1. Dar,dup ˘a atribuirea a[j+ 1] = aux; a [0]
: : :a[j]a[j+ 1]a[j+ 2]: : :a[i], iar prin incrementarea contorului i,
reg˘asim proprietatea invariant ˘a. La ies ¸irea din bucla for; i =n, invariantul implic ˘a
postcondit ¸ia.
Justificarea termin ˘ariiˆın timp finit a algoritmului este aceeas ¸i ca ˆın cazul algorit-
mului de sortare prin select ¸ia minimului, consider ˆand funct ¸ia de terminare pentru

Capitolul 1. Analiza algoritmilor de sortare elementari 14
cuclul exterior t(k) =nik, iar pentru cazul interior
t(k) =8
<
:jk+ 1;dac˘aaux < a [jk]
0;dac˘aauxa[jk]
1.2.4 Analiza complexit˘ at ¸ii
Atˆat num ˘arul comparat ¸iilor, c ˆat s ¸i num ˘arul mut ˘arilor depinde de distribut ¸ia init ¸ial ˘a
a elementelor ˆın secvent ¸ ˘a.ˆIn cazul cel mai favorabil, pentru fiecare i= 1;2; : : : ; n
1, are loc o singur ˘a comparat ¸ie s ¸i dou ˘a mut ˘ari(aux=a[i]; a[j+ 1] = a[i]). Lu ˆand
ˆın calcul s ¸i mut ˘arile s ¸i comparat ¸ile, se obt ¸ine o margine inferioar ˘a pentru timpul de
execut ¸ie,
3(n1)T(n):
ˆIn cazul cel mai defavorabil, pentru fiecare i= 1;2; : : : ; n1, au loc icomparat ¸ii s ¸i
i+ 2mut ˘ari. Obt ¸inem o margine superioar ˘aa timpului de execut ¸ie,
T(n)n1X
i=1(2i+ 2) = ( n1)(n+ 2):
Putem scrie
3(n1)T(n)(n1)(n+ 2):
DeciT(n)2
(n)s ¸iT(n)2O(n2):
1.3 Metoda prin Interschimbare(Bubble Sort)
Este una dintre cele mai simple metode de sortare, ˆıns˘a nu este cea mai eficient ˘a.
Se consider ˘a dat ˘a o secvent ¸ ˘aa1; a2; : : : ; a nde n elemente, pe care este definit ˘a
o relat ¸ie de ordine liniar ˘a<. Init ¸ial ordinea elementelor ˆın cadrul acestei secvent ¸e
este aleatoare. Interschimb ˘arile au loc p ˆan˘a cˆand elementele vectorului sunt com-
plet ordonate. Aceast ˘a variant ˘a de sortare se mai numes ¸te s ¸i metoda bulelor sau
BubbleSort .
Scopul acestui tip de sortare const ˘aˆın compararea elementelor a[i]s ¸ia[i+ 1];
dac˘aa[i]< a[i+ 1] , atunci se trece la urm ˘atoarea comparare, adic ˘aa[i+ 1] cu
a[i+2], dac ˘a nu, se interschimb ˘aa[i]cua[i+1] s ¸i apoi se compar ˘aa[i+1] cua[i+2].
Dup ˘a prima parcurgere a vectorului, pe ultima pozit ¸ie va fi cu sigurant ¸ ˘a elementul
avˆand valoarea cea mai mare, dup ˘a a doua parcurgere, pe penultima pozit ¸ie va
ajunge urm ˘atorul element ca valoare, etc. O singur ˘a parcurgere a vectorului nu
este suficient ˘a, ci trebuie continuat p ˆan˘a cˆand nu se mai efectueaz ˘a interschimb ˘ari.

Capitolul 1. Analiza algoritmilor de sortare elementari 15
Algoritmul de sortarea prin Interschimbare(Bubble Sort) scris sub form ˘a unui
cod in C++ este urm ˘atorul:
1#include <iostream>
2using namespace std;
3int bubble(int a[], int n)
4{
5 int j, i;
6 int sortat;
7 do {
8 sortat = 1;
9 for (i = 1; i <= n – 1; i++) {
10 if (a[i] > a[i + 1]) {
11 int aux = a[i];
12 a[i] = a[i + 1];
13 a[i + 1] = aux;
14 sortat = 0;
15 }
16 }
17 } while (sortat == 0);
18 return 1;
19}
20int main() {
21 int n,a[100],i;
22 cout << "Introduceti dimensiunea vectorului: n="; cin >>
n;
23 cout << "Introduceti elementele vectorului:" << endl;
24 for (i = 1; i <= n; i++)
25 {
26 cout << "a[" << i << "]=";
27 cin >> a[i];
28 }
29 bubble(a, n);
30 cout << "Vectorul sortat este:";
31 for (i = 1; i <= n; i++)
32 cout << a[i] << " ";
33 return 0;
34}
35

Capitolul 1. Analiza algoritmilor de sortare elementari 16
Exemplu. S˘a consider ˘am c ˘a s ¸irul de sortat este:
79, 40, 65, 81, 25, 38, 13.
Pasul 1:
79$4065 81 25 38 13 (prin ” $” am indicat o interschimbare)
4079$6581 25 38 13
40 65 79 81$2538 13
40 65 79 25 81$3813
40 65 79 25 38 81$13
40 65 79 25 38 13 81
La finalul primului pas, cel mai mare element din s ¸ir se afl ˘a pe ultima pozit ¸ie
a s ¸irului. Deci, acesta nu va mai face parte din subsecvent ¸a ce va fi parcurs ˘aˆın
continuare.
Pasul 2:
40 65 79$25 38 13
40 65 25 79$38 13
40 65 25 38 79$13
40 65 25 38 13 79
La finalul acestui pas, cel mai mare element al s ¸irului este pozit ¸ionat acum pe
penultima pozit ¸ie a s ¸irului init ¸ial. Prin urmare, acesta nu mai poate fi parcurs ˆın
contiunuare.
Pasul 3:
40 65$25 38 13
40 25 65$38 13
40 25 38 65$13 40 25 38 13 65
La finalul celui de-al treilea pas, num ˘arul 65se afl ˘a pe pozit ¸ia corect ˘aˆın s ¸irul
sortat.
Pasul 4:
40$25 38 13
25 40$38 13
25 38 40$13
25 38 13 40
Num ˘arul 40se afl ˘aˆın pozit ¸ia corect ˘aˆın s ¸irul sortat.
Pasul 5:
25 38$13
25 13 38

Capitolul 1. Analiza algoritmilor de sortare elementari 17
Elementul 38este pe pozit ¸ia sa final ˘aˆın s ¸irul sortat.
Pasul 6:
25$13 13 25
ˆIn acest moment, am terminat procesul de sortare deoarece s ¸irul s-a aranjat ˆın
ˆıntregime: 13, 25, 38, 40, 65, 79, 81.
1.3.1 Verificarea corectitudinii
Consider ˘am proprietatea
Inv1 =fa[j]a[k]; k= 0; : : : ; jg:
S˘a ar˘at˘am c ˘a aceast ˘a proprietate este invariant ˘a pentru ciclul interior (forj). La in-
trarea ˆın ciclu, (j= 0) , proprietatea este adev ˘arat˘a, pentru c ˘aa[0]a[0]. Presupu-
nem c ˘a proprietatea este adev ˘arat˘a laˆınceputul iterat ¸iei. Dac ˘aa[i]> a[j+1], atunci
se realizeaz ˘a interschimbarea elementelor s ¸i acestea vor fi ˆın ordinea a[j]< a[j+1],
iar dac ˘aa[j]a[j+ 1] , nu se efectueaz ˘a interschimb ˘ari, dar proprietatea este
adev ˘arat˘a. As ¸adar, proprietatea Inv1r˘amˆane adev ˘arat˘a la sf ˆars ¸itul iterat ¸iei. Dup ˘a
incrementarea variabilei jreg˘asim proprietatea Inv1. Ceea ce se realizeaz ˘aˆın ci-
clul interior este plasarea celui mai mare element din secvent ¸a a[0]; a[1]; : : : ; a [i]pe
pozit ¸ia i.
Fie proprietatea
Inv2 =fa[i+ 1]: : :a[n1];cua[i+ 1]a[j]; j= 0; : : : ; ig:
Proprietatea este invariant ˘a pentru ciclul exterior (fori): la intrarea ˆın ciclu, i=
n1, deci proprietatea este adev ˘arat˘a (s ¸ir vid), apoi r ˘amˆane adev ˘arat˘aˆın bucl ˘a
conform celor demonstrate anterior, iar la ies ¸irea din bucl ˘a,i= 0, deci proprietatea
devine Inv2 =fa[1]: : :a[n1];cua[1]a[0]g, ceea ce implic ˘a postcondit ¸ia.
Pentru a demonstra c ˘a ambele cicluri sunt finite, consider ˘am funct ¸ia de termi-
nare pentru ciclul exterior, t(k) =ik, iar pentru ciclul interior, t(k) =ikjk.
1.3.2 Analiza complexit˘ at ¸ii
Num ˘arul de comparat ¸ii nu depinde de propriet ˘at ¸ile datelor de intrare, acesta fiind
TC(n) =n1X
i=1i1X
j=01 =n1X
i=1i=n(n1)
2:
Num ˘arul de interschimb ˘ari depinde de repartizarea init ¸ial ˘a a elementelor ˆın s ¸ir,
deci vom analiza cazurile extreme. ˆIn cazul cel mai favorabil num ˘arul de mut ˘ari

Capitolul 1. Analiza algoritmilor de sortare elementari 18
ale elementelor ˆın vederea sort ˘arii este TM(n) = 0 , iar ˆın cazul cel mai defavorabil
se obt ¸ine TM(n) =3n(n1)
2:As ¸adar, 0TM(n)3n(n1)
2:Cum T(n) =TC(n) +
TM(n))n(n1)
2T(n)2n(n1);deciT(n)2(n2).
Algoritmul poate fi ˆımbun ˘at˘at ¸it, implic ˆand o variabil ˘a boolean ˘a care s ˘a indice
dac˘a la iterat ¸ia precedent ˘a au existat interschimb ˘ari. Scopul este de a reduce num ˘arul
de comparat ¸ii.
ˆIn acest caz, num ˘arul de comparat ¸ii ˆın cazul cel mai favorabil este TC(n) =
n1, iar ˆın cazul cel mai defavorabil este la fel ca ˆın cazul general. ˆIn ceea ce
prives ¸te num ˘aarul de mut ˘ari, se obt ¸ine aceeas ¸i estimare ca ˆın cazul general. Deci,
n1T(n)2n(n1). Prin urmare, avem c ˘aT(n)2
(n)s ¸iT(n)2O(n2).
1.4 Metoda Counting Sort
Aceast ˘a metod ˘a presupune c ˘a fiecare dintre cele nelemente ale datelor intrate se
afl˘a un num ˘arˆıntreg ˆıntre 1 s ¸i m, pentru un num ˘arˆıntreg m luat oarecare. Atunci
cˆandm=O(n), sortarea se execut ˘aˆın timpul O(n).
Ideea principal ˘aˆın sortarea prin num ˘arare este determinarea num ˘arului de ele-
mente mai mici dec ˆaty, pentru fiecare element ydin datele de intrare. Aceast ˘a
informat ¸ie poate fi utilizat ˘a pentru a pozit ¸iona elementul ydirect ˆın pozit ¸ia sa din
tabloul de ies ¸ire.
Presupunem c ˘a datele noastre de intrare formeaz ˘a un tablou a[1: : : n], s ¸i deci
lungime [a] =n. Sunt necesare alte dou ˘a tablouri suplimentare, tabloul b[1: : : n],
care cuprinde datele de ies ¸ire sortate, s ¸i tabloul c[1: : : m ], pentru stocarea tempo-
rar˘aˆın timpul lucrului. Avem urm ˘atorul algoritm:
O proprietate important ˘a a sort ˘arii prin num ˘arare este stabilitatea : numerele cu
aceeas ¸i valoare apar ˆın tabloul de ies ¸ire ˆın aceeas ¸i ordine ˆın care se g ˘asesc ˆın tabloul
de intrare. Bine ˆınt ¸eles, stabilitatea este important ˘a numai c ˆand datele ˆınvecinate
sunt deplasate ˆımpreun ˘a cu elementul ˆın curs de sortare.
Algoritmul de sortarea Counting Sort scris sub form ˘a unui cod in C++ este
urm ˘atorul:
1#include<iostream>
2using namespace std;
3int m = 0;
4/*Metoda de sortare */
5void Counting_Sort(int a[], int b[], int n)
6{
7 int c[100];
8 for (int i = 0; i<m + 1; i++)

Capitolul 1. Analiza algoritmilor de sortare elementari 19
9 {
10 c[i] = 0;
11 }
12 for (int j = 1; j <= n; j++)
13 {
14 c[a[j]]++;
15 }
16 for (int i = 1; i <= m; i++)
17 {
18 c[i] += c[i – 1];
19 }
20 for (int j = n; j >= 1; j–)
21 {
22 b[c[a[j]]] = a[j];
23 c[a[j]] = c[a[j]] – 1;
24 }
25}
26int main()
27{
28 int n;
29 cout << "Introduceti dimensiunea vectorului: ";
30 cin >> n;
31 int a[100], b[100];
32 cout << "Introduceti vectorul:"<<endl;
33 for (int i = 1; i <= n; i++)
34 {
35 cout << "a[" << i << "]=";
36 cin >> a[i];
37 if (a[i]>m)
38 {
39 m = a[i];
40 }
41 }
42 Counting_Sort(a, b, n);
43 cout << "Vectorul sortat este:";
44 for (int i = 1; i <= n; i++)
45 {
46 cout << b[i] << " ";

Capitolul 1. Analiza algoritmilor de sortare elementari 20
47 }
48 cout << endl;
49 return 0;
50}
51
52
1.4.1 Analiza complexit˘ at ¸ii
Sortarea prin num ˘arare are timpul total de execut ¸ie egal cu O(k+n),ˆıns˘aˆın practic ˘a
se utilizeaz ˘a atunci c ˆand avem k=O(n), caz ˆın care timpul necesar este O(n).
Acest tip de sortare are un timp mai bun dec ˆat marginea inferioar ˘a care este
egal ˘a cu
(nlgn), pentru c ˘a nu este o sortare bazat ˘a pe comparat ¸ii. De fapt, ˆın
cod nu apar comparat ¸ii ˆıntre elementele de intrare. Dar sortarea prin num ˘arare
foloses ¸te valorile elementelui ca un indice ˆıntr-un tablou. Deci, marginea inferioar ˘a

(nlgn)nu se aplic ˘a atunci c ˆand nu mai urm ˘arim modelul sort ˘arii prin comparat ¸ii.
1.5 Metoda Radix Sort
Este un algoritm de sortare ce pune accent pe cifrele individuale ale elementelor
sortate. Aceste elemente pot fi reprezentate prin orice alt caracter ce se poate scrie
prin numere ˆıntregi. Marea majoritate a calculatoarelor digitale sunt reprezentate
pe date ˆın memorie sub form ˘a de numere binare, pentru c ˘a este cea mai convena-
bil˘a reprezentare. Avem 2 tipuri de astfel de sortare: LSD(least significant digit) s ¸i
MSD(most significant digit). Cel din urm ˘a proceseaz ˘a reprezent ˘arile de la cea mai
semnficativ ˘a spre cea mai put ¸in semnificativ ˘a, iar LSD proceseaz ˘a invers.
O variant ˘a mai simpl ˘a a Radix sortului este aceea care foloses ¸te 10 cozi, adic ˘a
foloses ¸te c ˆate una pentru fiecare cifr ˘a de la 0 la 9. Fiecare coad ˘a va ret ¸ine la fiecare
pas acele numere care au cifra potrivit ˘a rangului curent(*). Elementele se scot din
cozi ˆın oridinea cresc ˘atoare a indicelui cozii dup ˘a ce a avut loc ˆımp˘art ¸irea (*). Dup ˘a
se pun ˆıntr-un vector, care acum devine noua secvent ¸ ˘a de sortat.
Algoritmul de sortarea Radix Sort scris sub form ˘a unui cod in C++ este urm ˘atorul:
1#include <iostream>
2using namespace std;
3int getMax(int a[], int n)
4{

Capitolul 1. Analiza algoritmilor de sortare elementari 21
5 int max = a[0];
6 for (int i = 1; i < n; i++)
7 if (a[i] > max)
8 max = a[i];
9 return max;
10}
11void countSort(int a[], int n, int exp)
12{
13 int output[100], i, count[10] = { 0 };
14 for (i = 0; i < n; i++)
15 count[(a[i] / exp) % 10]++;
16 for (i = 1; i < 10; i++)
17 count[i] += count[i – 1];
18 for (i = n – 1; i >= 0; i–)
19 {
20 output[count[(a[i] / exp) % 10] – 1] = a[i];
21 count[(a[i] / exp) % 10]–;
22 }
23 for (i = 0; i < n; i++)
24 a[i] = output[i];
25}
26void radixsort(int arr[], int n)
27{
28 int exp, m;
29 m = getMax(arr, n);
30 for (exp = 1; m / exp > 0; exp *= 10)
31 countSort(arr, n, exp);
32}
33int main()
34{
35 int n, i;
36 cout << "Introduceti dimensiunea vectorului: ";
37 cin >> n;
38 int a[100];
39 for (i = 0; i < n; i++)
40 {
41 cout << "Introduceti elementele vectorului " << i + 1
<< ": ";

Capitolul 1. Analiza algoritmilor de sortare elementari 22
42 cin >> a[i];
43 }
44 radixsort(a, n);
45 cout << "Vectorul sortat este: ";
46 for (i = 0; i < n; i++)
47 cout << a[i]<<" ";
48 return 0;
49}
50
De exemplu:
Secvent ¸a init ¸ial ˘a: 180, 55, 65, 80, 2, 34, 902, 56
Avem urm ˘atoarele cozi ˆın prima iterat ¸ie:
0: 180, 080
1: nimic
2: 002, 902
3: nimic
4: 034
5: 055, 065
6: 056
7-9: nimic
Noua secvent ¸ ˘a de sortat: 180, 080, 002, 902, 034, 055, 065, 056
Sort ˘am acum dup ˘a a doua cifr ˘a. Avem:
0: 002, 902
1: nimic
2: nimic
3: 034
4: nimic
5: 055, 056
6: 065
7: nimic
8: 180, 080
9: nimic
Noua secvent ¸ ˘a: 002, 902, 034, 055, 056, 065, 180, 080
Acum sort ˘am dup ˘a a treia cifr ˘a s ¸i avem:
0: 002, 034, 055, 056, 065, 080
1: 180

Capitolul 1. Analiza algoritmilor de sortare elementari 23
2-8: nimic
9: 902
Noua secvent ¸ ˘a: 002, 034, 055, 056, 065, 080, 180, 902 care este sortat ˘a.
1.5.1 Analiza complexit˘ at ¸ii
Pentru a fi eficient Radix sortul trebuie s ˘a folosim structuri de date potrivite. Ele-
mentele de sortat ar fi preferabil s ˘a fie ˆıntr-o list ˘aˆınl˘ant ¸uit ˘aˆın loc de o simpl ˘a ta-
bel˘a, deoarece ˆıntr-o list ˘aˆınl˘ant ¸uit ˘a nu mai trebuie s ˘a copiem ˆınregistrarea, ci doar
s˘a mut ˘amˆınregistrarea dintr-o list ˘aˆın alta. Pentru a avea o eficient ¸ ˘a cˆat mai bun ˘a
avem nevoie de pointeri la sf ˆars ¸itul fiec ˘arei liste.
Timpul de execut ¸ie al Radix sortului este O(n). Acest tip de algoritm nu necesit ˘a
foarte mult ˘a memorie.

Capitolul 2
Analiza algoritmi de sortare bazat ¸i
pe medota Divide-et-Impera
Divide-et-Impera este o una dintre cele mai cunoscute metode de proiectare a al-
goritmilor. Aceast ˘a strategie de proiectare presupune ˆımpart ¸irea programul ˆın cel
put ¸in dou ˘a subprograme independente, ˆıns˘a acestea sunt asem ˘an˘atoare cu pro-
blema init ¸ial ˘a. Aceste mici probleme, de regul ˘a sunt rezolvate ˆın mod recursiv s ¸i
dup ˘a se regrupeaz ˘a rezultatele pentru a crea o solut ¸ie problemei init ¸iale.
Pentru a rezolva o astfel de problem ˘a trebuie parcurs ¸i trei pas ¸i la nivel de recur-
sivitate:
ˆımpart ¸irea problemei init ¸iale ˆın mai multe subprobleme, numit divide
rezolvarea subproblemelor ˆın mod recursiv, dar dac ˘a acestea au dimensiuni
foarte mici, atunci cel mai bine e s ˘a le rezolv ˘amˆın mod uzual. Acest pas
poart ˘a denumirea de impera(conquer)
gruparea rezultatelor astfel ˆıncˆat s˘a obt ¸iem solut ¸ia la problema init ¸ial ˘a.
Exemplele specifice acestei metode sunt algoritmii de parcurgere a arborilor bi-
nari s ¸i algoritmul de c ˘autare binar ˘aˆın mult ¸imi total ordonate. Deoarece descrierea
strategiei este bazat ˘a pe recursivitate , trebuie pus accet pe o prelungire de tipul
problem ˘a7!subproblem ˘a unde dimensiunea devine o variabil ˘a liber ˘a.
Revenim la problema noastr ˘a, adic ˘a aceea a sort ˘ariiˆın ordinea cresc ˘atoare a unei
secvent ¸e de nnumere reale. Ne propunem s ˘a folosim tehnica diviz ˘arii pentru a
elabora alt ¸i algoritmi de sortare. Acet ¸ia sunt: sortarea prin interclasare(Mergesort)
s ¸i sortarea rapid ˘a(Quicksort).
Vom enunt ¸a un rezultat important pentru analiza eficient ¸ei algoritmilor bazat ¸i
pe tehnica diviz˘ arii , numit Teorema master . Presupunem c ˘a o problem ˘a de dimen-
siune neste descompus ˘aˆınbsubprobleme de aceeas ¸i dimensiune, egal ˘a cu n/b. De
24

Capitolul 2. Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 25
asemenea, presupunem c ˘a doar aprobleme dintre acestea necesit ˘a s˘a fie rezolvate,
ab(as ¸ibsunt constante, a1,b >1). Consider ˘am c ˘a divizarea problemei init ¸iale
ˆınbsubprobleme de dimensiune n/bs ¸i compunerea solut ¸iilor acestor subprobleme
auˆımpreun ˘a costul f(n), iar costul rezolv ˘arii cazului elementar este o constant ˘aT0.
Astfel, timpul de execut ¸ie al algoritmului general satisface recurent ¸a
T(n) =8
<
:T0;dac˘ann0
aT(n=b) +f(n);dac˘an > n 0:
ˆIn mod evident, ordinul de cres ¸tere al lui T(n)depinde de ordinul de cres ¸tere a lui
f(n)s ¸i de valorile constatelor as ¸ib.
Teorema 1. (Teorema master) Dac˘ a f(n)2(nd); d0, atunci
T(n) =8
>>><
>>>:(nd);dac˘ aa < bd
(ndlogn);dac˘ aa=bd
(nlogba);dac˘ aa > bd:
2.1 Metoda Mergesort (prin interschimbare)
Mergesort este un exemplu bun pentru aplicarea tehnicii Divide-et- Impera. Fie un
s ¸ir pe care ˆıl imp ˘art ¸im ˆın dou ˘a subs ¸iruri de lungimi aproximativ egale. Cele dou ˘a
s ¸iruri sunt ordonate recursiv folosind aceleas ¸i tehnici de sortare, adic ˘amergesort .
Apoi rezultatele sunt combinate (interclasate), obt ¸in ˆand astfel tabloul init ¸ial sortat.
Prin interclasare se ˆıntelege parcurgerea celor dou ˘a secvent ¸e ordonate s ¸i extragerea
de elemente din acestea astfel ˆınˆat s˘a obt ¸inem s ¸irul init ¸ial sortat. Aceste subsecvent ¸e
sunt parcurse simultan cu dou ˘a contoare s ¸i se compar ˘a elementele curente. Cel mai
mic element dintre cele dou ˘a este plasat ˆın s ¸irul final, iar contorul utlizat pentru
parcurgerea subs ¸irului din care a fost preluat elementul este incrementat. Procesul
continu ˘a pˆan˘a cˆand una dintre secvent ¸e a fost preluat ˆınˆıntregime s ¸i elementele
care r ˘amˆanˆın cealalt ˘a secvent ¸ ˘a sunt plasate direct ˆın s ¸irul final.
Algoritmul de sortarea Mergesort (prin interschimbare) scris sub form ˘a unui
cod in C++ este urm ˘atorul:
1#include <iostream>
2using namespace std;
3
4void Merge(int a[], int l, int h, int m)
5{
6int i, j, k, temp[50];

Capitolul 2. Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 26
7i = l;
8k = 0;
9j = m + 1;
10while (i <= m && j <= h)
11{
12 if (a[i] < a[j])
13 {
14 temp[k] = a[i];
15 k++;
16 i++;
17 }
18 else
19 {
20 temp[k] = a[j];
21 k++;
22 j++;
23 }
24}
25while (i <= m)
26{
27 temp[k] = a[i];
28 k++;
29 i++;
30}
31while (j <= h)
32{
33 temp[k] = a[j];
34 k++;
35 j++;
36}
37for (i = l; i <= h; i++)
38{
39 a[i] = temp[i – l];
40}
41}
42void MergeSort(int a[], int l, int h)
43{
44int m;

Capitolul 2. Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 27
45if (l< h)
46{
47 m = (l + h) / 2;
48 MergeSort(a, l, m);
49 MergeSort(a, m + 1, h);
50 Merge(a, l, h, m);
51}
52}
53
54int main()
55{
56int n, i;
57cout << "Introduceti dimensiunea vectorul pe care doriti
sa-l sortati: ";
58cin >> n;
59int a[100];
60for (i = 0; i < n; i++)
61{
62 cout << "Introduceti elementele vectorului " << i + 1 <<
": ";
63 cin >> a[i];
64}
65MergeSort(a, 0, n – 1);
66cout << "Vectorul sortat este: ";
67for (i = 0; i < n; i++)
68 cout<< a[i]<<" ";
69return 0;
70}
71
Un exemplu clar care ˆındeplinet ¸e cont ¸iile acestui algoritm:

Capitolul 2. Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 28
Figura 1: Realizarea algoritmului de sortare prin interclasare(din [6])
2.1.1 Verificarea corectitudini
Pornim de la stabilirea precondit ¸iilor s ¸i a postcondit ¸iilor: Pin=fa[stang : : : mijloc ]
este cresc˘ ator ¸ si a[mijloc +1: : : drept ]este cresc˘ atorg, iarPout=fa[stang : : : drept ]este cresc ˘atorg.
S˘a presupunem c ˘a, la interat ¸ia k, indicii ˆın cele dou ˘a p˘art ¸i ale vectorului sunt asunt
i, respectiv j. Astfel, vom considera proprietatea invariant ˘aI=ftemp [k]a[l]; l=
i; : : : ; mijloc s ¸itemp [k]a[l]; lj; : : : ; dreptgpentru prima strunctur ˘awhile . Ast-
fel spus, elementul pe care tocmai l-am copiat ˆıntemo [k]este cel mai mic dintre
elementele r ˘amase netransferate din cele dou ˘a p˘art ¸i ale vectorului a. Acum toate
elementele r ˘amase ˆınavor fi transferate ˆıntemp [k+ 1]; : : : ; temp [dreptstang ],
pentru c ˘a vectorul temp este completat la st ˆanga. Deci, la ˆıncheierea algoritmului
merge , va fi verificat ˘a condit ¸ia temp [k]temp [l];8k < l , ceea se ˆınseamn ˘a c˘a, dup ˘a
copierea elementelor din temp ˆına, tabloul va fi corect sortat de la stang ladrept .
Pentru a demonstra c ˘a invariantul este corect, ne reamintim c ˘a, atunci c ˆand
este apelat algoritmul de interclasare merge , cele dou ˘a subsecvent ¸e a lui a, de la
stang lamijloc s ¸i de la mijloc ladrept , sunt deja sortate. Deci, a[i]a[l]; l=i+
1; : : : ; mijloc s ¸ia[j]a[l]; l=j+ 1; : : : ; drept . As ¸adar, a[i]s ¸ia[j]sunt cele mai
mici elemente r ˘amase netransferate. Dac ˘aa[i]a[j], atunci temp [k]va primi va-
loarea a[i]s ¸i deci va fi adev ˘arat˘a relat ¸ia a[i]a[l]; l=j; : : : ; drept . Asem ˘anator

Capitolul 2. Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 29
este s ¸i pentru cel ˘alt caz. Aceast ˘a metod ˘a este stabil ˘a, dar are necesit ˘a un spat ¸iu de
memorie suplimentar ˆın etapa de interclasare.
Apelul algorimului pentru un vector ade dimensiune nse va face prin mergesort(a,0,n-
1).
Demonstrat ¸ia corectitudinii algoritmului recursiv se face prin induct ¸ie: cazul
n= 1 este corect, pentru c ˘a un singur vector este considerat deja sortat. Presu-
punem c ˘a algoritmul mergesort sorteaz ˘a corect orice vector de lungime strict mai
mic dec ˆatn. Presupunem c ˘a algoritmul funct ¸ioneaz ˘a pentru un vector de dimen-
siune n. Astfel, algoritmul mergesort se apeleaz ˘a pentru doi subvectori de lugime
n
2
s ¸inn
2
. Conform ipotezei inductive, aceste dou ˘a subtablouri vor fi sortate
corect s ¸i, cum algoritmul de interclasare este corect, rezult ˘a c˘a, dup ˘a apelul acetuia,
va rezulta un tablou corect sortat.
2.1.2 Analiza complexit˘ at ¸ii
Ne focaliz ˘am pe comparat ¸iile s ¸i transferurile de elemente. Consider ˘am c ˘aT(n)
este num ˘arul de prelucr ˘ari efecutate de c ˘atre algoritmul de sortare prin intercla-
sare s ¸i Tmerge (n)num ˘arul de prelucr ˘ari efectuate de algoritmul de interclasare.
Presupunem c ˘a dimensiunea problemei este o putere a lui 2. Din punct de ve-
dere al comparat ¸iilor s ¸i trasferurilor de elemente, sortarea prin interclasare a unui
element nu necisit ˘a mult timp, adic ˘aT(1) = 0 . Pentru n > 1, num ˘arul ma-
xim de operat ¸ii de baz ˘a efectuate ˆın algoritmul de interclasare este de ordinul
(n). Deci, Tmerge2(n)ˆın cel mai defavorabil caz. Avem urm ˘atoarea relat ¸ie
de recurent ¸ ˘a privit ˘a din punctul de vedere al comparat ¸iilor s ¸i transferurilor de ele-
mente:
T(n) =8
<
:2Tn
2
+ (n);dac˘an >1
0;dac˘an= 1;
pentru timpul de execut ¸ie al algoritmului mergeSort ,ˆın cel mai defavorabil caz.
Aplic ˘amTeorema master , a=b=2, d=1 s ¸i a=bd, rezult ˘a c˘aT(n)2(nlogn),ˆın cel
mai defavorabil caz. Deci, putem spune c ˘aT(n)2(nlogn).
2.2 Metoda Quicksort (rapid˘ a)
A fost inventat de Hoare ˆın 1962 s ¸i se bazeaz ˘a de asemenea pe tehnica Divide-
et-Impera, dar ˆın plus are la baz ˘a s ¸i metoda interschimb ˘arii. Spre deosebire de
mergesort , partea iterativ ˘a a algoritmului este pentru a construi subcazuri, nu de
a combina solut ¸iile lor. Este considerat unul dintre cei mai rapizi s ¸i mai utilizat ¸i
algoritmi de sortare p ˆan˘aˆın acest moment.

Capitolul 2. Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 30
Quicksort are o list ˘a de sortat pe care o ˆımparte ˆın dou ˘a subliste deoarece sunt
mai us ¸or de sortat. Pentru a rezlva o astfel de problem ˘a trebuie sa urm ˘arim urm ˘atorii
pas ¸i:
Alegerea unui element al listei pe care ˆıl vom numi pivot s ¸i astfel am ˆımpart ¸it
lista ˆın dou ˘a subliste
Elementele mai mici dec ˆat pivotul se reordoneaz ˘aˆın as ¸a fel ˆıncˆat s˘a fie plasate
ˆınaintea pivotului, iar elementele mai mari s ˘a fie dup ˘a pivot. F ˘acˆand aceast ˘a
partit ¸ie putem spune c ˘a pivotul se afl ˘aˆın pozit ¸ia sa final ˘a
Se sorteaz ˘a cele dou ˘a p˘at ¸i prin tehnica recursiv ˘a, pˆan˘a cˆandˆın subliste r ˘amˆane
doar un singur element.
Astfel, putem spune acum c ˘a lista init ¸ial ˘a a fost sortat ˘a corect.
Quicksort partit ¸ioneaz ˘a lista init ¸ial ˘a. Fie un tablou a, partit ¸ionarea ˆınseamn ˘a
aranjarea elementelor vectorului init ¸ial astfel ˆıncˆat elementele aflate la st ˆanga s ˘a
fie mai mici sau egale cu a[s]s ¸i elementele aflate la dreapta de a[s]s˘a fie mai mari
sau egale cu acesta. Deci, a[0]; : : : ; a [s1]a[s]s ¸ia[s+ 1]; : : : ; a [n1]a[s].
Elementul a[s]este pivotul. ˆIn contiunuare, cele dou ˘a subtablouri sunt sortate ˆın
mod independent prin apeluri recursive ale algoritmului. S ˘a remarc ˘am c ˘a la qui-
cksort partit ¸ionarea este prelucrarea cea mai important ˘a a algoritmului, deoarece
aceata presupune identificarea pivotului , adic ˘a a acelui element a[s] pentru care
a[k]a[s];cuk < s s ¸ia[k]a[s];cuk > s . Aceast ˘a metod ˘a de sortare se numes ¸te
sortarea prin partit ¸ionare . Dac ˘a nu exist ˘a un pivot, atunci strategia este s ˘a creeze
unul. Sunt mai multe strategii de alegere a pivotului. Dar, vom discuta despre pi-
votul selectat elementul subtabloului drept, deci pivot =a[stang ]s ¸i presupunem
c˘a algoritmul de partit ¸ionare este apelat pentru subtabloul a[stang : : : drept ]. Se
pornes ¸te din ambele capete ale sale s ¸i se compar ˘a elementele cu pivotul. ˆIns˘a par-
curgerea de la st ˆanga la dreapta se realizeaz ˘a de la al doilea element. Astfel, pentru
aceasta vom folosi un indice i. Pentru c ˘a dorim ca elementele mai mici dec ˆat pi-
vot s ˘a fie ˆın partea st ˆanga a subtabloului, se sare peste elementele mai mici dec ˆat
pivotul s ¸i se opret ¸e la primul element mai mare sau egal cu acesta, a[i]. Invers,
parcurgerea se ˆıncepe cu ultimul element al subtabloului s ¸i folosim un indice j.
ˆIn acest caz, dorim ca elementele mai mari dec ˆat pivotul s ˘a fie aranjate ˆın partea
dreapt ˘a a subtabloului s ¸i parcurgerea sare peste elementele mai mari dec ˆat pivotul
s ¸i se opres ¸te atunci c ˆand primul element ˆıntˆalnit este mai mic sau egal cu acesta,
a[j]. Dup ˘a realizarea acestor parcurgeri se opresc s ¸i avem trei situat ¸ii posibile s ˘a
apar ˘a: dac ˘ai < j , atunci se interschimb ˘a elementele a[i]s ¸ia[j]s ¸i se reia parcur-
gerea increment ˆand indicele is ¸i decrement ˆand indicele j; dac ˘ai > j , atunci vom

Capitolul 2. Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 31
obt ¸ine partit ¸ionarea subtabloului dup ˘a interschimbarea pivotului cu elementul a[i];
dac˘ai=j, atunci i=j=ss ¸i am obt ¸inut partit ¸ionarea. Dar, ultimele dou ˘a cazuri
pot fi scrise ˆımpreun ˘a, interschimb ˆand pivotul cu a[j], pentru ij.
Se aplic ˘a procedeul ˆın continuu de la st ˆanga s ¸i de la dreapta pivotului, p ˆan˘a
cˆand aceste subliste sunt suficient de mici, adic ˘a se reduc la un singur element.
Algoritmul de sortarea Quicksort (rapid ˘a) scris sub form ˘a unui cod in C++ este
urm ˘atorul:
1#include<iostream>
2using namespace std;
3void schimb(int *x, int *y)
4{
5int variabila;
6variabila = *x;
7*x = *y;
8*y = variabila;
9}
10int Partitie(int a[], int l, int h)
11{
12int pivot, index, i;
13index = l;
14pivot = h;
15for (i = l; i < h; i++)
16{
17 if (a[i] < a[pivot])
18 {
19 schimb(&a[i], &a[index]);
20 index++;
21 }
22}
23schimb(&a[pivot], &a[index]);
24return index;
25}
26int RandomPivotPartition(int a[], int l, int h)
27{
28int pvt, n, temp;
29n = rand();
30pvt = l + n % (h – l + 1);
31schimb(&a[h], &a[pvt]);

Capitolul 2. Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 32
32return Partitie(a, l, h);
33}
34int QuickSort(int a[], int l, int h)
35{
36int pivindex;
37if (l < h)
38{
39 pivindex = RandomPivotPartition(a, l, h);
40 QuickSort(a, l, pivindex – 1);
41 QuickSort(a, pivindex + 1, h);
42}
43return 0;
44}
45int main()
46{
47int n, i;
48cout << "Introduceti dimensiunea vectorului pe care doriti
sa-l sortati: ";
49cin >> n;
50int a[100];
51for (i = 0; i < n; i++)
52{
53 cout << "Introduceti elementul vectorului " <<i+1<<": ";
54 cin >> a[i];
55}
56QuickSort(a, 0, n – 1);
57cout << "Vectorul sortat este: ";
58for (i = 0; i < n; i++)
59cout <<a[i]<<" ";
60return 0;
61}
S˘a observ ˘am mai bine ˆın urm ˘atorul exemplu cum se realizeaz ˘a metoda quicksort .
S˘a consider ˘am urm ˘atorul vector de sortat: 6, 4, 2, 10, 9, 3, 5, 7 .
Conform algoritmului de partit ¸ionare, pivot= 6 ,astfel c ˘a vectorul va fi partit ¸ionat
ˆın dou ˘a subtablouri: unul a c ˘arui elemente mai mici sau egale cu 6, iar cel ˘alalt
va avea elementele mai mari sau egale cu 5. Pornim cu doi indici is ¸ijce vor fi

Capitolul 2. Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 33
deplasat ¸i spre mijlocul vectorului, p ˆan˘a cˆand se returneaz ˘a pozit ¸ia de partit ¸ionare
s, iar pivotul este interschimbat cu a[s]:
6 4 2 10 9 3 5 7 (pivot=6)
i j
6 4 2 10 9 3 5 7
i j
Elementele a[i]s ¸ia[j]vor fi interschimbate, rezult ˆand vectorul:
6 4 2 5 9 3 10 7
i j
6 4 2 5 9 3 10 7
i j
6 4 2 5 3 9 10 7
j i
Pentru c ˘a am ajuns ˆın situat ¸ia ij, se interschimb ˘a pivortul cu a[s], unde
s=j= 5este pozit ¸ia de partit ¸ionare:
3 4 2 5 6 9 10 7
S˘a remarc ˘am c ˘a toate elementele mai mici dec ˆat pivotul sunt la st ˆanga aces-
tuia, iar cele mai mari, la dreapta. Se aplic ˘a recursiv algoritmul de sortare pentru
subs ¸irurile a[0: : :4] =f3;4;2;5gs ¸ia[6: : :7] =f9;10;7g:
2.2.1 Verificarea corectitudinii
Pentru a verifica corectitudinea algoritmului de partit ¸ionare, identific ˘am precondit ¸ia
s ¸i postcondit ¸ia: Pin=fstang < dreptg, iarPout=fa[k]a[s]pentru k=stang; : : : ;
s1s ¸ia[k]a[s]pentru k=s+ 1; : : : ; dreptg. Fie proprietatea I=fdac˘ai <
j;atunci a[k]pivot; k =stang; : : : ; i; iara[k]pivot pentru k=j; : : : ; drept; iar
dac˘aij;atunci a[k]pivot pentru k=stang; : : : ; i1;iara[k]pivot pentru k=
j+ 1; : : : ; dreptg. Cum i < j , proprietatea Ieste invariant ˘aˆın raport cu structura
repetitiv ˘awhile , iar dup ˘a ultima interschimbare a pivotului cu elementul a[s], cu
s=j, se obt ¸ine postcondit ¸ia. Pentru c ˘a avem condit ¸iile de oprire din cele dou ˘a
structuri repeat , asta asigur ˘a c˘a indicii is ¸ijr˘amˆanˆıntre limitele stang s ¸idrept .
Corectitudinea algoritmului recursiv se face prin induct ¸ie: cazul c ˆandn= 1este
corect, deoarece un vector cu un singur element este considerat sortat. Presupunem
c˘a algoritmul quicksort sorteaz ˘a corect orice vector de lungime strict mai mic ˘a dec ˆat
n. Presupunem c ˘a se apleaz ˘a algoritmul pentru un vector de lungime n. Astfel,
obit ¸inem partit ¸ia s. Acum vom verifica c ˘a oricare ar fi dou ˘a elemente de indici is ¸i
jsunt ˆın ordinea corect ˘a: dac ˘ai < js1saus+ 1i < j; atunci a[i]a[j],
conform ipotezei inductive; dac ˘ai < s < j , atunci a[i]pivota[j], datorit ˘a
faptului c ˘a algoritmul de partit ¸ionare este corect.

Capitolul 2. Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 34
2.2.2 Analiza complexit˘ at ¸ii
Consider ˘am drep operat ¸ii de baz ˘a doar comparat ¸iile, deoarece ˆın algoritmul de
partit ¸ionare, num ˘arul acestora este mai mare, ˆın general dec ˆat num ˘arul interschim-
b˘arilor.
Cazul cel mai defavorabil se obt ¸ine atunci c ˆand la fiecare partit ¸ionare se obt ¸ine
una din subprobleme de dimensiune 1. Deoarece operat ¸ia de partit ¸ionare necesit ˘a
O(qp)comparat ¸ii, rezult ˘a c˘a pentru acest caz num ˘arul de comparat ¸ii este O(n2).
Acest rezultat este oarecum surprinz ˘ator, av ˆand ˆın vedere c ˘a numele metodei este
”sortarea rapid ˘a”. As ¸a cum vom vedea, ˆıntr-o distribut ¸ie normal ˘a, cazurile pentru
care quicksort execut ˘an2comparat ¸ii sunt rare, fapt care conduce la o complexitate
medie foarte bun ˘a a algoritmului. ˆIn contiunuare determin ˘am num ˘arul mediu de
comparat ¸ii. Presupunem c ˘aq+ 1p=nlungimea secvent ¸ei s ¸i c ˘a probabilitatea
ca pivotul xs˘a fie al k-lea element este1
n. Rezult ˘a c˘a probabilitatea obt ¸inerii su-
bproblemelor de dimensiune kp=i1s ¸iqk=nieste1
n.ˆIn procesul
de partit ¸ionare, un element al tabloului,pivotul, este comparat cu toate celelalte,
astfel c ˘a sunt necesare n1comparat ¸ii. Acum num ˘arul mediu de comparat ¸ii se
calculeaz ˘a prin urm ˘atoarea formul ˘a:
Tmediu (n) =8
>><
>>:(n1) +1
nnX
i=1(Tmediu (i1) +Tmediu (ni));dac˘an1
1 ;dac˘an= 0:
Rezolv ˘am aceast ˘a recurent ¸ ˘a. Avem:
Tmediu (n) = (n1) +2
n(Tmediu (0) +


+Tmediu (n1))
nTmediu (n) =n(n1) + 2( Tmediu (0) +


+Tmediu (n1)).
Trecem pe nˆınn-1:
(n1)Tmediu (n1) = ( n1)(n2)+2( Tmediu (0)+


+Tmediu (n2)). Sc˘adem:
nTmediu (n) = 2( n1)+( n+1)Tmediu (n1).ˆImp ˘art ¸im prin n(n1)s ¸i rezolv ˘am
recurent ¸a obt ¸inut ˘a:
Tmediu (n)
n+1=Tmediu (n1)
n+2
n12
n(n+1)
=Tmediu (n1)
n1+2
n+2
n+1
2
(n1)n+2
n(n+1)
=: : :
=Tmediu (0)
1+2
1+


+2
n+1
2
1


2+


+2
n(n+1)
= 1 + 2
1
1+1
2+


+1
n+12
1
1


1+


+1
n(n+1)
:
Deoarece 1 +1
2+


+1
n=O(log2n)s ¸i seriaP1
k(k+1)este convergent ˘a, rezult ˘a
c˘aT(n) =O(nlog 2n).
Prin urmare, complexitatea medie a algoritmului quicksort esteO(nlog 2n).
Amintim o metod ˘a mai eficient ˘a de a alege pivotul (alegerea aleatoare a pi-

Capitolul 2. Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 35
votului, metoda ”medianei celor 3 valori”- ˆın care se alege elementul mijlociu ca
m˘arime, dintre trei elemente alese la ˆıntˆamplare din vector etc.), utilizarea algo-
ritmului de sortare prin insert ¸ie direct ˘a pentru subtablourile de dimensiune mic ˘a
(ˆıntre 5 s ¸i 15 elemente) sau renunt ¸area la soratarea subtabloului de dimensiune
mic˘a s ¸iˆıncheierea algoritmului de sortare prin insert ¸ie direct ˘a aˆıntregului tablou ce
este aproape sortat, modificarea algoritmului de partit ¸ionare (de exemplu, partit ¸ionarea
vectorului ˆın trei p ˘art ¸i: elementele mai mici dec ˆat pivotul ˆıntr-o parte, cele egale cu
pivotul ˆın cea de-a doua parte s ¸i cele mai mari ˆın cea de-a treia parte).
Un dezavantaj al algoritmului quicksort este faptul c ˘a nu este stabil.

Bibliografie
[1] T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introducere ˆ ın Algoritmi , Computer
Libris Agora, Cluj-Napoca, 2000 (traducere).
[2] D. Lucanu, M. Craus, Proiectarea Algoritmilor , Ed. Polirom, 2008.
[3] Cristian A.Giumale – Introducere in analiza algoritmilor .
[4] Anany Levitin Introduction to The Design and Analysis of Algorithms-3rd ed , Pear-
son.
[5] R ˘azvan Andonie, Ilie G ˆarbacea, Algoritmi Fundamentali O perspectiv˘ a
C++ ,Computer Libris Agora, Cluj-Napoca, 1995 (traducere).
[6]https://www.geeksforgeeks.org/merge-sort/ .
36