Lucrare de licent a [605833]

Universitatea \Alexandru Ioan Cuza" din Ias i
Facultatea de Matematic a
Analiza Algoritmilor de
Sortare
Lucrare de licent  a
Conduc ator  stiint ic:
Lect. dr. Ana – Maria Mos neagu
Candidat: [anonimizat], 2019
Ia si

Cuprins
Introducere 2
1 Analiza algoritmilor de sortare elementari 4
1.1 Algoritmi de sortare bazat i pe compararea elementelor . . . . . . . . 4
1.1.1 Sortarea prin Select ie (Select sort) . . . . . . . . . . . . . . . 4
1.1.2 Sortarea prin Insert ie (Insert sort ) . . . . . . . . . . . . . . . 8
1.1.3 Sortarea prin Interschimbare . . . . . . . . . . . . . . . . . . 15
1.2 Algoritmi de sortare care nu folosesc compararea ^ ntre elemente . . . 22
1.2.1 Sortarea prin num arare(Counting sort) . . . . . . . . . . . . . 22
1.2.2 Radix sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2 Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 27
2.1 Sortarea prin interclasare (Mergesort) . . . . . . . . . . . . . . . . . 28
2.2 Sortarea rapid a (Quicksort) . . . . . . . . . . . . . . . . . . . . . . . 32
3 Aplicat ii practice 39
Bibliograe 40
1

Introducere
Aceast a lucrare urm are ste analiza din punct de vedere teoretic, c^ at  si 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.
Ace sti algoritmi sunt folosit i pentru a sorta at^ at liste de tip numeric, c^ at  si liste
de tip alfabetic. ^Inc a de la ^ nceputurile informaticii, algoritmii de sortare au atras
un num ar mare de studii ^ n domeniu.
De si ideea de baz a a lor este aparent simpl a  si oarecum familiar a, complexitatea
rezolv arii eciente a sort arii este mare.
Existent a unor algoritmi de sortare ecient i este esent ial a pentru utilizarea op-
tim a a altor algoritmi, cum ar  cei de c autare, sau cei de interclasare.
Pentru a considera un algoritm ca ind de sortare, datele acestuia de ie sire
trebuie s a ^ ndeplineasc a dou a condit ii:
ordinea elementelor din datele de ie sire trebuie s a e ori cresc atoare, ori des-
cresc atoare
datele de ie sire trebuie s a e 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 clasica ^ n dou a marii cate-
gorii: metode directe  si metode avansate.
IMetodele directe se bazeaz a pe algoritmi de dicultate redus a, u sor de g asit
 si de ^ nt eles. ^In aceast a categorie se reg ase ste:
Analiza algoritmilor de sortare elementari care se clasic a ^ n:
{Algoritmi de sortare bazat i pe compararea elementelor  si este alc atuit
din:
(a) Sortarea prin select ie
(b) Sortarea prin insert ie
2

Cuprins 3
(c) Sortarea prin interschimbare
(d) Shaker sort
{Algoritmi de sortare care nu folosesc compararea ^ ntre elemente  si
este alc atuit din:
(a) Sortarea prin num arare (Counting sort)
(b) Radix Sort
IIMetodele avansate se bazeaz a pe algoritmi put in mai complicat i, dar care
nu necesit a cuno stint e avansate de algoritmic a. Aici se reg ase ste:
Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera care
cuprinde:
(a) Sortarea MergeSort
(b) Sortarea QuickSort
Orice programator trebuie s a cunoasc a metodele de sortare  si s a aleag a folosirea
unei metode, ^ n funct ie de criteriul de ecient  a urm arit. Ecient 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  si memoria folosit a.

Capitolul 1
Analiza algoritmilor de sortare
elementari
1.1 Algoritmi de sortare bazat i pe compararea elemen-
telor
^In acest capitol vom presupune o secvent  a nit a format a din nelemente a0; a1; :::;
an1, dintr-o mult ime total ordonat a. A sorta aceast a secvent  a ^ nseamn a a rea-
ranja componentele acesteia ^ ntr-o anumit a ordine, premut^ andu-le. Presupunem c a
secvent a dat a este stocat a ^ ntr-un vector (tablou unidimensional). Formal, problema
sort arii ()cresc atoare) poate  denit a astfel:
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 care au avantajul c a sunt simpli, dar, ^ n
general, au performant e sc azute pentru tablouri de dimensiune mare :
I Sortarea prin Select ie
II Sortarea prin Insert ie
III Sortarea prin Interschimbare.
Vom verica corectitudinea pentru ecare algoritm descris  si ^ i vom analiza comple-
xitatea.
1.1.1 Sortarea prin Select ie (Select sort)
Metoda se bazeaz a pe selectarea, la ecare pas al algoritmului, a unui anumit
element din secvent  a  si apoi plasarea sa pe pozit ia corect a a  sirului. Algoritmii de
4

Capitolul 1. Analiza algoritmilor de sortare elementari 5
sortare ce au la baz a aceast a metod a diferit a ^ n funct ie de criteriul de select ie a
elementului: minim  si maxim din secvent a corespunz atoare.
Sortarea prin select ie a elementului minim
Prima dat a, se determin a cel mai mic element al tabloului. ^In acest sens, se
determin a indicele mastfel ^ nc^ at a[i]> a[m];8i= 0;1; : : : ; n1; i6=m:^In acest
caz, cel mai mic element, a[m], este plasat pe prima pozit ie ^ n  sirul sortat prin
interschimbarea elementului a[0] cu a[m]. Se repet a aceea si operat ie pentru sub sirul
r amas de sortat la ecare pas p^ an a c^ and ram^ ane doar un singur element sau  sirul
este aranjat cresc ator.
Algoritmul de sortare prin select ia elementului minim implementat ^ n C++ este
urm atorul:
1# include <iostream >
2using namespace std;
3void sort (int a[], int n) {
4 int i, min , m, j, temp ;
5 for (i = 0; i < n -1; i++)
6 {
7 min = a[i];
8 m = i;
9 for (j = i + 1; j < n; j++)
10 if (a[j]< min)
11 {
12 min = a[j];
13 m = j;
14 }
15 if(a[i ]!=a[m])
16 {
17 temp = a[i];
18 a[i] = a[m];
19 a[m] = temp ;
20 }
21 }
22}
23int main ()
24{
25 int a[20] , n, i;
26 cout << " Introduceti dimensiunea vectorului : n=";

Capitolul 1. Analiza algoritmilor de sortare elementari 6
27 cin >> n;
28 cout << " Introduceti elementele vectorului :" << endl ;
29 for (i = 0; i < n; i++)
30 {
31 cout << "a[" << i << "]=";
32 cin >> a[i];
33 }
34 sort (a, n);
35 cout << " Dupa sortarea prin selectia minimului ,
vectorul este : ";
36 for (i = 0; i < n; i++)
37 cout << a[i] << " ";
38 return 0;
39}
De exemplu, consider am urm atorul  sir pe care ne propunem s a-l sort am cresc ator
folosind metoda prezentat a:
10, 91, 2, 6, 11, 56, 23, 15, 19, 0.
Pas 1: Se determin a indicele elementului minim, m= 9  si se interschimb a
elementele a[0]  si a[9].
S irul devine: 0, 91, 2, 6, 11, 56, 23, 15, 19, 10.
Pas 2: Se determin a indicele elementului minim din sub sirul a[1::9],m= 2  si se
interschimb a elementele a[1]  si a[2].
S irul este acum: 0, 2, 91, 6, 11, 56, 23, 15, 19, 10.
Pas 3: Se determin a indicele elementului minim din sub sirul a[2::9],m= 3  si se
interschimb a elementele a[2]  si a[3].
S irul este acum: 0, 2, 6, 91, 11, 56, 23, 15, 19, 10.
Pas 4: Se determin a indicele elementului minim din sub sirul a[3::9],m= 9  si se
interschimb a elementele a[3]  si a[9].
S irul este acum: 0, 2, 6, 10, 11, 56, 23, 15, 19, 91.
Pas 5: Se determin a indicele elementului minim din sub sirul a[4::9],m= 4, dar
nu se realizeaz a nicio interschimbare deoarece a[4] coincide cu minimul sub sirului.
Pas 6: Se determin a indicele elementului minim din sub sirul a[5::9],m= 7  si se
interschimb a elementele a[5]  si 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 sub sirul a[6::9],m= 8  si se
interschimb a elementele a[6]  si a[8].
S irul este acum: 0, 2, 6, 10, 11, 15, 19, 56, 23, 91.

Capitolul 1. Analiza algoritmilor de sortare elementari 7
Pas 8: Se determin a indicele elementului minim din sub sirul a[7::9],m= 8  si se
interschimb a elementele a[7]  si a[8].
S irul este acum: 0, 2, 6, 10, 11, 15, 19, 23, 56, 91.
Pas 9: Se determin a indicele elementului minim din sub sirul a[8::9],m= 8  si nu
se realizeaz a nicio interschimbare deaorece a[8] coincide cu minimul sub sirului.
Algoritmul se opre ste,  sirul ind complet sortat.
Vericarea corectitudinii: Consider am c a precondit ia  si postcondit ia sunt:
Pin=fn2Ng siPout=fa[0]a[1]: : :a[n1]g. S a ar at am c a
proprietatea
I1 =fa[0]a[1]: : :a[i1]  sia[i1]a[j];8j=i; : : : ; n1g
este invariant a pentru ciclul fordup a i. Init ial, i= 0, deci I1 este satisf acut a la
intrare ^ n structura repetitiv a deoarece  sirul sortat este vid. Pentru ecare i, ^ n
ciclul fordup a 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
I2 =fa[m]a[k]; k= 1; : : : ; j1g;
adev arat la intrarea ^ n bucl a, r amas adev arat pe parcursul iterat iei, iar la ie sirea din
bucl a, I2 =fa[m]a[k]; k=i; : : : ; n1g:A sadar,
a[0]a[1]: : :a[i]  sia[i]a[j];8j=i+ 1; : : : ; n1:
Cum ieste incrementat la sf^ ar situl ec arei iterat ii, reg asim proprietatea invariant a.
La ie sirea din bucla fordup a i, invariantul conduce la postcondit ie, pentru c a
i=n1  sia[0]a[1]: : :a[n2]  sia[n2]a[n1]:
Pentru ecare dintre cele dou a cicluri for, variabila contor de iterat ie este in-
crementat a la ecare iterat ie, deci pot  identicate funct ii de terminare cores-
punz atoare. Pentru ciclul exterior, consider am funct ia de terminare t(k) =n1ik,
iar pentru ciclul interior, t(k) =njk. Deci, dup a un num ar nit de iterat ii condit iile
de contiunuare nu vor mai  ^ ndeplinite, execut ia algoritmului ^ ncheindu-se. Prin
urmare, algoritmul se va termina ^ ntr-un num ar nit de pa si, demonstr^ andu-se astfel
total corectitudinea algoritmului.
Analiza complexit at ii: Not am cu TC(n) num arul de comparat ii, iar cu TM(n)
num arul de mut ari efectuate pentru a sorta cresc ator tabloul dat  si cu T(n) timpul de

Capitolul 1. Analiza algoritmilor de sortare elementari 8
execut ie al algoritmului ce depinde de dimensiunea problemei(num arul de elemente
ale tabloului)  si de caracteristicile datelor de intrare (distribut ia init ial a a elementelor
^ n secvent  a). Num arul de comparat ii nu depinde de distribut ia init ial a a elementelor,
ind egal cu
TC(n) = (n1) + ( n2) +


+ 1 =n(n1)
2:
^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 ecare
iterat ie ise efectueaz a o interschimbare, deci trei mut ari  si TM(n) = 3( n1).
A sadar,
0TM(n)3(n1):
Cum T(n) =TC(n) +TM(n), obt inem c a
n(n1)
2T(n)(n1)(n+ 6)
2;
 si deci T(n)2(n2), deoarece T(n)2
(n2)  siT(n)2O(n2).
Sortarea prin select ie a 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 indicele M pentru care
a[i]< a[M],8i= 0;1; :::; n1; i6=M. Apoi sunt interschimbate elementele a[n1]
 sia[M] (elementul maxim este plasat pe ultima pozit ie ^ n  sir). Procedeul se repet a
pentru sub sirul format din elementele a[0]; a[1]; :::; a [n2]. Se caut a elementul cel
mai mare din acest sub sir  si se interschimb a cu a[n2]  s.a.m.d., p^ an a c^ and sub sirul
va cont ine un singur element.
Vericarea corectitudinii algoritmului prin select ia maximului se realizeaz a asem a-
n ator cu cel al algoritmului prin select ia minimului.
1.1.2 Sortarea prin Insert ie (Insert sort )
Sortarea prin insert ie direct a
Aceast a metod a de sortare const a ^ n identicarea pozit iei pentru ecare ele-
ment a[i]; i1, ^ n sub sirul a[0: : : i1], deja ordonat. 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 ase ste un element a[j], ^ n sub sirul deja ordonat,
astfel ^ nc^ at a[j]6a[i]. Se insereaz a elementul a[i] dup a a[j], deplas^ andu-se ^ nt^ ai
elementele a[i1]; a[i2]; : : : ; a [j+ 1] cu o pozit ie la dreapta.

Capitolul 1. Analiza algoritmilor de sortare elementari 9
Algoritmul de sortare prin insert ie direct a implementat in C++ este urm atorul:
1 # include <iostream >
2 using namespace std;
3 void insert ( int a[], int n)
4 {
5 int aux ,j;
6 for (int i=0; i < n;i++)
7 {
8 j = i -1;
9 aux=a[i];
10 while (j >=0 && aux < a[j])
11 {
12 a[j +1]= a[j];
13 j –;
14 }
15 a[j +1]= aux;
16 }
17 }
18 int main ()
19 {
20 int a[100] , n, i;
21 cout << " Introduceti dimensiunea vectorului , n= ";
22 cin >> n;
23 cout << " Introduceti vectorul :" << endl ;
24 for (int i = 0; i < n; i++)
25 {
26 cout << "a[" << i << "]= ";
27 cin >> a[i];
28 }
29 insert (a, n);
30 cout << " Vectorul sortat este : ";
31 for (i = 0; i < n; i++)
32 cout << a[i] << " ";
33 return 0;
34 }
Presupunem c a vrem s a sort am  sirul:
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

Capitolul 1. Analiza algoritmilor de sortare elementari 10
^ nceputul problemei suntem ^ n cazul ^ n care lista de elemente este vid a. Algoritmul
va alege c^ ate un element din  sirul init ial  si ^ l va insera ^ n lista de elemente sortate.
Elementele din  sirul init ial se aleg ^ n ordinea ^ n care apar ele ^ n  sir. ^In exemplul
nostru le vom alege ^ n ordinea 20, 7, 3, 5, etc.
Pasul 1. Vom ^ ncepe cu elementul a[0] = 20. Cum lista de elemente sortate este
vid a, insert ia lui va  foarte simpl a. Vom obt ine:
20, 7, 3, 5, 6, 2, 11, 10.
Pasul 2. Apoi urmeaz a elementul a[1] = 7. Vrem s a ^ l inser am ^ n lista de
elemente 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 ecient spat iul de memorie ^ l vom
aduce pe 20 ^ n locul lui 7  si pe urm a ^ l vom pune pe 7 ^ naintea lui 20 prin intermediul
variablie aux. Vom obt ine:
7, 20, 3, 5, 6, 2, 11, 10.
Pasul 3. Apoi urmeaz a a[2] = 3. Pe 3 ar trebui s a ^ l inser am ^ naintea lui 7. Din
nou, pentru a folosi ecient spat iul de memorie, deplas am pe 7  si pe 20 spre dreapta
cu o pozit ie,  si pe urm a plas am pe 3 ^ naintea lor. Vom obt ine:
3, 7, 20, 5, 6, 2, 11, 10.
Pasul 4. Urmeaz a elementul a[3] = 5. Pe 5 trebuie s a ^ l inser am ^ ntre 3  si 7.
Vom deplasa pe 7 si 20 spre dreapta cu o pozit ie. ^In felul acesta se va elibera o
pozit ie ^ ntre 3  si 7, loc unde ^ l vom plasa pe 5. Obt inem:
3, 5, 7, 20, 6, 2, 11, 10.
Procedeul continu a ^ n mod similar p^ an a c^ and  si ultimul element din  sirul original
este plasat pe pozit ia corect a ^ n  sirul ordonat.
Putem vedea cum  sirul ordonat se construie ste treptat peste  sirul nesortat, ^ n
acela si spat iu de memorie ocupat de acesta.
Ideea de principiu este c a la pasul kavem deja k1 numere sortate  si vrem s a
plas am elementul a[k] pe pozit ia corect a ^ ntre aceste k1 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 a[k]. Cum toate numerele
de la dreapta lui sunt mai mari ca el  si toate numerele de la st^ anga lui sunt mai mici
ca el, rezult a c a avem acum knumere sortate  si putem trece la pasul k+ 14.
Vericarea corectitudinii: S a ar at am c a
I1 =fa[0]a[1]: : :a[i1]g
este inavariant pentru ciclul fordup a i(elementele  sirului sortat, a[0]; : : : ; a [i1],
sunt elementele  sirului original de la 0 la i1, permutate). Init ial, i= 1, deci
precondit ia implic a faptul c a  sirul format dintr-un singur element poate  consi-

Capitolul 1. Analiza algoritmilor de sortare elementari 11
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
I2 =fa[0]a[1]: : :a[j]  siauxa[j+ 1] = a[j+ 2]: : :a[i]g:
Vom ar ata c a aceasta este o proprietate invariant a pentru structura repetitiv a while .
La intarea ^ n ciclu, j=i1; aux =a[i] =a[j+1], iar  sirul 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 a aux < a [j] =a[j+ 1]: : :a[i]. Dup a
execut ie prelucr arii j=j1; a[0]a[1]: : :a[j]  siaux < a [j+ 1] = a[j+ 2]
: : :a[i]. Deci, I2 este un invariant pentru ciclul while .
La sf^ ar situl 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 ie sirea din bucla for; i =n, invariantul implic a
postcondit ia.
Justicarea termin arii ^ n timp nit a algoritmului este aceea si ca ^ n cazul algo-
ritmului de sortare prin select ia minimului, consider^ and funct ia de terminare pentru
ciclul exterior t(k) =nik, iar pentru ciclul interior
t(k) =8
<
:jk+ 1;dac a aux < a [jk]
0;dac a auxa[jk]
Analiza complexit at ii: At^ at num arul comparat iilor, c^ at  si num arul mut arilor
depinde de distribut ia init ial a a elementelor ^ n secvent  a. ^In cazul cel mai favorabil,
pentru ecare i= 1;2; : : : ; n1, are loc o singur a comparat ie  si dou a mut ari ( aux=
a[i]; a[j+ 1] = a[i]). Lu^ and ^ n calcul  si mut arile  si comparat ile, se obt ine o margine
inferioar a pentru timpul de execut ie,
3(n1)T(n):

Capitolul 1. Analiza algoritmilor de sortare elementari 12
^In cazul cel mai defavorabil, pentru ecare i= 1;2; : : : ; n1, au loc icomparat ii  si
i+ 2 mut ari. Obt inem o margine superioar a 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)  siT(n)2O(n2):
Sortarea prin insert ie cu pas variabil (shellsort)
Metoda a fost propus a, ^ n anul 1959, de c atre Donald Shell  si este cunoscut a sub
numele de shellsort .
Shellsort este o extensie simpl a a sort arii prin insert ie direct a  si care, se poate
executa 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  si ecare grup a av^ and
elementele distant ate la un anumit pas h, numit increment. Acest lucru poart a
numele de h-sortare .
Ideea principal a a acestui tip de sortare este aceea de a sorta prin insert ie di-
rect a^ n mod repetat toate elementele la distant e xe: h1; h2; : : : ; h k= 1  si hi+1< hi.
Exist a mai multe modalit at i de a alege increment ii, de alegerea acestora depinz^ and
performant a algoritmului. Alegerea increment ilor se dovede ste a  foarte impor-
tant a. Increment ii pot  ale si dup a o putere a lui 2 sau putem folosi un tablou de
increment i cu valori descresc atoare, ultima dintre acestea ind obligatoriu 1. Pentru
aumite alegeri ale secvent ei de increment i se pot obt ine algoritmi de complexitate
mai mic a dec^ at cea a algoritmului de sortare prin insert ie direct a. Un astfel de  sir
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  sir de increment i, deoarece este u sor de implementat
(are aceea si complexitate ^ n cel mai defavorabil caz):
1;4;13;40;121;364;1093;3280; : : :
A sadar, 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

Capitolul 1. Analiza algoritmilor de sortare elementari 13
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 defavo-
rabil. 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 nal.
Algoritmul de sortare prin insert ie cu pas variabil (shellsort) implementat in
C++ este urm atorul:
1 # include <iostream >
2 using namespace std;
3 void shellSort ( double a[], int n)
4 {
5 int i, j, h;
6 double aux ;
7 h=1;
8 while (h< n/3)
9 {
10 h=3* h+1; // sirul de incrementi sugerat de Knuth
11 }
12 while (h >=1)
13 {
14 for(i=h;i < n -1;i++)
15 {
16 aux =a[j];
17 j=i;
18 while (j >=h && a[j-h] > aux)
19 {
20 a[j]=a[j-h];
21 j=j-h;
22 }
23 a[j]= aux;
24 }
25 h=h/3;

Capitolul 1. Analiza algoritmilor de sortare elementari 14
26 }
27 }
28 int main ()
29 {
30 double a [100];
31 int i, n;
32 cout << " Introduceti dimensiunea vectorului pe care
doriti sa -l sortati : ";
33 cin >> n;
34 for (i = 0; i < n; i++)
35 {
36 cout << " Introduceti elementul vectorului " <<i+1<<"
:";
37 cin >> a[i];
38 }
39 shellSort (a, n);
40 cout << " Vectorul sortat este : ";
41 for (i = 0; i < n; i++)
42 cout << a[i] << " ";
43 return 0;
44 }
De exemplu, consider am urm atorul  sir:
11, 23, 17, 46, 35, 49, 8, 66, 20, 52, 6, 21, 44, 32, 57.
Vom folosi algoritmul de sortare prin mic sorarea incrementului folosind secvent a
de increment i 7, 4, 1.
Pas 1: Grupele de sortat, la distant a de 7 pa si sunt: f11, 66, 57g,f23, 20g,f17,
52g,f46, 6g,f35, 21g,f49, 44g,f8, 32g. Sortate prin inserare direct a, devin: f11,
57, 66g,f20, 23g,f17, 52g,f6, 46g,f21, 35g,f21, 35g,f44, 49g,f8, 32g.
Noul tablou este:
11, 20, 8, 6, 21, 32, 17, 35, 23, 44, 46, 57, 49, 52, 66.
Pas 2: Grupele de sortat, la distant a de 4 pa si sunt: f11, 21, 23, 49g,f20, 44,
52, 32g,f17, 8, 46, 66g,f6, 57, 35g. Grupele sortate prin insert ie direct a: f11, 21,
23, 49g,f20, 32, 44, 52g,f8, 17, 46, 66g,f6, 35, 57g.
Tabloul devine:
11, 20, 8, 6, 21, 32, 17, 35, 23, 44, 46, 57, 49, 52, 66.
Pas 3: Sortarea la distant a de 1 pas duce la sortarea ^ ntregului tablou, de fapt
ind vorba de sortarea prin insert ie direct a aplicat a ^ ntregului tablou.

Capitolul 1. Analiza algoritmilor de sortare elementari 15
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.1.3 Sortarea prin Interschimbare
Bubblesort
Este una dintre cele mai simple metode de sortare,^ ns a inecient a pentru tablouri
de dimensiuni mari.
Interschimb arile se consider a pentru elementele vecine ale secvent ei de sortat ce
nu sunt ^ n ordinea corect a  si au loc p^ an a c^ and elementele vectorului sunt complet
ordonate. Aceast a variant a de sortare se mai nume ste  si metoda bulelor sau
BubbleSort .
Elementul principal al acestui tip de sortare const a ^ n compararea elementelor
a[i]  sia[i+ 1]; dac a a[i]< a[i+ 1], atunci se trece la urm atoarea comparare, adic a
a[i+ 1] cu a[i+ 2], dac a nu, se interschimb a a[i] cua[i+ 1]  si apoi se compar a
a[i+ 1] cu a[i+ 2]. Dup a prima parcurgere a vectorului, pe ultima pozit ie va
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 sucient a, ci trebuie continuat p^ an a c^ and nu se mai efectueaz a
interschimb ari.
Algoritmul de sortarea prin interschimbare(Bubble Sort) implementat in C++
este urm atorul:
1 # include <iostream >
2 using namespace std;
3 void bubble ( int a[], int n)
4 {
5 int i,j;
6 double aux ;
7 for (i=n -1; i >= 0;i –)
8 {
9 for(j=0;j <= i -1;j++)
10 {
11 if(a[j]>a[j +1])
12 {
13 aux=a[j];
14 a[j]=a[j +1];
15 a[j +1]= aux;
16 }

Capitolul 1. Analiza algoritmilor de sortare elementari 16
17 }
18 }
19 }
20 int main () {
21 int n,a[100] , i;
22 cout << " Introduceti dimensiunea vectorului : n=";
23 cin >> n;
24 cout << " Introduceti elementele vectorului :" << endl ;
25 for (i = 0; i < n; i++)
26 {
27 cout << "a[" << i << "]=";
28 cin >> a[i];
29 }
30 bubble (a, n);
31 cout << " Vectorul sortat este :";
32 for (i = 0; i < n; i++)
33 cout << a[i] << " ";
34 return 0;
35 }
Exemplu. S a consider am c a  sirul de sortat este:
79, 40, 65, 81, 25, 38, 13.
Pasul 1:
79$40 65 81 25 38 13 (prin " $" am indicat o interschimbare)
40 79$65 81 25 38 13
40 65 79 81$25 38 13
40 65 79 25 81$38 13
40 65 79 25 38 81 $13
40 65 79 25 38 13 81
La nalul primului pas, cel mai mare element din  sir se a
 a pe ultima pozit ie
a  sirului. Deci, acesta nu va mai face parte din subsecvent a ce va  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

Capitolul 1. Analiza algoritmilor de sortare elementari 17
La nalul acestui pas, cel mai mare element al sub sirului este pozit ionat acum
pe penultima pozit ie a  sirului init ial. Prin urmare, acesta nu va mai face parte din
subsecvent a ce va  parcurs a ^ n continuare.
Pasul 3:
40 65$25 38 13
40 25 65$38 13
40 25 38 65$13
40 25 38 13 65
La nalul celui de-al treilea pas, num arul 65 se a
 a pe pozit ia corect a ^ n  sirul
sortat.
Pasul 4:
40$25 38 13
25 40$38 13
25 38 40$13
25 38 13 40
Num arul 40 se a
 a ^ n pozit ia corect a ^ n  sirul sortat.
Pasul 5:
25 38$13
25 13 38
Elementul 38 este pe pozit ia sa nal a ^ n  sirul sortat.
Pasul 6:
25$13
13 25
^In acest moment, am terminat procesul de sortare deoarece  sirul este ordonat:
13;25;38;40;65;79;81:
Vericarea corectitudinii: Consider am proprietatea
I1 =fa[j]a[k]; k= 0; : : : ; jg:
S a ar at am c a aceast a proprietate este invariant a pentru ciclul interior fordup a j.
La intrarea ^ n ciclu, ( j= 0), proprietatea este adev arat a, pentru c a a[0]a[0].
Presupunem c a proprietatea este adev arat a la ^ nceputul iterat iei. Dac a a[i]> a[j+
1], atunci se realizeaz a interschimbarea elementelor  si acestea vor  ^ n ordinea a[j]<
a[j+ 1], iar dac a a[j]a[j+ 1], nu se efectueaz a interschimb ari, dar proprietatea
este adev arat a. A sadar, proprietatea I1 r am^ ane adev arat a la sf^ ar situl iterat iei.
Dup a incrementarea variabilei jreg asim proprietatea I1. Ceea ce se realizeaz a ^ n
ciclul interior este plasarea celui mai mare element din secvent a a[0]; a[1]; : : : ; a [i] pe
pozit ia i.

Capitolul 1. Analiza algoritmilor de sortare elementari 18
Fie proprietatea
I2 =fa[i+ 1]: : :a[n1];cua[i+ 1]a[j]; j= 0; : : : ; ig:
Proprietatea este invariant a pentru ciclul exterior fordup a i: la intrarea ^ n ciclu,
i=n1, deci proprietatea este adev arat a ( sir vid), apoi r am^ ane adev arat a ^ n bucl a
conform celor demonstrate anterior, iar la ie sirea din bucl a, i= 0, deci proprietatea
devine I2 =fa[1]: : :a[n1];cua[1]a[0]g, ceea ce implic a postcondit ia.
Pentru a demonstra c a ambele cicluri sunt nite, consider am funct ia de terminare
pentru ciclul exterior, t(k) =ik, iar pentru ciclul interior, t(k) =ikjk.
Analiza complexit at ii: Num arul de comparat ii nu depinde de propriet at ile da-
telor de intrare, acesta ind
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  sir, deci
vom analiza cazurile extreme. ^In cazul cel mai favorabil num arul de mut ari ale
elementelor ^ n vederea sort arii este TM(n) = 0, iar ^ n cazul cel mai defavorabil se
obt ine TM(n) =3n(n1)
2:A sadar, 0TM(n)3n(n1)
2:Cum T(n) =TC(n) +
TM(n))n(n1)
2T(n)2n(n1);deciT(n)2(n2).
Algoritmul poate  ^ 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.
Algoritmul de sortare prin interschimbare (^ mbun at at it) implementat ^ n C++
este urm atorul:
1 # include <iostream >
2 using namespace std;
3 void bubble2 ( int a[], int n)
4 {
5 int i,m;
6 bool schimb ;
7 double aux ;
8 m= n;
9 do
10 {
11 schimb = false ;
12 for(i=0;j <= m -2;j++)

Capitolul 1. Analiza algoritmilor de sortare elementari 19
13 {
14 if(a[i]>a[i +1])
15 {
16 aux=a[i];
17 a[i]=a[i +1];
18 a[i +1]= aux;
19 schimb = true ;
20 }
21 }
22 m= m -1;
23 } while ( schimb ==0) ;
24 }
25 int main () {
26 int n,a[100] , i;
27 cout << " Introduceti dimensiunea vectorului : n=";
28 cin >> n;
29 cout << " Introduceti elementele vectorului :" << endl ;
30 for (i = 0; i < n; i++)
31 {
32 cout << "a[" << i << "]=";
33 cin >> a[i];
34 }
35 bubble2 (a, n);
36 cout << " Vectorul sortat este :";
37 for (i = 0; i < n; i++)
38 cout << a[i] << " ";
39 return 0;
40 }
^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 prive ste
num arul de mut ari, se obt ine aceea si estimare ca ^ n cazul general. Deci, n1
T(n)2n(n1). Prin urmare, avem c a T(n)2
(n)  siT(n)2O(n2).
Shaker sort
Modic^ and algoritmul de sortare prin interschimbarea elementelor vecine, sort am
elementele unui tablou, astfel ca la ecare pas s a se plaseze pe pozit iile nale c^ ate
dou a elemente: minimul, respectiv maximul din subtabloul parcurs la pasul respec-

Capitolul 1. Analiza algoritmilor de sortare elementari 20
tiv.
Algoritmul shaker sort implementat ^ n C++ este urm atorul:
1# include <iostream >
2using namespace std;
3void shaker (int a[], int n)
4{
5 bool swapped = true ;
6 int s= 0;
7 int e = n – 1;
8 while ( swapped )
9 {
10 swapped = false ;
11 for (int i = s; i < e; ++i)
12 {
13 if (a[i] > a[i + 1])
14 {
15 swap (a[i], a[i + 1]) ;
16 swapped = true ;
17 }
18 }
19 if (! swapped )
20 break ;
21 swapped = false ;
22 –e;
23 for (int i = e – 1; i >= s; –i)
24 {
25 if (a[i] > a[i + 1])
26 {
27 swap (a[i], a[i + 1]) ;
28 swapped = true ;
29 }
30 }
31 ++s;
32 }
33}
34int main ()
35{
36 int n, a[100] , i;

Capitolul 1. Analiza algoritmilor de sortare elementari 21
37 cout << " Introduceti dimensiunea vectorului : n=";
38 cin >> n;
39 cout << " Introduceti elementele vectorului :" << endl ;
40 for (i = 0; i < n; i++)
41 {
42 cout << "a[" << i << "]=";
43 cin >> a[i];
44 }
45 shaker (a, n);
46 cout << " Vectorul sortat este :";
47 for (i = 0; i < n; i++)
48 cout << a[i] << " ";
49 return 0;
50}
De exemplu:
Fie urm atorul  sir: 6 ;2;5;3;9;1;3.
Pas 1:
6!2 5 3 9 1 3 (prin !indic am o interschimbare spre dreapta)
2 6!5 3 9 1 3
2 5 6!3 9 1 3
2 5 3 6!9 1 3
Observ am c a 6 este mai mic ca 9, deci mai departe interschimb am cu 9.
2 5 3 6 9!1 3
2 5 3 6 1 9!3
2 5 3 6 1 3 9
La nalul primului pas, cel mai mare element din  sir se a
 a pe ultima pozit ie.
Pas 2:
2 5 3 6 1 3 9 (prin indic am o interschimbare spre st^ anga)
2 5 3 6 1 3 9
2 5 3 1 6 3 9
2 5 1 3 6 3 9
2 1 3 6 3 9
1 2 5 3 6 3 9
La nalul celui de=al doilea pas, cel mai mic elemente din  sir se a
 a pe pozit ia
primului indice al  sirului.
Pas 3:
1 2!5 3 6 3 9
1 2 5!3 6 3 9

Capitolul 1. Analiza algoritmilor de sortare elementari 22
1 2 3 5!6 3 9
1 2 3 5 6!3 9
1 2 3 5 3 6 9
La nalul acestui pas, num arul 6 se a
 a pe pozit ia corect a ^ n  sirul sortat.
Pas 4:
1 2 3 5 3 6 9
1 2 3 3 5 6 9
Acum,  sirul este deja sortat, dar algoritmul nu  stie dac a e nalizat. Deci, algo-
ritmul trebuie s a completeze aceast a trecere integral a, f ar a a interschimba.
1 2 3 3 5 6 9
1 2 3 3 5 6 9.
Debea acum putem spune c a am terminat procesul de sortare.
1.2 Algoritmi de sortare care nu folosesc compararea
^ ntre elemente
1.2.1 Sortarea prin num arare(Counting sort)
Fie un tablou a[0: : : n1], de dimensiune n, cu elementele din mult imea f0;1;2;
: : : ; mg. Pentru sortarea unui astfel de tablou poate  descris un algoritm de sor-
tare de complexitate liniar a, dac a mnu este semnicativ mai mare dec^ at n. Pa sii
algoritmului sunt:
i) se construiet e tabloul f[0: : : m ] al frecvent elor de aparit ie a valorilor ele-
mentelor tabloului a(fireprezint a de c^ ate ori apare valoarea i^ n tabloul
a; i= 0; : : : ; m );
ii) se calculeaz a tabloul frecvent elor cumulate, fc[0: : : m ]; fci=Pi
j=0fj; i=
0; : : : ; m ;
iii) se folose ste tabloul frecvent elor cumulate pentru a contrui tabloul ordonat b.
Counting sort implementat in C++ este urm atorul:
1# include < iostream >
2# include < algorithm >
3using namespace std;
4int getMax (int array [], int size )
5{
6 int max = array [1];
7 for (int i = 2; i <= size ; i++)

Capitolul 1. Analiza algoritmilor de sortare elementari 23
8 {
9 if ( array [i] > max )
10 max = array [i];
11 }
12 return max ;
13}
14void countSort (int *a, int n)
15{
16 int b [100];
17 int max = getMax (a, n);
18 int f [100];
19 for (int i = 0; i <= max; i++)
20 f[i] = 0;
21 for (int i = 1; i <= n; i++)
22 f[a[i ]]++;
23 for (int i = 1; i <= max; i++)
24 f[i] += f[i – 1];
25 for (int i = n; i >= 1; i –)
26 {
27 b[f[a[i]]] = a[i];
28 f[a[i]] -= 1;
29 }
30 for (int i = 1; i <= n; i++)
31 {
32 a[i] = b[i];
33 }
34}
35int main ()
36{
37 int n, i;
38 cout << " Introduceti dimensiunea vectorului : ";
39 cin >> n;
40 int a [100];
41 cout << " Introduceti elementele vectorului :\n";
42 for (i = 1; i <= n; i++)
43 {
44 cout << "a[" << i << "]=";
45 cin >> a[i];

Capitolul 1. Analiza algoritmilor de sortare elementari 24
46 }
47 countSort (a, n);
48 cout << " Vectorul sortat este : ";
49 for (i = 1; i <= n; i++)
50 cout << a[i] << " ";
51 return 0;
52}
De exemplu:
Fie  sirul:
1 5 3 3 1 1 2 2 1 2 1 3 5 3
Pas 1. Analiz am frecvent a ec arei aparit ie a numerelor din  sirul respectiv.
Num arul 0 nu apare niciodat a ^ n  sir, 1 apare de cinci ori ^ n  sir, 2 apare de trei
ori, 3 apare de patru ori, 4 nu apare nicodat a  si 5 apare de dou a ori.
Pas 2. Se realizeaz a un  sir cu frecvent ele analizate:
0 5 3 4 0 2
Algoritmul de sortare prin num arare are timpul de execut ie O(m+n). Dac a
m2O(n) atunci algoritmul are complexitate liniar a. Dac a meste mult mai mare
dec^ at n(de exemplu m2O(n2)), atunci ordinul de complexitate al algoritmului de
sortare este determinat de m.
1.2.2 Radix sort
Fie un tablou a[0: : : n1] de dimensiune n, cu elemente numere naturale cu cel
mult kcifre.
Algoritmul este bazat pe urm atoarea idee: folosind counting sort, se ordoneaz a
tabloul ^ n raport cu cifra cea mai put in semnicativ a a ec arui num ar, apoi se
sorteaz a ^ n raport cu cifra de rang imediat superior  s.a.m.d., p^ an a se ajunge la cifra
cea mai semnicativ a.
Dac a m= 10keste semnicativ mai mare dec^ at n, atunci sortarea prin num arare
nu este ecient a. Dar dac a keste mult mai mic dec^ at n, atunci se poate obt ine un
algoritm de complexitate O(kn).
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{
5 int max = a [0];
6 for (int i = 1; i < n; i++)

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

Capitolul 1. Analiza algoritmilor de sortare elementari 26
45 radixsort (a, n);
46 cout << " Vectorul sortat este : ";
47 for (i = 0; i < n; i++)
48 cout << a[i] << " ";
49 return 0;
50}
De exemplu:
Consider am urm atorul tablou:
180;55;85;90;902;34;2;76
Pas 1: ^Incepem s a sort am dup a cel mai mic num ar semncativ al unit at ilor
din tabloul. Obt inem urm atorul tabloul:
180;90;902;2;34;55;85;76.
Oberv am c a 180 apare ^ n fat a lui 90 pentru c a 180 a avut loc ^ naintea lui 90 ^ n
tablou, similar  si pentru 902 cu 2  si 55 cu 85.
Pas 2: Apoi, sort am dup a num arul zecilor  si obt inem:
902;2;34;55;76;180;85;90.
Observ am c a 902 revine din nou ^ naitea lui 2 pentru c a acesta este implementat
^ n fat a lui 2.
Pas 3: Apoi, sort am dup a num arul sutelor  si obt inem:
2;34;55;76;85;90;180;902.
^In acest moment, am terminat procesul de sortare deoarece tabloul este ordonat.

Capitolul 2
Analiza algoritmilor de sortare
bazat i pe metoda
Divide-et-Impera
Divide-et-Impera este o una dintre cele mai cunoscute metode de proiectare a
algoritmilor. 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 problema
init ial a. Aceste mici probleme, de regul a sunt rezolvate ^ n mod recursiv  si dup a se
regrupeaz a rezultatele pentru a crea o solut ie problemei init iale.
Pentru a rezolva o astfel de problem a trebuie parcur si trei pa si 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 specice acestei metode sunt algoritmii de parcurgere a arborilor bi-
nari  si 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)
 si sortarea rapid a(Quicksort).
27

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 28
Vom enunt a un rezultat important pentru analiza ecient ei algoritmilor
bazat i pe tehnica diviz arii , numit Teorema master . Presupunem c a o problem a
de dimensiune neste descompus a ^ n bsubprobleme de aceea si dimensiune, egal a cu
n=b. De asemenea, presupunem c a doar aprobleme dintre acestea necesit a s a e
rezolvate, ab(a sibsunt constante, a1,b >1). Consider am c a divizarea pro-
blemei init iale ^ n bsubprobleme de dimensiune n=b si compunerea solut iilor acestor
subprobleme au ^ mpreun a costul f(n), iar costul rezolv arii cazului elementar este o
constant a T0. Astfel, timpul de execut ie al algoritmului general satisface recurent a
T(n) =8
<
:T0;dac a nn0
aT(n=b) +f(n);dac a n > n 0:
^In mod evident, ordinul de cre stere al lui T(n) depinde de ordinul de cre stere a lui
f(n)  si de valorile constatelor a sib:
Teorema 1. (Teorema master) Dac a f(n)2(nd); d0, atunci
T(n) =8
>>><
>>>:(nd);dac a a < bd
(ndlogn);dac a a=bd
(nlogba);dac a a > bd:
2.1 Sortarea prin interclasare (Mergesort)
Mergesort este un exemplu bun pentru aplicarea tehnicii Divide-et- Impera. Fie
un  sir pe care ^ l imp art im ^ n dou a sub siruri de lungimi aproximativ egale. Cele dou a
 siruri sunt ordonate recursiv folosind acelea si tehnici de sortare, adic a mergesort .
Apoi rezultatele sunt combinate (interclasate), obt in^ and astfel tabloul init ial sortat.
Prin interclasare se ^ ntelege parcurgerea celor dou a secvent e ordonate  si extragerea
de elemente din acestea astfel ^ n^ at s a obt inem  sirul init ial sortat. Aceste subsecvent e
sunt parcurse simultan cu dou a contoare  si se compar a elementele curente. Cel mai
mic element dintre cele dou a este plasat ^ n  sirul nal, iar contorul utlizat pentru
parcurgerea sub sirului 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  si elementele care
r am^ an ^ n cealalt a secvent  a sunt plasate direct ^ n  sirul nal.
Mergesort implementat in C++ este urm atorul:
1# include <iostream >
2using namespace std;
3
4void Merge (int a[], int l, int h, int m)

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 29
5{
6 int i, j, k, temp [50];
7 i = l;
8 k = 0;
9 j = m + 1;
10 while (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 }
25 while (i <= m)
26 {
27 temp [k] = a[i];
28 k++;
29 i++;
30 }
31 while (j <= h)
32 {
33 temp [k] = a[j];
34 k++;
35 j++;
36 }
37 for (i = l; i <= h; i++)
38 {
39 a[i] = temp [i – l];
40 }
41}
42void MergeSort (int a[], int l, int h)

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 30
43{
44 int m;
45 if (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{
56 int n, i;
57 cout << " Introduceti dimensiunea vectorul pe care
doriti sa -l sortati : ";
58 cin >> n;
59 int a [100];
60 for (i = 0; i < n; i++)
61 {
62 cout << " Introduceti elementele vectorului " << i + 1
<< ": ";
63 cin >> a[i];
64 }
65 MergeSort (a, 0, n – 1);
66 cout << " Vectorul sortat este : ";
67 for (i = 0; i < n; i++)
68 cout << a[i]<<" ";
69 return 0;
70}
Un exemplu clar care ^ ndeplinet e condit iile acestui algoritm:
Fie vectorul: 9 ;8;10;4;7;5;18;17.
Pasul 1. Se ^ njum at at e ste vectorul, form^ andu-se dou a secvent e:(9, 8, 10, 4)  si
(7, 5, 18, 17).
Pasul 2. ^In continuare proced am la fel pentru prima secvent  a:(9,8)  si (10, 4).
Pasul 3. Proced am la fel pentru prima subsecvent  a din prima secvent a:(9), (8).
Pasul 4. Similar  si pentru secvent a: (10, 4).
Pasul 5. Am obt inut vectori de dimensiune unu care se interclaseaz a:(9) cu (7)

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 31
 si (10) cu (4). Deci, am obt inut secvent a: (3, 8, 9, 10).
Pasul 6. Se procedeaz a analog  si pentru secvent a: (7, 5, 18, 17). S i obit inem:
(5, 7, 17, 18).
Pasul 7. Am obt iunut vectorul: 3 ;8;9;10;5;7;17;18.Cu ajutorul interclas arii se
obt ine vectorul sortat: 4 ;5;7;8;9;10;17;18.
Vericarea corectitudini: Pornim de la stabilirea precondit iilor  si a postcondit ii-
lor: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 asunti, respectiv j. Astfel, vom con-
sidera proprietatea invariant a I=ftemp [k]a[l]; l=i; : : : ; mijloc  sitemp [k]
a[l]; lj; : : : ; dreptgpentru prima strunctur a while . Astfel spus, elementul pe care
tocmai l-am copiat ^ n temo [k] este cel mai mic dintre elementele r amase netransfe-
rate din cele dou a p art i ale vectorului 4 a. Acum toate elementele r amase ^ n avor
 transferate ^ n temp [k+ 1]; : : : ; temp [dreptstang ], pentru c a vectorul temp este
completat la st^ anga. Deci, la ^ ncheierea algoritmului merge , va  vericat a condit ia
temp [k]temp [l];8k < l , ceea se ^ nseamn a c a, dup a copierea elementelor din temp
^ na, tabloul va  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  si de la mijloc ladrept , sunt deja sortate. Deci, a[i]a[l]; l=
i+ 1; : : : ; mijloc  sia[j]a[l]; l=j+ 1; : : : ; drept . A sadar, a[i]  sia[j] sunt cele
mai mici elemente r amase netransferate. Dac a a[i]a[j], atunci temp [k] va primi
valoarea a[i]  si deci va  adev arat a relat ia a[i]a[l]; l=j; : : : ; drept . Asem anator
este  si 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; n1).
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. Presupunem
c a algoritmul mergesort sorteaz a corect orice vector de lungime strict mai mic dec^ at
n. Presupunem c a algoritmul funct ioneaz a pentru un vector de dimensiune n. Astfel,
algoritmul mergesort se apeleaz a pentru doi subvectori de lugimen
2
 sinn
2
.
Conform ipotezei inductive, aceste dou a subtablouri vor  sortate corect  si, cum
algoritmul de interclasare este corect, rezult a c a, dup a apelul acetuia, va rezulta un
tablou corect sortat.

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 32
Analiza complexit at ii: Ne focaliz am pe comparat iile  si transferurile de elemente.
Consider am c a T(n) este num arul de prelucr ari efecutate de c atre algoritmul de
sortare prin interclasare  si 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 vedere al comparat iilor  si trasferurilor de elemente, sortarea prin interclasare
a unui element nu necisit a mult timp, adic a T(1) = 0. Pentru n > 1, num arul
maxim 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  si transferurilor de elemente:
T(n) =8
<
:2Tn
2
+ (n);dac a n >1
0;dac a n= 1;
pentru timpul de execut ie al algoritmului mergeSort , ^ n cel mai defavorabil caz.
Aplic am Teorema master ,a=b= 2; d= 1  si a=bd, rezult a c a T(n)2(nlogn),
^ n cel mai defavorabil caz. Deci, putem spune c a T(n)2(nlogn).
2.2 Sortarea rapid a (Quicksort)
A fost inventat de Hoare ^ n 1962  si se bazeaz a de asemenea pe tehnica Divide-
et-Impera, dar ^ n plus are la baz a  si 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  si mai utilizat i
algoritmi de sortare p^ an a ^ n acest moment.
Quicksort are o list a de sortat pe care o ^ mparte ^ n dou a subliste deoarece sunt
mai u sor de sortat. Pentru a rezlva o astfel de problem a trebuie sa urm arim urm atorii
pa si:
Alegerea unui element al listei pe care ^ l vom numi pivot  si astfel am ^ mpart it
lista ^ n dou a subliste
Elementele mai mici dec^ at pivotul se reordoneaz a ^ n a sa fel ^ nc^ at s a e plasate
^ naintea pivotului, iar elementele mai mari s a e dup a pivot. F ac^ and aceast a
partit ie putem spune c a pivotul se a
 a ^ n pozit ia sa nal 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 a
ate la st^ anga s a e

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 33
mai mici sau egale cu a[s]  si elementele a
ate la dreapta de a[s] s a e mai mari
sau egale cu acesta. Deci, a[0]; : : : ; a [s1]a[s]  sia[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
quicksort partit ionarea este prelucrarea cea mai important a a algoritmului, deoa-
rece aceata presupune identicarea pivotului , adic a a acelui element a[s] pentru care
a[k]a[s];cuk < s  sia[k]a[s];cuk > s . Aceast a metod a de sortare se nume ste
sortarea prin partit ionare . Dac a nu exist a un pivot, atunci strategia este s a cre-
eze unul. Sunt mai multe strategii de alegere a pivotului. Dar, vom discuta despre
pivotul selectat elementul subtabloului drept, deci pivot =a[stang ]  si presupunem
c a algoritmul de partit ionare este apelat pentru subtabloul a[stang : : : drept ]. Se
porne ste din ambele capete ale sale  si 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 e ^ n partea st^ anga a subtabloului, se sare peste elementele mai mici dec^ at
pivotul  si se opret e la primul element mai mare sau egal cu acesta, a[i]. Invers,
parcurgerea se ^ ncepe cu ultimul element al subtabloului  si folosim un indice j.
^In acest caz, dorim ca elementele mai mari dec^ at pivotul s a e aranjate ^ n partea
dreapt a a subtabloului  si parcurgerea sare peste elementele mai mari dec^ at pivotul
 si se opre ste atunci c^ and primul element ^ nt^ alnit este mai mic sau egal cu acesta,
a[j]. Dup a realizarea acestor parcurgeri se opresc  si avem trei situat ii posibile s a
apar a: dac a i < j , atunci se interschimb a elementele a[i]  sia[j]  si se reia parcurgerea
increment^ and indicele i si decrement^ and indicele j; dac a i > j , atunci vom obt ine
partit ionarea subtabloului dup a interschimbarea pivotului cu elementul a[i]; dac a
i=j, atunci i=j=s si am obt inut partit ionarea. Dar, ultimele dou a cazuri pot
scrise ^ mpreun a, interschimb^ and pivotul cu a[j], pentru ij.
Se aplic a procedeul ^ n continuu de la st^ anga  si de la dreapta pivotului, p^ an a c^ and
aceste subliste sunt sucient de mici, adic a se reduc la un singur element.
Quicksort implementat in C++ este urm atorul:
1# include < iostream >
2using namespace std;
3void schimb (int *x, int *y)
4{
5 int variabila ;
6 variabila = *x;
7 *x = *y;
8 *y = variabila ;
9}

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 34
10int Partitie (int a[], int l, int h)
11{
12 int pivot , index , i;
13 index = l;
14 pivot = h;
15 for (i = l; i < h; i++)
16 {
17 if (a[i] < a[ pivot ])
18 {
19 schimb (&a[i], &a[ index ]);
20 index ++;
21 }
22 }
23 schimb (&a[ pivot ], &a[ index ]);
24 return index ;
25}
26int RandomPivotPartition (int a[], int l, int h)
27{
28 int pvt , n, temp ;
29 n = rand ();
30 pvt = l + n % (h – l + 1);
31 schimb (&a[h], &a[pvt ]);
32 return Partitie (a, l, h);
33}
34int QuickSort (int a[], int l, int h)
35{
36 int pivindex ;
37 if (l < h)
38 {
39 pivindex = RandomPivotPartition (a, l, h);
40 QuickSort (a, l, pivindex – 1);
41 QuickSort (a, pivindex + 1, h);
42 }
43 return 0;
44}
45int main ()
46{
47 int n, i;

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 35
48 cout << " Introduceti dimensiunea vectorului pe care
doriti sa -l sortati : ";
49 cin >> n;
50 int a [100];
51 for (i = 0; i < n; i++)
52 {
53 cout << " Introduceti elementul vectorului " <<i+1<<":
";
54 cin >> a[i];
55 }
56 QuickSort (a, 0, n – 1);
57 cout << " Vectorul sortat este : ";
58 for (i = 0; i < n; i++)
59 cout <<a[i]<<" ";
60 return 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  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 i sijce vor
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]  sia[j] vor  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= 4 este 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-

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 36
tuia, iar cele mai mari, la dreapta. Se aplic a recursiv algoritmul de sortare pentru
sub sirurile a[0: : :3] =f3;4;2;5g sia[5: : :7] =f9;10;7g:
3 4 2 5 (pivot =3)
i j
3 4 2 5
i j
3 2 4 5
j i .
Se interschimb a pivotul cu a[s], unde s=j= 1 este pozit ia de partit ionare:
2;3;4;5
Se aplic a recursiv algoritmul de sortare pentru sub sirurile a[0: : :0] =f2g si
a[2: : :3] =f4;5g. Primul caz este elementar,  sirul format dintr-un singur element
ind implicit sortat.
4 5 (pivot =3)
i j
4 5
j i
Se returneaz a pozit ia de interschimbare, s=j= 2.Apoi se apeleaz a recursiv
algoritmul de sortare pentru sub sirurile: a[2: : :1] sia[3: : :3]. Primul caz este cores-
punz ator unui sub sir vid, iar al doilea este un caz elementar.
Apelul algoritmului de sortare pentru subsecvent a a[5: : :7] =f9;10;7g:
9 10 7 (pivot =9)
i j
Elementele a[i]  sia[j] vor  interschimbate, rezult^ and vectorul:
9 7 10
i j
Indicii vor iar a si deplasat i,
9 7 10
j i
Se interschimb a pivotul cu elementul a[s]  si se returneaz a pozit ia de interschim-
bare, s=j= 6.
7;9;10
Se apeleaz a recursiv algoritmul de sortare pentru sub sirurile: a[5: : :5]  sia[7: : :7].
Ambele sunt cazuri elementare. Algoritmul se opre ste.
Vericarea corectitudinii: Pentru a verica corectitudinea algoritmului de par-
tit ionare, identic am precondi- t ia  si postcondit ia: Pin=fstang < dreptg, iar
Pout=fa[k]a[s] pentru k=stang; : : : ; s1  sia[k]a[s] pentru k=s+
1; : : : ; dreptg. Fie proprietatea I=fdac a i < j; atunci a[k]pivot; k =stang; : : : ; i;
iara[k]pivot pentru k=j; : : : ; drept; iar dac a ij;atunci a[k]pivot pentru

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 37
k=stang; : : : ; i1;iara[k]pivot pentru k=j+ 1; : : : ; dreptg. Cum i < j , pro-
prietatea Ieste invariant a ^ n raport cu structura repetitiv a while , iar dup a ultima
interschimbare a pivotului cu elementul a[s], cus=j, se obt ine postcondit ia. Pen-
tru c a avem condit iile de oprire din cele dou a structuri repeat , asta asigur a c a indicii
i sijr am^ an ^ ntre limitele stang  sidrept .
Corectitudinea algoritmului recursiv se face prin induct ie: cazul c^ and n= 1 este
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 verica c a oricare ar  dou a elemente de indici i si
jsunt ^ n ordinea corect a: dac a i < js1 sau s+ 1i < j; atunci a[i]a[j],
conform ipotezei inductive; dac a i < s < j , atunci a[i]pivota[j], datorit a
faptului c a algoritmul de partit ionare este corect.
Analiza complexit at ii: Consider am drept 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 ecare 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". A sa cum vom vedea, ^ ntr-o distribut ie normal a, cazurile pentru
care quicksort execut a n2comparat 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 a q+ 1p=nlungimea secvent ei  si c a probabilitatea
ca pivotul xs a e al k-lea element este1
n. Rezult a c a probabilitatea obt inerii
subproblemelor de dimensiune kp=i1  siqk=nieste1
n.^In procesul de
partit ionare, un element al tabloului,pivotul, este comparat cu toate celelalte, astfel
c a sunt necesare n1 comparat 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 a n1
1 ;dac a n= 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)).

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 38
Trecem pe n^ nn1:
(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)  si 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)  si 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 ecient a de a alege pivotul (alegerea aleatoare a pivotului,
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 algoritmului de
sortare prin insert ie direct a pentru subtablourile de dimensiune mic a (^ ntre 5  si 15
elemente) sau renunt area la soratarea subtabloului de dimensiune mic a  si ^ ncheierea
algoritmului de sortare prin insert ie direct a a^ ntregului tablou ce este aproape sortat,
modicarea algoritmului de partit ionare (de exemplu, partit iona- rea 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  si cele mai mari ^ n cea de-a treia parte).
Un dezavantaj al algoritmului quicksort este faptul c a nu este stabil.

Capitolul 3
Aplicat ii practice
Aplicat ia 1. La sf^ ar situl lunii iunie la proba de 150 m vitez a din cadrul unei
competit ii de atletism particip a 9 participant i de sex feminin reprezent^ and ecare
cate un club sportiv. Primele 3 ^ n clasament, ^ n funct ie de timpul cel mai mic
de sosire, vor  recrutate s a fac a parte din echipa nat ional a a t  arii. Presupunem
c a acestea nu depinde de rezultatul alteia, deci sunt independente  si urmeaz a o
repartit ie uniform a de 10.5 secunde  si 11.5 secunde. Determinat i timpii celor 3
sportive.
39

Bibliograe
[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 ,
Pearson.
[5] R azvan Andonie, Ilie G^ arbacea, Algoritmi Fundamentali O perspectiv a
C++ ,Computer Libris Agora, Cluj-Napoca, 1995 (traducere).
40