Lucrare de licent a [605832]

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 ( SelectSort ) . . . . . . . . . . . . . . . . . 4
1.1.2 Sortarea prin insert ie ( InsertSort ) . . . . . . . . . . . . . . . . 8
1.1.3 Sortarea prin interschimbarea elementelor vecine . . . . . . . . 15
1.2 Algoritmi de sortare care nu folosesc compararea ^ ntre elemente . . . . 22
1.2.1 Sortarea prin num arare ( CountingSort ) . . . . . . . . . . . . . 22
1.2.2 Sortarea pe baza cifrelor RadixSort . . . . . . . . . . . . . . . . 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 40
Bibliograe 54
1

Introducere
^In aceast a lucrare ne-am propus s a descriem principalii algoritmi de sortare  si
s a-i analiz am din punct de vedere al corectitudinii  si ecient ei lor asimptotice.
Problema sort arii const a ^ n rearanjarea ^ ntr-o ordine specicat a a elementelor
unei colect ii de date. ^Inc a de la ^ nceputurile informaticii, algoritmii de sortare au fost
intens studiat i. De si ideea de baz a a lor este aparent simpl a, s-a c autat ecientizarea
acestora.
Pentru a considera un algoritm ca ind un algoritm corect 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.
Metodele de sortare cele mai frecvent folosite se pot clasica ^ n dou a marii cate-
gorii: metode elementare  si metode avansate de sortare.
Metodele elementare se bazeaz a pe algoritmi de dicultate redus a, u sor de
descris  si de ^ nt eles. ^In aceast a categorie se reg asesc: algoritmii de sortare bazat i pe
compararea elementelor (sortarea prin select ie, sortarea prin insert ie, sortarea prin
interschimbarea elementelor vecine)  si algoritmi de sortare care nu folosesc compara-
rea ^ ntre elemente (sortarea prin num arare ( CountingSort )  si sortarea pe baza cifrelor
(RadixSort ).
Metodele avansate se bazeaz a pe algoritmi ceva mai complicat i, care nece-
sit a cuno stint e avansate de algoritmic a: de exemplu, algoritmii de sortare bazat i
pe metoda Divide-et-Impera (sortarea prin interclasare ( MergeSort ), sortarea rapid a
(QuickSort )).
Analiza unui algoritm se refer a la dou a aspecte: corectitudinea  si complexitatea
lui.
Un algoritm este part ial corect , dac a algoritmul este nit  si se termin a cu rezul-
tatele dorite. Pe de alt a parte, un algoritm este total corect , dac a se termin a ^ n timp
nit  si cu rezultatele a steptate.
2

Cuprins 3
Complexitatea unui algoritm se refer a la cantitatea de resurse consumate la
execut ie, adic a timp de execut ie  si spat iu de memorie. ^In cele ce urmeaz a vom
analiza complexitatea unui algoritm doar din perspectiva timpului s au de execut ie.
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. Astfel, ^ n funct ie de dimen-
siunea problemei de rezolvat  si de caracteristicile datelor de intrare, se va alege una
sau alta dintre tehnicile de sortare.

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 nnumere [ 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 :
1. Sortarea prin select ie
2. Sortarea prin insert ie
3. Sortarea prin interschimbarea elementelor vecine.
Vom verica corectitudinea pentru ecare algoritm descris  si ^ i vom analiza comple-
xitatea.
1.1.1 Sortarea prin select ie ( SelectSort )
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 sortat. Algoritmii
4

Capitolul 1. Analiza algoritmilor de sortare elementari 5
de sortare ce au la baz a aceast a metod a diferit a ^ n funct ie de criteriul de select ie a:
de exemplu, minimul sau maximul 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  si  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 SelectSort ( double a[], int n)
4{
5 int i, j, m;
6 double aux ;
7 for (i = 0; i < n – 1; i++)
8 {
9 m = i;
10 for (j = i + 1; j < n; j++)
11 {
12 if (a[m] > a[j])
13 m = j;
14 }
15 if (m != i)
16 {
17 aux = a[m];
18 a[m] = a[i];
19 a[i] = aux;
20 }
21 }
22}
23int main ()
24{
25 double a [20];
26 int n, i;

Capitolul 1. Analiza algoritmilor de sortare elementari 6
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 SelectSort (a, n);
36 cout << " Dupa sortarea prin selectia minimului , vectorul
este : ";
37 for (i = 0; i < n; i++)
38 cout << a[i] << " ";
39 cout << endl ;
40 return 0;
41}
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 ele-
mentele 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].

Capitolul 1. Analiza algoritmilor de sortare elementari 7
S irul este acum: 0, 2, 6, 10, 11, 15, 19, 56, 23, 91.
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. 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 ur-
mare, algoritmul se va termina ^ ntr-un num ar nit de pa si, demonstr^ andu-se astfel
total corectitudinea algoritmului.

Capitolul 1. Analiza algoritmilor de sortare elementari 8
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
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 in-
terschimb 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 metod a 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, iar complexitatea este aceea si.
1.1.2 Sortarea prin insert ie ( InsertSort )
Sortarea prin insert ie direct a
Aceast a metod a de sortare const a ^ n identicarea pozit iei pentru ecare element
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[i
2]; : : : , p^ an a c^ and se g ase ste un element a[j], ^ n sub sirul deja ordonat, astfel ^ nc^ at

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

Capitolul 1. Analiza algoritmilor de sortare elementari 10
36 return 0;
37 }
Presupunem c a vrem s a sort am  sirul:
20, 7, 3, 5, 6, 2, 11, 10.
Lista de elemente sortate p^ an a la un moment dat se va construi ^ n partea din
st^ anga a tabloului init ial. La ^ nceputul problemei suntem ^ n cazul ^ n care lista de
elemente sortate cont ine doar primul element. 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
7, 3, 5, etc.
Pasul 1. Vom ^ ncepe cu 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 2. 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 3. 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 knumere sortate  si vrem s a
plas am elementul a[k] pe pozit ia corect a ^ ntre aceste knumere sortate. Deplas am
spre dreapta toate numerele care sunt mai mari dec^ at elementul a[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 k+ 1 numere sortate  si putem trece la pasul urm ator.
Vericarea corectitudinii. S a ar at am c a
I1 =fa[0]a[1]: : :a[i1]g

Capitolul 1. Analiza algoritmilor de sortare elementari 11
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-
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

Capitolul 1. Analiza algoritmilor de sortare elementari 12
inferioar a pentru timpul de execut ie,
3(n1)T(n):
^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 . Aceast a metod a a de sortare este o extensie a sort arii prin
insert ie direct a  si care, poate avea performant e mai bune ^ n ceea ce prive ste timpul
de execut ie, permit ^ and schimburi de elemente la distant e mai mari. Ideea este de a
rearanja un vector pe grupe, ecare grup a av^ and elementele distant ate la un anumit
pash, numit increment. Grupele vor  sortate prin insert ie direct a, aceast a sortare
numindu-se h-sortare .
Ideea principal a a acestui tip de sortare este aceea de a sorta prin insert ie direct a
^ n mod repetat toate elementele la distant e xe: h1; h2; : : : ; h k= 1, cu 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 important 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 cu cel de mai sus):
1;4;13;40;121;364;1093;3280; : : :

Capitolul 1. Analiza algoritmilor de sortare elementari 13
A sadar, dup a cum se observ a, cel de-al i-lea increment este egal cu de 3 ori incre-
mentul 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 defavorabil.
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;

Capitolul 1. Analiza algoritmilor de sortare elementari 14
24 }
25 h = h/3;
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 cout << endl ;
44 return 0;
45 }
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.

Capitolul 1. Analiza algoritmilor de sortare elementari 15
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.
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 interschimbarea elementelor vecine
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.
Metoda se bazeaz a pe 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 BubbleSort implementat in C++ este urm atorul:
1 # include <iostream >
2 using namespace std;
3 void BubbleSort ( double 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 }
17 }

Capitolul 1. Analiza algoritmilor de sortare elementari 16
18 }
19 }
20 int main ()
21 {
22 double a [100];
23 int n, i;
24 cout << " Introduceti dimensiunea vectorului : n=";
25 cin >> n;
26 cout << " Introduceti elementele vectorului :";
27 for (i = 0; i < n; i++)
28 {
29 cout << "a[" << i << "]=";
30 cin >> a[i];
31 }
32 BubbleSort (a, n);
33 cout << " Vectorul sortat este :";
34 for (i = 0; i < n; i++)
35 cout << a[i] << " ";
36 return 0;
37 }
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 BubbleSort2 ( double 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; i <= m -2; i++)

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 != false );
24 }
25 int main ()
26 {
27 double a [100];
28 int n, i;
29 cout << " Introduceti dimensiunea vectorului : n=";
30 cin >> n;
31 cout << " Introduceti elementele vectorului :" << endl ;
32 for (i = 0; i < n; i++)
33 {
34 cout << "a[" << i << "]=";
35 cin >> a[i];
36 }
37 BubbleSort2 (a, n);
38 cout << " Vectorul sortat este :";
39 for (i = 0; i < n; i++)
40 cout << a[i] << " ";
41 return 0;
42 }
^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, n1T(n)2n(n1).
Prin urmare, avem c a T(n)2
(n)  siT(n)2O(n2).

Capitolul 1. Analiza algoritmilor de sortare elementari 20
ShakerSort
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 respectiv.
ShakerSort implementat ^ n C++ este:
1# include <iostream >
2using namespace std;
3
4void ShakerSort ( double a[], int n)
5{
6 int s, d, i, t;
7 double aux ;
8 s = 0;
9 d = n -1;
10 do
11 {
12 t = 0;
13 for (i = s; i <= d – 1; i++)
14 {
15 if (a[i] > a[i + 1])
16 {
17 aux = a[i];
18 a[i] = a[i + 1];
19 a[i + 1] = aux;
20 t = i;
21 }
22 }
23 if (t != 0)
24 {
25 d = t;
26 t = 0;
27 for (i = d; i >= s + 1; i –)
28 {
29 if (a[i] < a[i – 1])
30 {
31 aux = a[i];
32 a[i] = a[i – 1];

Capitolul 1. Analiza algoritmilor de sortare elementari 21
33 a[i – 1] = aux;
34 t = i;
35 }
36 }
37 s = t;
38 }
39 } while (t != 0 && s != d);
40}
41int main ()
42{
43 double a [100];
44 int n, i;
45 cout << " Introduceti dimensiunea vectorului : n=";
46 cin >> n;
47 cout << " Introduceti elementele vectorului :" << endl ;
48 for (i = 0; i < n; i++)
49 {
50 cout << "a[" << i << "]=";
51 cin >> a[i];
52 }
53 ShakerSort (a, n);
54 cout << " Vectorul sortat este :";
55 for (i = 0; i < n; i++)
56 cout << a[i] << " ";
57 return 0;
58}
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.

Capitolul 1. Analiza algoritmilor de sortare elementari 22
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
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 ( CountingSort )
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 elemen-
telor tabloului a(fireprezint a de c^ ate ori apare valoarea i^ n tabloul a; i=
0; : : : ; m );

Capitolul 1. Analiza algoritmilor de sortare elementari 23
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.
Algoritmul de sortare prin num arare ( CountingSort ) implementat in C++ este:
1# include < iostream >
2using namespace std;
3void CountingSort (int a[], int n, int m)
4{
5 int b [100];
6 int f [100];
7 for (int i = 0; i <= m; i++)
8 f[i] = 0;
9 for (int i = 0; i < n; i++)
10 f[a[i ]]++;
11 for (int i = 1; i <= m; i++)
12 f[i] += f[i – 1];
13 for (int i = n -1; i >= 0; i –)
14 {
15 b[f[a[i]] -1] = a[i];
16 f[a[i]] -= 1;
17 }
18 for (int i = 0; i < n; i++)
19 {
20 a[i] = b[i];
21 }
22}
23int main ()
24{
25 int a[100] , n, m, i;
26 cout << " Introduceti dimensiunea vectorului : ";
27 cin >> n;
28 cout << " Introduceti elementele vectorului :\n";
29 for (i = 0; i < n; i++)
30 {
31 cout << "a[" << i << "]=";
32 cin >> a[i];
33 }

Capitolul 1. Analiza algoritmilor de sortare elementari 24
34 cout << " Introduceti m="; cin >> m;
35 CountingSort (a, n, m);
36 cout << " Vectorul sortat este : ";
37 for (i = 0; i < n; i++)
38 cout << a[i] << " ";
39 return 0;
40}
De exemplu, e  sirul:
9, 4, 1, 7, 9 ,1, 2, 0.
Observ am c a  sirul nostru are valori cuprinse ^ ntre 0 si 9, deci m= 9. Ideea este
s a num ar am de c^ ate ori apare cifra 0, de c^ ate ori apare cifra 1  si tot a sa p^ an a la
ultima cifr a, 9. Deoarece exist a 10 valori posibile, vom folosi un  sir de 10 elemente,
toate init ializate cu 0. Realiz am  sirul frecvent elor astfel: primul element este 9, deci
vom incrementa f[9]. Al doilea element este 4  si deci vom incrementa f[4]  s.a.m.d.,
vom ajunge la urm atorul  sir al frecvent elor:
1, 2, 1, 0, 1, 0, 0, 1, 0, 2.
Se calculeaz a apoi  sirul frecvent elor cumulate:
1, 3, 4, 4, 5, 5, 5, 6, 6, 8
Folosind  sirul frecvent elor cumulate, determin am tabloul bal elementelor sortate.
De exemplu: a[7] = 0  si f[0] = 1. Atunci ^ nseamn a c a acest element va  plasat pe
prima pozit ie ^ n b(b[f[a[7]]1] = a[7]). ^In nal,  sirul sortat beste copiat ^ n  sirul
init ial a:
0, 1, 1, 2, 4, 7, 9, 9.
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 Sortarea pe baza cifrelor RadixSort
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 CountingSort , se ordoneaz a
tabloul ^ n raport cu cifra cea mai put in semnicativ a a ec arui num ar, apoi se sor-
teaz 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

Capitolul 1. Analiza algoritmilor de sortare elementari 25
algoritm de complexitate O(kn).
RadixSort implementat in C++ este:
1# include <iostream >
2using namespace std;
3void CountingSort (int a[], int n, int m, int c)
4{
5 int b[100] , j, i, f [100];
6 for (i = 0; i <= m; i++)
7 f[i] = 0;
8 for (i = 0; i < n; i++)
9 {
10 j = (a[i] / c) % 10;
11 f[j ]++;
12 }
13 for (i = 1; i <= m; i++)
14 f[i] += f[i – 1];
15 for (i = n -1; i >= 0; i –)
16 {
17 j = (a[i] / c) % 10;
18 b[f[j] -1] = a[i];
19 f[j]–;
20 }
21 for (i = 0; i < n; i++)
22 a[i] = b[i];
23}
24void RadixSort (int a[], int n)
25{
26 int i;
27 int mx = a [0];
28 for (i = 1; i < n; i++)
29 {
30 if (a[i] > mx)
31 mx = a[i];
32 }
33 for (i = 1; mx/i >0; i *=10)
34 CountingSort (a, n, 9, i);
35}
36int main ()

Capitolul 1. Analiza algoritmilor de sortare elementari 26
37{
38 int a[100] , n, i;
39 cout << " Introduceti dimensiunea vectorului : ";
40 cin >> n;
41 cout << " Introduceti elementele vectorului :";
42 for (i = 0; i < n; i++)
43 {
44 cout << "a[" << i << "]=";
45 cin >> a[i];
46 }
47 RadixSort (a, n);
48 cout << " Vectorul sortat este : ";
49 for (i = 0; i < n; i++)
50 cout << a[i] << " ";
51 return 0;
52}
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 semin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
Tehnica diviz arii (divide-et-Impera) este o una dintre cele mai cunoscute
metode de proiectare a algoritmilor. Aceast a strategie de proiectare presupune
^ mpart irea problemei ^ n cel put in dou a subprobleme independente, asem an atoare cu
problema init ial a, dar de dimensiuni mai mici. Problemele sunt rezolvate, de regul a,
recursiv, urm^ and ca rezultatele s a e combinate pentru a obt ine solut ia problemei
init iale.
Pentru a rezolva problema prin tehnica diviz arii trebuie parcur si trei pa si:
^ mpart irea problemei init iale ^ n dou a sau mai multe subprobleme independete,
de aproximativ aceea si dimensiune ( divide )
rezolvarea subproblemelor ^ n mod recursiv; dac a acestea au dimensiuni mici,
atunci se rezolv a direct ( impera sauconquer )
combinarea rezultatelor astfel ^ nc^ at s a obt iem solut ia problemei init iale.
Paradigma Divide et Imperea st a la baza proiect arii de algoritmi ecient i de sor-
tare, cum ar : sortarea prin interclasare ( MergeSort )  si sortarea rapid a ( QuickSort ).
Analiza ecient ei algoritmilor bazat i pe tehnica diviz arii. Vom enunt a un
rezultat important pentru analiza complexit at i algoritmilor elaborat i folosind 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 problemei init iale ^ n
27

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 28
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
<
:T;
0dac 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 )
Algoritmul a fost descris de John von Neumann ^ n 1945, av^ and la baz a tehnica
Divide et Impera. Pa sii algoritmului sunt: se ^ mparte tabloul de elemente ^ 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
^ nc^ at s a rezulte  sirul init ial sortat. Subsecvent ele 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 in C++ este:
1# include <iostream >
2using namespace std;
3void Merge (int a[], int s, int m, int d)
4{
5 int i, j, k, temp [50];
6 i = s;
7 k = 0;
8 j = m + 1;

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

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 30
47 MergeSort (a, m + 1, d);
48 Merge (a, s, m, d);
49 }
50}
51int main ()
52{
53 int a[100] , n, i;
54 cout << " Introduceti dimensiunea vectorul pe care doriti
sa -l sortati : ";
55 cin >> n;
56 for (i = 0; i < n; i++)
57 {
58 cout << " Introduceti elementele vectorului " << i + 1
<< ": ";
59 cin >> a[i];
60 }
61 MergeSort (a, 0, n – 1);
62 cout << " Vectorul sortat este : ";
63 for (i = 0; i < n; i++)
64 cout << a[i]<<" ";
65 return 0;
66}
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)
 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 obt inem: (5,
7, 17, 18).
Pasul 7. Am obt inut 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 corectitudinii. Pornim de la stabilirea precondit iilor  si a postcondit ii-
lor: Pin=fa[s : : : m ] este cresc ator  si a[m+ 1: : : d] este cresc atorg, iar Pout=

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 31
fa[s : : : d ] 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 considera proprietatea in-
variant a I=ftemp [k]a[l]; l=i; : : : ; m  sitemp [k]a[l]; lj; : : : ; dgpentru prima
strunctur a while . Astfel spus, elementul pe care tocmai l-am copiat ^ n temp [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^ n avor  transferate^ n temp [k+1]; : : : ; temp [ds],
pentru c a vectorul temp este completat de la st^ anga la dreapta. 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
laslad.
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 slam
 si de la mlad, sunt deja sortate. Deci, a[i]a[l]; l=i+ 1; : : : ; m  sia[j]a[l]; l=
j+ 1; : : : ; d . 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; : : : ; d . Asem anator este  si pentru cel alalt caz.
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.
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 efectuate de c atre algoritmul de sor-
tare 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 necesit a mult timp, adic a T(1) = 0. Pentru n > 1 se parcurg
pa sii corespunz atori metodei Divide et Impera .^In pasul de divizare , se calculeaz a
doar mijlocul subvectorului, calcul care nu are nevoie de operat ii de comparat ie sau
transfere. La pasul impera rezolv am recursiv dou a subprobleme, ecare de dimen-
siune n=2. Deci acest pas contribuie cu 2 T(n=2) la timpul de execut ie. La pasul ^ n
care se combin a solut iile subproblemelor are loc, de fapt, interclasarea subvectorilor

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 32
ordonat i. Num arul maxim de operat ii de baz a efectuate ^ n algoritmul de intercla-
sare este de ordinul ( n). Deci, Tmerge2(n) ^ n cel mai defavorabil caz. Obt inem
urm atoarea relat ie de recurent  a:
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 se poate aplica cazul
doi din Teorema master  si se obt ine c a T(n)2(nlogn), ^ n cel mai defavorabil
caz. Deci, putem spune c a T(n)2(nlogn). Aceast a metod a necesit a un spat iu de
memorie suplimentar ^ n etapa de interclasare.
2.2 Sortarea rapid a ( QuickSort )
Acest algoritm este unul dintre cei mai utilizat i algoritmi de sortare, ind un
algoritm ce are la baz a metoda Divide et Impera  si metoda interschimb arii. A fost
dezvoltat de C.A.R. Hoare ^ n 1960. Dac a ^ n algoritmului de interclasare, diviza-
rea vectorului ^ n dou a subsecvent e se face t in^ and cont de pozit ia elementelor, ^ n
algoritmul de sortare rapid a se t ine cont  si de valoarea acestuia. Algortimul Mer-
geSort are nevoie de o procedur a de interclasare tocmai pentru c a ^ n ecare dintre
cele dou a subsecvent e se g asesc  si elemente de valoare mic a  si elemente de valoare
mare. Algoritmul de sortare rapid a se bazeaz a pe partit ionarea  sirului init ial. Ast-
fel, av^ and tabloul a, partit ionarea presupune o rearanjare a elementelor vectorului
init ial astfel ^ nc^ at toate elementele a
ate la st^ anga unui element a[s] sunt mai mici
sau egale cu a[s], iar toate elementele a
ate la dreapta a[s] sunt mai mari sau egale cu
acesta. Deci, a[0]; : : : ; a [s1]a[s]  sia[s+ 1]; : : : ; a [n1]a[s]. Elementul a[s] se
nume ste pivot . Astfel, dup a ce se realizeaz a o partit ionare, elementul a[s] se va a
a
pe pozit ia nal a ^ n  sirul sortat. Se continu a apoi recursiv, folosind aceea si tehnic a de
sortare, cu cei doi subvectori a
at i la st^ anga  si la dreapta elementului a[s] indepen-
dent. S a remarc am c a, ^ n cazul algoritmului MergeSort , divizarea problemei init iale
^ n dou a subprobleme este imediat a  si ^ ntregul efort const a ^ n combinarea solut iilor
prin interclasarea celor dou a  siruri sortate, pe c^ and, ^ n cazul algoritmului QuickSort ,
dicultatea st a ^ n pasul de divizare, iar etapa de combinare a solut iilor nu necesit a
niciun efort. Astfel, partit ionarea este prelucrarea cea mai important a a algoritmului,
deoarece aceasta presupune identicarea pivotului , adic a a acelui element a[s] pentru
carea[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 creeze unul. Sunt mai multe strategii de alegere a pivotului. Astfel, vom

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 33
selecta primul element al subtabloului drept pivot, deci pivot =a[stang ]  si presupu-
nem c a algoritmul de partit ionare este apelat pentru subtabloul a[stang : : : drept ].
Se parcurge subtabloul pornind din ambele capete ale sale  si se compar a elementele
cu pivotul. Parcurgerea de la st^ anga la dreapta se realizeaz a de la al doilea element.
Pentru aceasta vom folosi un indice i. Din moment ce dorim ca elementele mai mici
dec^ at pivotul s a e rearanjate ^ n partea st^ anga a subtabloului, parcurgerea sare peste
elementele mai mici dec^ at pivotul  si se opret e la primul element mai mare sau egal
cu acesta, a[i]. Parcurgerea de la dreapta la st^ anga ^ ncepe cu ultimul element al
subtabloului, folosind un indice j. Din moment ce dorim ca elementele mai mari
dec^ at pivotul s a e aranjate ^ n partea dreapt a a subtabloului, 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 ce ambele parcurgeri se opresc, sunt
trei situat ii ce pot s a apar a: dac a i < j , atunci se interschimb a elementele a[i]  si
a[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 sub siruri sunt sucient de mici, adic a se reduce la un singur element.
QuickSort implementat in C++ este:
1# include < iostream >
2using namespace std;
3int partition (int a[], int stang , int drept )
4{
5 int i, j, pivot , aux;
6 i = stang ;
7 j = drept + 1;
8 pivot = a[ stang ];
9 while ( true )
10 {
11 do {
12 i = i + 1;
13 } while (i <= drept && a[i] < pivot );
14 do {
15 j = j – 1;
16 } while (j >= stang && a[j]> pivot );
17 if (i < j)

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 34
18 {
19 aux = a[i];
20 a[i] = a[j];
21 a[j] = aux;
22 }
23 else {
24 aux = a[ stang ];
25 a[ stang ] = a[j];
26 a[j] = aux;
27 return j;
28 }
29 }
30}
31void QuickSort (int a[], int stang , int drept )
32{
33 int s;
34 if ( stang < drept )
35 {
36 s = partition (a, stang , drept );
37 QuickSort (a, stang , s – 1);
38 QuickSort (a, s + 1, drept );
39 }
40}
41int main ()
42{
43 int a[100] , n, i;
44 cout << " Introduceti dimensiunea vectorul pe care doriti
sa -l sortati :";
45 cin >> n;
46 for (i = 0; i < n; i++)
47 {
48 cout << " Introduceti elementele vectorului " << i + 1
<< ":";
49 cin >> a[i];
50 }
51 QuickSort (a, 0, n – 1);
52 cout << " Vectorul sortat este : ";
53 for (i = 0; i < n; i++)

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 35
54 cout << a[i] << " ";
55 return 0;
56}
De exemplu:
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-
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.

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 36
4 5 (pivot =3)
i j
4 5
j i
Se returneaz a pozit ia de interschimbare, s=j= 2. Apoi se apeleaz a recur-
siv algoritmul de sortare pentru sub sirurile: a[2: : :1] sia[3: : :3]. Primul caz este
corespunz 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 partit ionare,
identic am precondit ia  si postcondit ia: Pin=fstang < dreptg, iarPout=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 k=
stang; : : : ; i1;iara[k]pivot pentru k=j+ 1; : : : ; dreptg. Cum precondit ia
i < j , proprietatea 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.
Pentru 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. Presu-
punem 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 pozit ia de partit ionare s. Acum vom verica c a oricare ar  dou a
elemente de indici i sijsunt ^ n ordinea corect a: dac a i < js1 sau s+ 1
i < j; atunci a[i]a[j], conform ipotezei inductive; dac a i < s < j , atunci

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 37
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 interschimb arilor. Pentru un vector de dimensiune nnum arul de
comparat ii este n+ 1, dac a i > j ,  sin, dac a i=j.
Ecient a algoritmului QuickSort depinde de dimensiunile celor dou a sub siruri
obt inute prin partit ionare. Cu c^ at cele dou a dimensiuni sunt mai apropiate, cu at^ at
se realizeaz a mai put ine comparat ii. Astfel, cazul cel mai favorabil se obt ine c^ and
toate partit ion arile se realizeaz a^ n mijlocul sub sirurilor corespunz atoare ( partit ion ari
echilibrate ).^In acest caz, num arul de comparat ii satisface recurent a
Tn(n) =8
<
:0 ;dac a n= 1
2T(n=2) +n ; dac a n >1:
Conform Teoremei master, T(n)2(nlogn), ^ n cel mai favorabil caz, deci algoritmul
are clasa de complexitate
( nlogn).
Cazul cel mai defavorabil se obt ine c^ and toate partit ion arile sunt dezechilibrate :
unul dintre sub siruri este vid, iar cel alalt are dimensiunea cu 1 mai mic a dec^ at dimen-
siunea sub sirului pentru care este apelat algoritmul de partit ionare. Aceast a situat ie
se ^ nt^ alne ste c^ and algoritmul de sortare este apelat pentru  siruri deja ordonate, spre
deosebire de algoritmii de sortare elementari. ^Intr-adev ar, dac a folosim drept pivot
a[0]  si vectorul este strict cresc ator, parcurgerea de la st^ anga la dreapta se opre ste
pea[1], ^ n timp ce parcurgerea de la dreapta la st^ anga se opre ste pe a[0], return^ and
pozit ia de partit ionare 0. Deci, dup a ce efectueaz a n+ 1 comparat ii pentru a realiza
aceast a partit ionare  si interschimb a pivotul cu el ^ nsu si, continu a cu sortarea  sirului
deja ordonat strict cresc ator a[1: : : n1]. Algoritmul se opre ste dup a ce proceseaz a
 si ultimul sub sir, a[n2: : : n1]. Num arul total de comparat ii efectuate este egal
cu
T(n) = (n+ 1) + n+


+ 3 =(n+ 1)( n+ 2)
232(n2):
Deci, ^ n cazul cel mai defavorabil, algoritmul are o complexitate p atratic a  si atunci
T(n)2O(n2).
Vom analiza  si cazul mediu, plec^ and de la ipoteza c a  sirul este unul aleator. Pre-
supunem c a partit ionarea se poate realiza ^ n orice pozit ie scu aceea si probabilitate
(= 1=n), 0sn1,  si c a se realizeaz a n+ 1 comparat ii pentru a obt ine o
partit ionare. Num arul de comparat ii, ^ n cazul ^ n care pozit ia pivotului este s, satis-
faceTs(n) =T(s) +T(n1s) +n+ 1, pentru c a dup a partit ionare, cele dou a
sub siruri rezultate au s, respectiv, n1s, elemente. Prin urmare, timpul de

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 38
execut ie satisface
Tmediu (n) =8
>><
>>:1
nn1X
s=0Ts(n) ;dac a n1
0 ;dac a n= 0 sau n= 1:
Obt inem:
Tmediu (n) =1
nn1X
s=0[(n+ 1) + Tmediu (s) +Tmediu (n1s)] =
= (n+ 1) +1
nn1X
s=0[Tmediu (s) +Tmediu (n1s)]
 si deci
Tmediu (n) = (n+ 1) +2
nn1X
s=0[Tmediu (s); n > 1
nTmediu (n) = 2n1X
s=0Tmediu (s) +n(n+ 1); n > 1:
Deci este adev arat a  si relat ia urm atoare
(n1)Tmediu (n1) = 2n2X
s=0Tmediu (s) +n(n1):
Sc az^ and ultimele dou a relat ii se obt ine formula de recurent  a pentru T(n):
Tmediu (n) =n+ 1
nTmediu (n1) + 2 ; n > 1:
Astfel, prin subtitut ie invers a obt inem:
Tmediu (n) =n+ 1
nTmediu (n1) + 2
Tmediu (n1) =n
n1Tmediu (n2) + 2
Tmediu (n2) =n1
n2Tmediu (n3) + 2
…
Tmediu (2) =3
2Tmediu (1) + 2
Tmediu (1) = 0 :

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera 39
^Inmult im a doua relat ie cun+1
n, a treia cun+1
n1 s.a.m.d., penultima relat ie cun+1
3,
iar ultima cun+1
2, apoi sum am relat iile:
Tmediu (n) = 2( n+ 1)1
n+1
n1+


+1
3
+ 2 = 2( n+ 1)nX
i=31
i+ 2:
Aproxim am sumaPn
i=31
iRn
31
xdx= lnn
3 si atunci Tmediu (n) = 2( n+ 1) lnn
3+ 2
2nlnn1:38nlog2n. Rezultatul obt inut sugereaz a c a, ^ n cazul mediu, algoritmul
de sortare efectueaz a cu aproximativ 38% mai multe comparat ii dec^ at ^ n cazul cel
mai favorabil.
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 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  si cele mai mari ^ n cea de-a treia parte).

Capitolul 3
Aplicat ii practice
Aplicat ia 1. La sf^ ar situl lunii iunie, la proba de 100 m vitez a din cadrul unei
competit ii nat ionale de atletism, s-au ^ nscris 81 de participante de sex feminin, re-
prezent^ and ecare cate un club sportiv. ^In cadrul acestei competit ii se vor desf a sura
trei etape.
Prima etapa:
Se vor crea nou a grupe alc atuite din c^ ate nou a sportive ce vor intra ^ n competit ie ^ n
cadrul ec arei grupe. Primele trei ^ n clasament, ^ n funct ie de timpul cel mai mic de
sosire, vor trece ^ n etapa a doua.
A doua etap a:
Dup a select ia desf a surat a ^ n prima etap a, au mai r amas doar 27 de sportive. Astfel
se vor forma trei grupe de c^ ate nou a sportive. Primele trei ^ n clasament din ecare
grup a vor trece ^ n etapa a treia.
Etapa nal a:
Aceast a etap a este decisiv a, deoarece ^ n nal, se va preciza cine se va calica la
Campionatul Internat ional de Atletism. Se va realiza doar o singur a grup a cu nou a
sportive care vor intra ^ n competit ie. Dup a a
area clasamentului, doar primele trei
se vor calica.
Aplicat ia va returna cele trei c^ a stig atoare care vor reprezenta t ara.
Solut ie: Presupunem c a timpii obt inut i de sportive sunt variabile aleatoare ce ur-
meaz a o repartit ie uniform a. ^In C++, pentru generarea de numere pseudoaleatoare
ce au o distribut ie uniform a continu a pe intervalul [ a; b), aveam urm atoarea posibi-
litate: mai ^ nt^ ai, set am starea init ial a a generatorului
1default_random_engine generator (( unsigned int) time ( NULL ));
Funct ia time(NULL) (denit a ^ n ctime ) returneaz a timpul scurs ^ n secunde de la
1 ianuarie 1970, ora 00:00:00. Se utilizeaz a valoarea returnat a de aceast a funct ie,
40

Aplicat ii practice 41
pentru a init ializa generatorul de ecare dat a cu alt a valoare,  si deci, pentru a genera
numere aleatoare diferite, la apelul repetat al funct iei random de mai jos.
Funct ia random , denit a mai jos, genereaz un num ar pseudoaleator uniform dis-
tribuit din intervalul [ a; b):
1double random ( double a, double b) {
2uniform_real_distribution < double > dist (a, b);
3return dist ( generator );
4}
Astfel, pentru aplicat ia noastr a vom genera aleator timpii obt inut i de sportive. Fi-
ecare grup a este format a cu c^ ate nou a sportive care reprezint a ecare cate un club,
deci acestea vor concura ^ ntre ele ^ n cadrul grupei din care vor  repartizate  si nu-
mele fetelor vor  citite dintr-un  sier text sportive.txt . Astfel, pentru ecare grup a
^ n parte se va realiza un clasament ^ n funct ie de timpul de sosire la linia de nish.
Acest timp se va genera aleator uniform continuu cu parametrii de 10.7 secunde  si
11.7 secunde, deci vom apela funct ia random explicat a mai sus cu parametrii co-
respunz atori. Clasamentul se realizeaz a folosind algoritmul de sortare prin insert ie
direct a.
Dup a realizarea clasamentului pentru ecare grup a, se vor alege primele trei
fete din ecare grup a pentru a continua ^ n etapa a doua. Vom scrie numele fetelor
calicate ^ ntr-un  sier text calicare etapa1.txt .
^In etapa a doua au r amas 27 de sportive. Deci se vor ^ mp at i ^ n trei grupe. Dup a
realizarea grupelor, sportivele vor intra ^ n competit ie ^ n cadrul grupei din care face
parte  si numele fetelor vor  citite din  sierul text calicare etapa1.txt . Apoi, se va
realiza din nou un clasament, dup a timpul de sosire cu parametrii de 10.5 secunde
 si 11.5 secunde, folosind algoritmul de sortare prin interschimbare. Primele trei
persoane din clasament din ecare grup a merge ^ n etapa a treia, adic a cea nal a.
Vom scrie numele fetelor calicate ^ ntr-un  sier text calicare etapa2.txt .
Acum sportivele r amase vor forma o singur a grup a  si vor concura,iar numele fete-
lor vor  citite din  sirul text anterior. Dup a a
area clasamentului (am folosit algo-
ritmul de sortare prin selet ie) cu parametrii de 10.3 secunde  si 11.3 secunde, primele
trei sportive se vor calica la Campionatul Internat ional de Atletism  si vor reprezenta
t ara. Rezultatele obt inute le vom scrie ^ ntr-un  sier text calicare campionat.txt .
1# include < iostream >
2# include <random >
3# include <ctime >
4# include <fstream >
5using namespace std;

Aplicat ii practice 42
6struct sportiva {
7 char nume [50];
8 double a;
9};
10sportiva p [100];
11default_random_engine generator (( unsigned int) time ( NULL ));
12double random ( double a, double b)
13{
14 uniform_real_distribution < double > dist (a, b);//
distributia uniform continua
15 return dist ( generator );
16}
17void BubbleSort ( sportiva p[], int n)
18{
19 int i, j;
20 sportiva aux;
21 for (i = n – 1; i >= 0; i –)
22 {
23 for (j = 0; j <= i – 1; j++)
24 {
25 if (p[j].a > p[j + 1].a)
26 {
27 aux = p[j];
28 p[j] = p[j + 1];
29 p[j + 1] = aux;
30 }
31 }
32 }
33}
34void InsertSort ( sportiva p[], int n)
35{
36 sportiva aux;
37 int j;
38 for (int i = 0; i < n; i++)
39 {
40 j = i – 1;
41 aux = p[i];
42 while (j >= 0 && aux.a < p[j].a)

Aplicat ii practice 43
43 {
44 p[j + 1] = p[j];
45 j –;
46 }
47 p[j + 1] = aux;
48 }
49}
50void SelectSort ( sportiva p[], int n)
51{
52 int i, j, m;
53 sportiva aux;
54 for (i = 0; i < n – 1; i++)
55 {
56 m = i;
57 for (j = i + 1; j < n; j++)
58 {
59 if (p[m].a > p[j].a)
60 m = j;
61 }
62 if (m != i)
63 {
64 aux = p[m];
65 p[m] = p[i];
66 p[i] = aux;
67 }
68 }
69}
70ifstream in(" sportive .txt");
71ifstream in1(" calificare_etapa1 .txt");
72ifstream in2(" calificare_etapa2 .txt");
73ofstream out(" calificare_etapa1 .txt");
74ofstream out1 (" calificare_etapa2 .txt");
75ofstream out2 (" calificare_campionat .txt");
76void fisier ()
77{
78 for(int i = 0; i <= 80; i++)
79 {
80 if (! in)

Aplicat ii practice 44
81 {
82 cerr << " File can 't be opened ! " << endl ;
83 system (" PAUSE ");
84 }
85 in >> p[i]. nume ;
86 }
87}
88void Etapa1 () {
89 fisier ();
90 cout << " Etapa I \n\n\n";
91 for (int i = 0; i <= 8; i++) {
92 cout << " GRUPA " << i+1 << " " << endl ;
93 cout << endl ;
94 cout << endl ;
95 cout << " Intra in competitie fetele din grupa " << i+1
<< endl ;
96 cout << endl ;
97 for (int j = 0; j <= 8; j++) {
98 p[j+9*i].a = random (10.7 , 11.7) ;
99 cout << p[j+9* i]. nume << " are timpul : " << " " << p
[j+9*i].a << endl ;
100 }
101 cout << endl ;
102 sportiva v [9];
103 for (int k = 0; k <= 8; k++)
104 v[k] = p[k + 9*i];
105 InsertSort (v, 9);
106 cout << "Top 3 rezultate dupa competitie din grupa "
<< i+1 << " sunt :" << endl ;
107 cout << v [0]. nume << " are timpul : " << " " << v [0]. a
<< endl ;
108 cout << v [1]. nume << " are timpul : " << " " << v [1]. a
<< endl ;
109 cout << v [2]. nume << " are timpul : " << " " << v [2]. a
<< endl ;
110 out << v [0]. nume << endl ;
111 out << v [1]. nume << endl ;
112 out << v [2]. nume << endl ;

Aplicat ii practice 45
113 cout << endl ;
114 cout << endl ;
115 }
116}
117void Etapa2 () {
118 Etapa1 ();
119 cout << " Etapa II \n\n\n"
;
120 for (int k = 0; k < 3; k++) {
121 cout << " GRUPA " << k+1 << " " << endl ;
122 cout << endl ;
123 cout << endl ;
124 cout << " Intra in competitie fetele din grupa " << k+1
<< endl ;
125 cout << endl ;
126 for (int m = 0; m <= 8; m++) {
127 in1 >> p[m + 9 * k]. nume ;
128 p[m+9*k].a = random (10.5 , 11.5) ;
129 cout << p[m + 9 * k]. nume << " are timpul : " << " "
<< p[m + 9 * k].a << endl ;
130 }
131 cout << endl ;
132 sportiva v [9];
133 for (int m = 0; m <= 8; m++)
134 v[m] = p[m + 9 * k];
135 BubbleSort (v, 9);
136 cout << "Top 3 rezultate dupa competitie din grupa "
<< k+1 << " sunt :" << endl ;
137 cout << v [0]. nume << " are timpul : " << " " << v [0]. a
<< endl ;
138 cout << v [1]. nume << " are timpul : " << " " << v [1]. a
<< endl ;
139 cout << v [2]. nume << " are timpul : " << " " << v [2]. a
<< endl ;
140 out1 << v [0]. nume << endl ;
141 out1 << v [1]. nume << endl ;
142 out1 << v [2]. nume << endl ;
143 cout << endl ;

Aplicat ii practice 46
144 cout << endl ;
145 }
146}
147void Etapa3 () {
148 Etapa2 ();
149 cout << " Etapa III \n\n\n";
150 int l = 1;
151 cout << " Etapa finala " << endl ;
152 cout << endl ;
153 cout << endl ;
154 cout << " Intra in competitie fetele : " << endl ;
155 cout << endl ;
156 for (int m = 0; m <= 8; m++) {
157 in2 >> p[m]. nume ;
158 p[m].a = random (10.3 , 11.3) ;
159 cout << p[m]. nume << " are timpul : " << " " << p[m].a
<< endl ;
160 }
161 cout << endl ;
162 SelectSort (p, 9);
163 cout << " Sportivele care merg la campionatul
international sunt :\n";
164 cout << p [0]. nume << " are timpul : " << " " << p [0]. a <<
endl ;
165 cout << p [1]. nume << " are timpul : " << " " << p [1]. a <<
endl ;
166 cout << p [2]. nume << " are timpul : " << " " << p [2]. a <<
endl ;
167 out2 << p [0]. nume <<" " << p [0]. a << endl ;
168 out2 << p [1]. nume << " " << p [1]. a << endl ;
169 out2 << p [2]. nume << " " << p [2]. a << endl ;
170 cout << endl ;
171 cout << endl ;
172}
173int main () {
174 cout << " ––– CAMPIONATUL NATIONAL DE ATLETISM 100 m
VITEZA FEMININ –––––-" << endl ;
175 cout << endl ; cout << endl ;

Aplicat ii practice 47
176 Etapa3 ();
177 in. close ();
178 in1. close ();
179 in2. close ();
180 out. close ();
181 out1 . close ();
182 out2 . close ();
183 return 0;
184}
Aplicat ia 2. Cofet aria Charlotte are doar de un singur angajat  si trebuie s a satis-
fac a comenzile a nclient i care ^  si aleg din meniul pus la dispozit ie c^ ate un desert.
Cunosc^ and timpul de servire necesar ec arui client, vom stabili o ordine de servire
astfel ^ nc^ at timpul de a steptare s a e minim.
Solut ie: Timpul total de a steptare este suma timpilor de a steptare pentru ecare
client ^ n parte. Dac a not am cu wi, timpul de a steptare pentru cientul i; i=1; n
 si timpul total de a steptare cu T, atunci T=nX
i=1wi. A minimiza timpul total de
a steptare este acela si lucru cu a minimiza timpul mediu de a steptare, care este T=n.
Vom identica client ii prin numere de la 1 la n. Problema poate  rezolvat a
folosind tehnica Backtracking, gener^ and astfel toate solut iile posibile  si aleg^ and apoi
pe cea optim a, adic a pe cea care minimizeaz a timpul total de a steptare. De fapt,
prin aceast a metod a se vor generara toate permut arile mult imii f1;2;3; : : : ; ng si,
pentru ecare solut ie ^ n parte, se va calcula timpul total de a steptare. Se va alege
solut ia pentru care Teste minim.
Tehnica Greedy este clar mai efcient a din punctul de vedere al timpului de
execut ie  si al simplit at ii. Algoritmul bazat pe aceast a tehnic a este: la ecare pas
se va selecta clientul cu timpul minim de servire din mult imea de client i r amas a.
^In scopul obt inerii solut iei optime, vom sorta cresc ator  sirul client ilor folosind al-
goritmul de sortare prin interclasare dup a timpul de servire a acestora. Se poate
demonstra c a acest algoritm conduce ^ ntotdeauna la solut ia optim a.
Un client este caracterizat prin num arul s au de ordine  si prin timpul de ser-
vire. Datele de intrare vor  citite dintr-un  sier text evidenta.txt . Pe prima linie
a  sierului se a
 a num arul nde client i. Linia a doua a  sierului cont ine nnumere
naturale, separate prin spat ii, reprezent^ and timpii de servire a client ilor, ti; i=1; n.
Datele de ie sire vor  scrise ^ n  sierul text timpi.txt .
1# include < iostream >
2# include < fstream >

Aplicat ii practice 48
3# define dim 100
4using namespace std;
5struct Client {
6//t= timpuk de servire ; nr= numarul de oridne
7 int t, nr;
8};
9ifstream in(" evidenta .txt");
10ofstream out(" timpi .txt");
11void Merge ( Client a[], int s, int m, int d)
12{
13 int i, j, k;
14 Client temp [dim ];
15 i = s;
16 k = 0;
17 j = m + 1;
18 while (i <= m && j <= d)
19 {
20 if (a[i].t < a[j].t)
21 {
22 temp [k] = a[i];
23 i++;
24 }
25 else
26 {
27 temp [k] = a[j];
28 j++;
29 }
30 k++;
31 }
32 while (i <= m)
33 {
34 temp [k] = a[i];
35 k++;
36 i++;
37 }
38 while (j <= d)
39 {
40 temp [k] = a[j];

Aplicat ii practice 49
41 k++;
42 j++;
43 }
44 for (k = 0; k <= d – s; k++)
45 {
46 a[s + k] = temp [k];
47 }
48}
49void MergeSort ( Client a[], int s, int d)
50{
51 int m;
52 if (s < d)
53 {
54 m = (s + d) / 2;
55 MergeSort (a, s, m);
56 MergeSort (a, m + 1, d);
57 Merge (a, s, m, d);
58 }
59}
60void timp ( Client c[], int n, ofstream &out )
61{
62// clientii sunt in ordine crescatoare
63// dupa timpii de servire
64 int i, j;
65 int T = 0;
66 for (i = 0; i < n; i++) {
67 out << c[i]. nr << " ";
68 for (j = 0; j <= i; j++)
69 T += c[j].t;
70 }
71 out << endl << " Timpul total de asteptare este " << T <<
endl ;
72}
73int main ()
74{
75 int n;
76 Client c[dim ];
77 if (! in) {

Aplicat ii practice 50
78 cout << " Eroare la deschiderea fisierului ." << endl ;
79 exit (1) ;
80 }
81 in >> n;
82 for (int i = 0; i < n; i++) {
83 in >> c[i].t;
84 c[i]. nr = i + 1;
85 }
86 in. close ();
87 MergeSort (c, 0, n – 1);
88 timp (c, n, out);
89 out. close ();
90 return 0;
91}
Aplicat ia 3. Managerul unui festival de dansuri populare trebuie s a selecteze o
mult ime c^ at mai ampl a de spectacole din cele nposibile ce pot  jucate ^ n singura
sal a pe care o are la dispozit ie. Pentru ecare spectacol i-a fost anunt at intervalul
^ n care se poate desfasura [ si; fi] (sireprezint a ora  si minutul de ^ nceput, iar fiora
 si minutul de nal al spectacolului i). Vom determina un program care s a permit a
spectatorilor vizionarea unui numar c^ at mai mare de spectacole.
Solut ie: Spectacolele vor  identicate prin numere de la 1 la n. Vom sorta specta-
colele cresc ator folosind algoritmul de sortare rapid a dup a momentul de ^ ncheiere a
acestora. Algoritmul greedy va  urm atorul: mai ^ nt^ ai select am spectacolul care se
termin a cel mai devreme. La ecare pas select am primul spectacol disponibil, care
nu se suprapune cu cele deja selectate, deci care ^ ncepe dup a ce se termin a ultimul
spectacol selectat.
Datele de intrare se vor citi dintr-un  sier text spectacol.txt , ^ n care, pe prima
linie, se a
 a num arul de spectacole n. Pe urm atoarele nlinii se vor a
a c^ ate 4 valori:
primele dou a reprezint a ora  si minutul ^ nceperii spectacolului curent, iar ultimele
dou a reprezint a ora  si minutul termin arii spectacolului. Datele de ie sire, numerele
de ordine ale spectacolelor care ^ ndeplinesc restrict iile problemei, vor  af sate ^ n
 sierul text specatacol aranjat.txt , separate prin spat ii.
1# include < iostream >
2# include < fstream >
3# define dim 100
4using namespace std;
5struct Spectacol

Aplicat ii practice 51
6{
7//s= momentul inceperii spectacolului
8//f= momentul incheierii spectacolului
9// nr= numarul curent
10 int s, f, nr;
11};
12int partition ( Spectacol a[], int stang , int drept )
13{
14 int i, j;
15 i = stang ;
16 j = drept + 1;
17 Spectacol pivot , aux;
18 pivot = a[ stang ];
19 while ( true ) {
20 do {
21 i = i + 1;
22 } while (i <= drept && a[i].f < pivot .f);
23 do {
24 j = j – 1;
25 } while (j >= stang && a[j].f > pivot .f);
26 if (i < j) {
27 aux = a[i];
28 a[i] = a[j];
29 a[j] = aux;
30 }
31 else {
32 aux = a[ stang ];
33 a[ stang ] = a[j];
34 a[j] = aux;
35 return j;
36 }
37 }
38}
39void QuickSort ( Spectacol a[], int stang , int drept )
40{
41 int s;
42 if ( stang < drept ) {
43 s = partition (a, stang , drept );

Aplicat ii practice 52
44 QuickSort (a, stang , s – 1);
45 QuickSort (a, s + 1, drept );
46 }
47}
48ifstream in(" spectacol .txt");
49ofstream out(" spectacol_aranjat .txt");
50void programare ( Spectacol a[], int n, ofstream &out )
51{
52// spectacolele sunt in ordine crescatoare dupa momentul
inchidere a acestora
53 out << endl << a [0]. nr << " ";
54//u= indexul ultimului spectacol adaugat in program
55 int i, u = 0;
56 for (i = 1; i < n; i++) {
57 if (a[i].s >= a[u].f) {
58 out << a[i]. nr << " ";
59 u = i;
60 }
61 }
62}
63int main ()
64{
65 int n, h, m;
66 Spectacol a[dim ];
67 if (! in) {
68 cout << " Eroare la deschiderea fisierului ." << endl ;
69 exit (1) ;
70 }
71 in >> n;
72 for (int i = 0; i < n; i++) {
73 a[i]. nr = i + 1;
74 in >> h >> m;// transformam orele in minute
75 a[i].s = h * 60 + m;
76 in >> h >> m;
77 a[i].f = h * 60 + m;
78 }
79 in. close ();
80 QuickSort (a, 0, n -1);

Aplicat ii practice 53
81 programare (a, n, out);
82 out. close ();
83 return 0;
84}

Bibliograe
[1] R. Andonie, I. G^ arbacea, Algoritmi Fundamentali. O perspectiv a C++ , Ed.
Computer Libris Agora, Cluj-Napoca, 1995.
[2] T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introducere ^ n Algoritmi , Ed. Com-
puter Libris Agora, Cluj-Napoca, 2000 (traducere).
[3] D. Lucanu, M. Craus, Proiectarea Algoritmilor , Ed. Polirom, 2008.
[4] C. A. Giumale, Introducere in analiza algoritmilor , Ed. Polirom, 2004 .
[5] A. Levitin, Introduction to The Design and Analysis of Algorithms-3rd Edition ,
Ed. Pearson, 2012.
54