Lucrare de licent a [605839]

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 elementari de sortare 4
1.1 Algoritmi de sortare bazat i pe compararea elementelor . . . . . . . . . 4
1.1.1 Sortarea prin select ie ( SelectSort ) . . . . . . . . . . . . . . . . . 5
1.1.2 Sortarea prin insert ie ( InsertSort ) . . . . . . . . . . . . . . . . 9
1.1.3 Sortarea prin interschimbarea elementelor vecine . . . . . . . . 14
1.2 Algoritmi de sortare bazat i pe num arare . . . . . . . . . . . . . . . . . 20
1.2.1 Sortarea prin num arare ( CountingSort ) . . . . . . . . . . . . . 20
1.2.2 Sortarea pe baza cifrelor ( RadixSort ) . . . . . . . . . . . . . . . 22
2 Analiza algoritmilor de sortare bazat i pe metoda Divide et Impera 24
2.1 Sortarea prin interclasare ( MergeSort ) . . . . . . . . . . . . . . . . . . 25
2.2 Sortarea rapid a ( QuickSort ) . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Aplicat ii practice 36
Bibliograe 52
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 anumit a ordine 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 din punctul de vedere al complexit at ii{timp.
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 mari 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: algoritmi de sortare bazat i
pe compararea elementelor (sortarea prin select ie, sortarea prin insert ie, sortarea
prin interschimbarea elementelor vecine)  si algoritmi de sortare bazat i pe num arare
(sortarea prin num arare ( CountingSort )  si sortarea pe baza cifrelor ( RadixSort )).
Metodele avansate se bazeaz a pe algoritmi ceva mai complicat i, care necesit a
cuno stint e avansate de algoritmic a. Este cazul algoritmilor de sortare bazat i pe
metoda Divide-et-Impera: sortarea prin interclasare ( MergeSort )  si sortarea rapid a
(QuickSort ).
Analiza unui algoritm se refer a la dou a aspecte: vericarea corectitudinii  si ana-
liza complexit at ii acestuia.
^In analiza corectitudinii unui algoritm, se stabilesc mai ^ nt^ ai propriet at ile pe care
trebuie s a le satisfac a datele de intrare pentru ca problema s a aib a sens, numite
precondit ii . Apoi, se precizeaz a condit iile pe care trebuie s a le ^ ndeplineasc a datele
de ie sire, numite postcondit ii . Acestea descriu relat iile care exist a ^ ntre datele de
2

Cuprins 3
intrare  si cele de ie sire conform enunt ului problemei. Spunem c a precondit iile  si
postcondit iile constitue specicat iile problemei . Apoi, trebuie demonstrat c a pornind
de la precondit ii  si execut^ and pa sii algoritmului, postcondit iile vor  satif acute.
Un algoritm este part ial corect , dac a algoritmul se termin a cu rezultatele dorite,
^ n ipoteza c a este nit. Pe de alt a parte, un algoritm este total corect , dac a se termin a
^ n timp nit  si cu rezultatele a steptate.
Structurile care pot pune probleme ^ n ceea ce prive ste corectitudinea unui algo-
ritm sunt cele repetitive. A sadar, de c^ ate ori va ap area o structur a repetitiv a ^ ntr-un
algoritm, va trebui demonstrat a corectitudinea acesteia. Regula structurii repetitive
a lui Hoare spune c a, pentru a demonstra c a o structur a repetitiv a este part ial co-
rect a trebuie pus a ^ n evident  a o proprietate (o armat ie privind starea algoritmului)
care satisface urm atoarele condit ii: precondit iile implic a proprietatea, dac a este ade-
varat a la intrarea ^ n ciclu  si condit ia de continuare este adev arat a, atunci r am^ ane
adev arat a dup a executarea corpului ciclului (proprietate invariant a)  si c^ and condit ia
de continuare devine fals a (la ie sirea din ciclu) proprietatea implic a postcondit iile.
Pentru a demonstra formal c a o structur a repetitiv a se termin a ^ n timp nit, se
va pune ^ n evident  a o funct ie t:N!Nce depinde de num arul curent al iterat iei cu
urm atoarele propriet at i: este strict descresc atoare, c^ at timp condit ia de continuare
este adev arat a, funct ia ia valori mai mari sau egale cu 1, iar atunci c^ and condit ia de
continuare devine fals a, funct ia ia valoarea 0. O astfel de funct ie poart a numele de
funct ie de terminare .
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
(complexitatea-timp). Timpul de execut ie al unui algoritm de rezolvare a unei pro-
bleme depinde de dimensiunea acesteia, deci de volumul datelor de intrare. De
asemenea, timpul de execut ie poate depinde  si de caracteristicile (distribut ia) date-
lor de intrare. A determina timpul de execut ie al unui algoritm ^ nseamn a a num ara
c^ ate operat ii elementare se execut a. A estima timpul de execut ie ^ nseamn a a num ara
doar operat iile considerate de baz a. Atunci c^ and timpul de execut ie depinde  si de
propriet at ile datelor de intrare, acesta ar trebui studiat ^ n cazul cel mai favorabil
(num ar minim de operat ii executate), ^ n cazul cel mai defavorabil (num ar maxim de
operat ii executate)  si, eventual, ^ n cazul mediu (corespunde instant elor aleatoare).
Pentru algoritmii de sortare, operat iile de baz a sunt comparat iile ^ ntre elemente  si
mut arile acestora.
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.

Capitolul 1
Analiza algoritmilor elementari
de sortare
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, permut^ 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 ecient a{
timp.
4

Capitolul 1. Analiza algoritmilor elementari de sortare 5
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
de sortare ce au la baz a aceast a metod a diferit a ^ n funct ie de criteriul de select ie: de
exemplu, a minimului sau a maximului din secvent a corespunz atoare.
Sortarea prin select ia elementului minim
La primul pas al algoritmului, 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:
Apoi, 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++:
1# include <iostream >
2using namespace std;
3
4void SelectSort ( double a[], int n)
5{
6 int i, j, m;
7 double aux ;
8 for (i = 0; i < n – 1; i++)
9 {
10 m = i;
11 for (j = i + 1; j < n; j++)
12 {
13 if (a[m] > a[j])
14 m = j;
15 }
16 if (m != i)
17 {
18 aux = a[m];
19 a[m] = a[i];
20 a[i] = aux;
21 }
22 }
23}

Capitolul 1. Analiza algoritmilor elementari de sortare 6
24
25int main ()
26{
27 double a [20];
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 SelectSort (a, n);
38 cout << " Dupa sortarea prin selectia minimului , vectorul
este : ";
39 for (i = 0; i < n; i++)
40 cout << a[i] << " ";
41 cout << endl ;
42 return 0;
43}
Exemplu. Consider am urm atorul  sir pe care ne propunem s a-l sort am cresc ator
folosind metoda prezentat a:
a[ ] =f10;91;2;6;11;56;23;15;19;0g.
Pasul 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.
Pasul 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.
Pasul 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.
Pasul 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.
Pasul 5: Se determin a indicele elementului minim din sub sirul a[4: : :9],m= 4,

Capitolul 1. Analiza algoritmilor elementari de sortare 7
dar nu se realizeaz a nicio interschimbare deoarece a[4] coincide cu minimul sub sirului.
Pasul 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.
Pasul 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.
Pasul 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.
Pasul 9: Se determin a indicele elementului minim din sub sirul a[8: : :9],m= 8
 si nu se realizeaz a nicio interschimbare deoarece 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 I1este 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,

Capitolul 1. Analiza algoritmilor elementari de sortare 8
iar pentru ciclul interior, t(k) =njk. Deci, dup a un num ar nit de iterat ii condit iile
de continuare 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.
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 ia elementului maxim
Aceast a metod a este similar a cu sortarea prin select ia elementului minim, doar
c a acum vom determina elementul maxim al tabloului, deci indicele Mpentru 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.

Capitolul 1. Analiza algoritmilor elementari de sortare 9
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[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.
Algoritmul de sortare prin insert ie direct a implementat ^ n C++:
1 # include <iostream >
2 using namespace std;
3
4 void InsertSort ( double a[], int n)
5 {
6 int i, j;
7 double aux ;
8 for (i = 1; i < n; i++)
9 {
10 j = i – 1;
11 aux=a[i];
12 while (j >= 0 && aux < a[j])
13 {
14 a[j +1]= a[j];
15 j –;
16 }
17 a[j +1]= aux;
18 }
19 }
Exemplu. Presupunem c a vrem s a sort am  sirul:
a[ ] =f20;7;3;5;6;2;11;10g.
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. ^In exemplul nostru le vom alege ^ n ordinea 7, 3, 5,
etc.

Capitolul 1. Analiza algoritmilor elementari de sortare 10
Pasul 1. Vom ^ ncepe cu elementul a[1] = 7. Vrem s a ^ l inser am ^ n lista de
elemente sortate astfel ^ nc^ at 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
variabilei 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 ^ l 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 dec^ at el  si toate numerele de la st^ anga lui sunt mai
mici dec^ at 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
este invariant 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:

Capitolul 1. Analiza algoritmilor elementari de sortare 11
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, dac a
aux < a [j], din a[j+ 1] = a[j] rezult a c a aux < a [j] =a[j+ 1]: : :a[i]. Dup a
execut ia prelucr arii j=j1; a[0]a[1]: : :a[j]  siaux < a [j+ 1] = a[j+ 2]
: : :a[i]. Deci, I2este 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 iile, se obt ine o
margine 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):

Capitolul 1. Analiza algoritmilor elementari de sortare 12
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 de sortare este o extindere 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. 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 anumite alegeri ale secvent ei de increment i se pot obt ine al-
goritmi 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; : : : :
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 ecient 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

Capitolul 1. Analiza algoritmilor elementari de sortare 13
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 ^ n
C++:
1 # include <iostream >
2 using namespace std;
3
4 void ShellSort ( double a[], int n)
5 {
6 int i, j, h;
7 double aux ;
8 h = 1;
9 while (h < n/3)
10 {
11 h=3 * h + 1; // sirul de incrementi sugerat de Knuth
12 }
13 while (h >= 1)
14 {
15 for(i = h; i < n – 1; i++)
16 {
17 aux = a[j];
18 j = i;
19 while (j >= h && a[j-h] > aux)
20 {
21 a[j] = a[j-h];
22 j = j – h;
23 }
24 a[j] = aux;
25 }
26 h = h/3;
27 }
28 }
Exemplu. Consider am urm atorul  sir:
11, 23, 17, 46, 35, 49, 8, 66, 20, 52, 6, 21, 44, 32, 57.

Capitolul 1. Analiza algoritmilor elementari de sortare 14
Vom folosi algoritmul de sortare prin mic sorarea incrementului folosind secvent a
de increment i 7, 4, 1.
Pasul 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,f44, 49g,f8, 32g.
Noul tablou este:
11, 20, 17, 6, 21, 44, 8, 57, 23, 52, 46, 35, 49, 32, 66.
Pasul 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.
Pasul 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
A.BubbleSort
Este una dintre cele mai simple metode de sortare, ^ ns a inecient a pentru ta-
blouri 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 ce are 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, deci
trebuie continuat p^ an a c^ and nu se mai efectueaz a interschimb ari.
Algoritmul BubbleSort implementat ^ n C++ :
1 # include <iostream >
2 using namespace std;
3
4 void BubbleSort ( double a[], int n)
5 {
6 int i, j;

Capitolul 1. Analiza algoritmilor elementari de sortare 15
7 double aux ;
8 for (i = n – 1; i >= 0; i –)
9 {
10 for(j = 0; j <= i -1; j++)
11 {
12 if(a[j] > a[j +1])
13 {
14 aux = a[j];
15 a[j] = a[j +1];
16 a[j+1] = aux;
17 }
18 }
19 }
20 }
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
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

Capitolul 1. Analiza algoritmilor elementari de sortare 16
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]. Pre-
supunem 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 proprie-
tatea este adev arat a. A sadar, proprietatea I1r 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.
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

Capitolul 1. Analiza algoritmilor elementari de sortare 17
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++:
1 # include <iostream >
2 using namespace std;
3
4 void BubbleSort2 ( double a[], int n)
5 {
6 int i, m;
7 bool schimb ;
8 double aux ;
9 m = n;
10 do
11 {
12 schimb = false ;
13 for(i = 0; i <= m -2; i++)
14 {
15 if(a[i] > a[i +1])
16 {
17 aux = a[i];
18 a[i] = a[i +1];

Capitolul 1. Analiza algoritmilor elementari de sortare 18
19 a[i+1] = aux;
20 schimb = true ;
21 }
22 }
23 m = m -1;
24 } while ( schimb != false );
25 }
^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).
B. ShakerSort
Modic^ and algoritmul de sortare prin interschimbarea elementelor vecine, sort am
elementele unui tablou, astfel ^ nc^ at 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++:
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;

Capitolul 1. Analiza algoritmilor elementari de sortare 19
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];
33 a[i – 1] = aux;
34 t = i;
35 }
36 }
37 s = t;
38 }
39 } while (t != 0 && s != d);
40}
Exemplu. Fie urm atorul  sir:
6;2;5;3;9;1;3.
Pasul 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 dec^ at 9, deci nu se realizeaz a interschimb ari.
2 5 3 6 9!1 3
2 5 3 6 1 9!3
2 5 3 6 1 3 9
^In acest moment, cel mai mare element din  sir se a
 a pe ultima pozit ie.
2 5 3 6 1 3 9 (prin indic am o interschimbare spre st^ anga)
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

Capitolul 1. Analiza algoritmilor elementari de sortare 20
La nalul primului pas, cel mai mic element din  sir se a
 a pe prima pozit ie a
 sirului.
Pasul 2:
1 2 5!3 6 3 9
1 2 3 5 6!3 9
1 2 3 5 3 6 9
Elementul 6 se a
 a pe pozit ia corect a ^ n  sirul sortat.
1 2 3 5 3 6 9
1 2 3 3 5 6 9
S irul este deja sortat, dar algoritmul trebuie s a continue parcurgerea, f ar a reali-
zarea interschimb arilor.
1.2 Algoritmi de sortare bazat i pe num arare
1.2.1 Sortarea prin num arare ( CountingSort )
Consider am 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
sortare de complexitate liniar a, dac a mnu este semnicativ mai mare dec^ at n. Pa sii
algoritmului sunt:
i) se construie ste 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; i2f0; : : : ; mg);
ii) se calculeaz a tabloul frecvent elor cumulate, fc[0: : : m ]; fci=iX
j=0fj,
i2f0; : : : ; mg;
iii) se folose ste tabloul frecvent elor cumulate pentru a contrui tabloul ordonat b.
Algoritmul de sortare prin num arare ( CountingSort ) implementat ^ n C++:
1# include < iostream >
2using namespace std;
3
4void CountingSort (int a[], int n, int m)
5{
6 int b [100];
7 int f [100];
8 for (int i = 0; i <= m; i++)
9 f[i] = 0;

Capitolul 1. Analiza algoritmilor elementari de sortare 21
10 for (int i = 0; i < n; i++)
11 f[a[i ]]++;
12 for (int i = 1; i <= m; i++)
13 f[i] += f[i – 1];
14 for (int i = n -1; i >= 0; i –)
15 {
16 b[f[a[i]] -1] = a[i];
17 f[a[i]] -= 1;
18 }
19 for (int i = 0; i < n; i++)
20 {
21 a[i] = b[i];
22 }
23}
Exemplu. Fie  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.

Capitolul 1. Analiza algoritmilor elementari de sortare 22
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
algoritm de complexitate O(kn).
RadixSort implementat ^ n C++:
1# include <iostream >
2using namespace std;
3
4void CountingSort (int a[], int n, int m, int c)
5{
6 int b[100] , j, i, f [100];
7 for (i = 0; i <= m; i++)
8 f[i] = 0;
9 for (i = 0; i < n; i++)
10 {
11 j = (a[i] / c) % 10;
12 f[j ]++;
13 }
14 for (i = 1; i <= m; i++)
15 f[i] += f[i – 1];
16 for (i = n -1; i >= 0; i –)
17 {
18 j = (a[i] / c) % 10;
19 b[f[j] -1] = a[i];
20 f[j]–;
21 }
22 for (i = 0; i < n; i++)
23 a[i] = b[i];
24}
25
26void RadixSort (int a[], int n)

Capitolul 1. Analiza algoritmilor elementari de sortare 23
27{
28 int i;
29 int mx = a [0];
30 for (i = 1; i < n; i++)
31 {
32 if (a[i] > mx)
33 mx = a[i];
34 }
35 for (i = 1; mx/i >0; i *=10)
36 CountingSort (a, n, 9, i);
37}
Exemplu. Consider am urm atorul  sir:
180, 55, 85, 90, 902, 34, 2, 76.
Vom ^ ncepe s a aranj am  sirul dup a cifra cea mai put in semincativ a a ec arui
num ar, adic a aceea a unit at ilor  si obt inem:
180, 90, 902, 2, 34, 55, 85, 76.
Observ am c a 180 apare ^ n fat a lui 90 pentru c a 180 a fost ^ n  sirul init ial ^ naintea
lui 90, similar  si pentru 902 cu 2  si 55 cu 85.
Apoi urmeaz a s a ordon am  sirul dup a cifra de rang imediat superior, adic a aceea
a zecilor. S irul devine:
902, 2, 34, 55, 76, 180, 85, 90.
Observ am c a 902 revine din nou ^ naintea lui 2 pentru c a acesta era ^ n fat a lui 2.
^In nal, s a ordon am dup a cifra de rang imediat superior fat  a de pasul anterior,
adic a aceea a sutelor. Obt inem  sirul sortat:
2, 34, 55, 76, 85, 90, 180, 902.
Referint e bibliograce. Pentru vericarea corectitudinii algoritmilor studiat i  si
pentru analiza ecient ei acestora am folosit [2], [3]  si [4].

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 cunos-
cute metode de proiectare a algoritmilor. Aceast a strategie de proiectare presupune
^ mp art 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:
^ mp art irea problemei init iale ^ n dou a sau mai multe subprobleme independente,
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 inem 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 ii algoritmilor elaborat i folosind teh-
nica diviz arii, numit Teorema master . Presupunem c a o problem a de dimensiune n
este descompus a ^ n bsubprobleme de aceea si dimensiune, egal a cu n=b. De aseme-
nea, 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
24

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide et Impera 25
^ nbsubprobleme 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 )
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 fo-
losind 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 par-
curgerea 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 ^ n C++:
1# include <iostream >
2using namespace std;
3
4void Merge (int a[], int s, int m, int d)
5{
6 int i, j, k, temp [50];
7 i = s;
8 k = 0;

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

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide et Impera 27
47 m = (s + d) / 2;
48 MergeSort (a, s, m);
49 MergeSort (a, m + 1, d);
50 Merge (a, s, m, d);
51 }
52}
Exemplu. Fie vectorul:
9, 8, 10, 4, 7, 5, 18, 17.
Se ^ njum at at e ste vectorul, form^ andu-se dou a subsecvent e: (9, 8, 10, 4)  si (7, 5,
18, 17). ^In continuare proced am la fel pentru prima secvent  a: obt inem (9, 8)  si (10,
4), apoi (9), (8)  si similar, (10), (4). Am obt inut vectori de dimensiune unu care se
interclaseaz a: (9) cu (8)  si (10) cu (4). Deci, am obt inut secvent ele: (8, 9)  si (4, 10),
care prin interclasare devin (4, 8, 9, 10). Se procedeaz a analog  si pentru secvent ele:
(7), (5)  si (18), (17). Obt inem: (5, 7, 17, 18).
Prin interclasare 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=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 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
structur a while . Altfel 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).

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide et Impera 28
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 lungimen
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
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 transferurilor 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 de transferare. La pasul impera , rezolv am recursiv dou a subprobleme, ecare
de dimensiune 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 ordonat i. 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.
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, divizarea
vectorului ^ n dou a subsecvent e se face t in^ and cont de pozit ia elementelor, ^ n algorit-

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide et Impera 29
mul de sortare rapid a se t ine cont  si de valoarea acestuia. Algortimul MergeSort 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. Al-
goritmul de sortare rapid a se bazeaz a pe partit ionarea  sirului init ial. Astfel, av^ and
tabloul a, partit ionarea presupune o rearanjare a elementelor vectorului init ial ast-
fel ^ nc^ at toate elementele a
ate la st^ anga unui element a[s] sunt mai mici sau egale
cua[s], iar toate elementele a
ate la dreapta lui 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
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 opre ste 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.

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide et Impera 30
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 ^ n C++:
1# include < iostream >
2using namespace std;
3
4int partition (int a[], int stang , int drept )
5{
6 int i, j, pivot , aux;
7 i = stang ;
8 j = drept + 1;
9 pivot = a[ stang ];
10 while ( true )
11 {
12 do {
13 i = i + 1;
14 } while (i <= drept && a[i] < pivot );
15 do {
16 j = j – 1;
17 } while (j >= stang && a[j]> pivot );
18 if (i < j)
19 {
20 aux = a[i];
21 a[i] = a[j];
22 a[j] = aux;
23 }
24 else {
25 aux = a[ stang ];
26 a[ stang ] = a[j];
27 a[j] = aux;
28 return j;
29 }
30 }
31}
32
33void QuickSort (int a[], int stang , int drept )
34{
35 int s;

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide et Impera 31
36 if ( stang < drept )
37 {
38 s = partition (a, stang , drept );
39 QuickSort (a, stang , s – 1);
40 QuickSort (a, s + 1, drept );
41 }
42}
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 vectorul va  partit ionat
^ n dou a subtablouri: unul a c arui elemente sunt mai mici sau egale cu 6, iar cel alalt
va avea elementele mai mari sau egale cu 6. 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 pivotul 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:

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide et Impera 32
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 =4)
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]  si a[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.
S irul sortat este:
2, 3, 4, 5, 6, 7, 9, 10.
Vericarea corectitudinii. Pentru a verica corectitudinea algoritmului de parti-
t ionare, identic am precondit 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
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.
Datorit a condit iilor de continuare din cele dou a structuri do-while , este asigurat a
condit ia 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

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide et Impera 33
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 apeleaz a algoritmul pentru un vector de lungime n.
Astfel, obt 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+ 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 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).

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide et Impera 34
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
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=0Tmediu (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

Capitolul 2. Analiza algoritmilor de sortare bazat i pe metoda Divide et Impera 35
Tmediu (n2) =n1
n2Tmediu (n3) + 2
…
Tmediu (2) =3
2Tmediu (1) + 2
Tmediu (1) = 0 :
^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 suma
nX
i=31
iZn
31
xdx= lnn
3
 si atunci
Tmediu (n) = 2( n+ 1) lnn
3+ 22nlnn1: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.
Metode mai eciente de a alege pivotul sunt: alegerea aleatoare a acestuia sau
metoda "medianei celor 3 valori" { ^ n care se alege elementul mijlociu ca m arime,
dintre trei elemente alese la ^ nt^ amplare din vector. Alte solut ii de ecientizare: utili-
zarea algoritmului de sortare prin insert ie direct a pentru subtablourile de dimensiune
mic a (^ ntre 5  si 15 elemente) sau renunt area la sortarea subtabloului de dimensiune
mic a  si ^ ncheierea algoritmului de sortare cu sortare prin insert ie direct a a ^ ntregului
tablou ce este aproape sortat sau modicarea algoritmului de partit ionare (de exem-
plu, 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).
Referint e bibliograce. Pentru detalii legate de tehnica Divide et Impera am
utilizat [1]  si [2]. Pentru vericarea corectitudinii algoritmilor studiat i  si pentru
analiza ecient ei acestora am folosit [2], [3]  si [4].

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,
reprezent^ and ecare c^ ate un club sportiv. ^In cadrul acestei competit ii se vor desf a sura
trei etape.
Prima etap a:
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 ));
36

Aplicat ii practice 37
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,
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 a un num ar pseudoaleator uniform
distribuit din intervalul [ a; b):
1double random ( double a, double b)
2{
3 uniform_real_distribution < double > dist (a, b);
4 return dist ( generator );
5}
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 c^ ate un club,
deci acestea vor concura ^ ntre ele ^ n cadrul grupei din care vor  repartizate  si numele
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 se-
cunde, deci vom apela funct ia random descris a mai sus cu parametrii corespunz 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 art i ^ n trei grupe.
Dup a realizarea grupelor, sportivele vor intra ^ n competit ie ^ n cadrul grupei din care
fac 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 (variabile aleatoare uniform
continue cu parametrii de 10.5 secunde  si 11.5 secunde), folosind BubbleSort . 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
fetelor vor  citite din  sierul text anterior. Dup a a
area clasamentului (am folosit
algoritmul de sortare prin select ie pentru  sirul timpilor de sosire, ce sunt variabile
aleatoare uniform continue 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 .

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

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

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

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

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

Aplicat ii practice 43
173}
174int main () {
175 cout << " ––– CAMPIONATUL INTERNATIONAL DE ATLETISM
100m VITEZA FEMININ –––––-" << endl ;
176 cout << endl ; cout << endl ;
177 Etapa3 ();
178 in. close ();
179 in1. close ();
180 in2. close ();
181 out. close ();
182 out1 . close ();
183 out2 . close ();
184 return 0;
185}
Red am mai jos un exemplu de utilizare al algoritmului propus.
Etapa I:
Grupa 1 Grupa 2 Grupa 3
Popescu: 11.5569 Petru: 11.2006 Ciuhat: 11.6002
Ionescu: 10.7351 Comanescu: 10.9803 Flescan: 10.825
Adam: 10.7798 Marcel: 11.4706 Catana: 10.7137
Ilinca: 11.1196 Spatariu: 11.4925 Huian: 11.0676
Savin: 10.7137 Dinculescu: 11.2574 Gabor: 11.4836
Macadan: 11.3043 Popa: 11.4738 Alupei: 11.4136
Balan: 11.2294 Bran: 11.5764 Mardare: 11.0554
Pop: 11.4123 Birjovanu: 11.2524 Gheorghe: 11.2932
Ioan: 10.8257 Elisei: 11.6899 Iliescu: 11.4399
Top 3:
Savin: 10.7137 Comanescu: 10.9803 Catana: 10.7137
Ionescu: 10.7351 Petru: 11.2006 Flescan: 10.825
Adam: 10.7798 Birjovanu: 11.2524 Mardare: 11.0554
Grupa 4 Grupa 5 Grupa 6
Ungurasu: 11.2127 Fodor: 11.5814 Gherasim: 10.9783
Morodan: 11.2276 Selaru: 10.8036 Paduraru: 10.877
Galaon: 11.6811 Taralunga: 10.7721 Mihalache: 11.401

Aplicat ii practice 44
Paris: 11.5964 Cenusa: 11.4446 Belciu: 10.8537
Ciangau: 10.9859 Gabor: 11.032 Benone: 11.4048
Grigoras: 11.2153 Adam: 10.7073 Neagu: 11.0663
Diaconu: 11.5471 Rotar: 10.914 Raileanu: 10.7953
Danescu: 11.2952 Toderas: 11.2749 Moisa: 10.9094
Irimia: 10.9407 Budaca: 11.4928 Negru: 11.41
Top 3:
Irimia: 10.9407 Adam: 10.7073 Raileanu: 10.7953
Ciangau: 10.9859 Taralunga: 10.7721 Belciu: 10.8537
Ungurasu: 11.2127 Selaru: 10.8036 Paduraru: 10.877
Grupa 7 Grupa 8 Grupa 9
Ivan: 11.0826 Rusu: 11.6147 Stefan: 11.222
Hotu: 11.5426 Pan: 11.4435 Ivanovici: 10.9666
Mutu: 11.6421 Iacob: 10.8238 Iosub: 10.7314
Ipate: 11.2666 Tabacaru: 10.8067 Culerariu: 10.7537
Vilcan: 11.2861 Scortanu: 10.7989 Ungureanu: 11.538
Rata: 11.2104 Sarivan: 11.2375 Manea: 10.9064
Bobeica: 11.2041 Nutu: 10.8616 Dumitrescu: 11.4119
Matei: 11.3872 Busuioc: 10.8676 Bontea: 11.2996
Ancuta: 11.5988 Balcus: 10.9871 Scarlatescu: 10.9676
Top 3:
Ivan: 11.0826 Scortanu: 10.7989 Iosub: 10.7314
Bobeica: 11.2041 Tabacaru: 10.8067 Culerariu: 10.7537
Rata: 11.2104 Iacob: 10.8238 Manea: 10.9064
Etapa II:
Grupa 1 Grupa 2 Grupa 3
Savin: 11.1283 Irimia: 10.7527 Ivan: 10.6541
Ionescu: 11.4882 Ciangau: 10.7023 Bobeica: 10.9717
Adam: 11.1024 Ungurasu: 11.3175 Rata: 10.6938
Comanescu: 11.3613 Adam: 10.6816 Scortanu: 11.2177
Petru: 11.058 Taralunga: 11.4897 Tabacaru: 11.1914
Birjovanu: 11.2991 Selaru: 11.1096 Iacob: 11.1885
Catana: 10.5816 Raileanu: 10.7168 Iosub: 11.3959
Flescan: 10.9211 Belciu: 10.6745 Culerariu: 11.2575
Mardare: 10.8024 Paduraru: 10.8512 Manea: 11.2406
Top 3:
Catana: 10.5816 Belciu: 10.6745 Ivan: 10.6541
Mardare: 10.8024 Adam: 10.6816 Rata: 10.6938
Flescan: 10.9211 Ciangau: 10.7023 Bobeica: 10.9717

Aplicat ii practice 45
Etapa III:
Grupa 1
Catana: 10.5813
Mardare: 10.5827
Flescan: 10.4974
Belciu: 10.9476
Adam: 11.0341
Ciangau: 10.7083
Ivan: 10.3685
Rata: 10.4401
Bobeica: 10.597
Top 3:
Ivan: 10.3685
Rata: 10.4401
Flescan: 10.4974
Conform algoritmului, sportivele calicate la Campionatul Internat ional de Atletism
sunt:
Ivan are timpul 10.3685
Rata are timpul 10.4401
Flescan are timpul 10.4974.
Aplicat ia 2. Cofet aria Charlotte are un singur angajat  si trebuie s a satisfac a comen-
zile 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 clientul i; i21; 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 identica 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 genera 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.

Aplicat ii practice 46
Tehnica Greedy este clar mai ecient 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 algoritmul
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 servire.
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; i21; n.
Datele de ie sire vor  scrise ^ n  sierul text, timpi.txt .
1# include < iostream >
2# include < fstream >
3# define dim 100
4using namespace std;
5struct Client {
6//t= timpul de servire ; nr= numarul de ordine
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];

Aplicat ii practice 47
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];
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;

Aplicat ii practice 48
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) {
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}
Red am mai jos un exemplu de utilizare al algoritmului propus.
Pentru un num ar de 5 client i care au timpii de servire 12, 7, 15, 20, respectiv 11,
algoritmul ofer a urm atoarea ordine de servire: primul client servit este clientul cu
indicativul 2, al doilea client servit este clientul cu indicativul 5, al treilea client servit
este clientul cu indicativul 1, al patrulea client servit este clientul cu indicativul 3,
respectiv ultimul client servit este clientul cu indicativul 4. Timpul total de a steptare
este 165.
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

Aplicat ii practice 49
^ n care se poate desf a sura [ 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 num ar 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  a 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
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);

Aplicat ii practice 50
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 );
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
incheierii 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;

Aplicat ii practice 51
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);
81 programare (a, n, out);
82 out. close ();
83 return 0;
84}
Red am mai jos un exemplu de utilizare al algoritmului propus.
Presupunem c a trebuie programate 5 spectacole care au momentele de ^ nceput
12:30, 15:00, 10:00, 18:00, respectiv 12:15  si momentele de ^ ncheiere 16:30, 18:00,
18:30, 20:45, respectiv 13:00. Algoritmul ofer a urm atoarea ordine de desf a surare a
spectacolelor: primul spectacol programat este spectacolul cu indicativul 5, al doilea
spectacol programat este spectacolul cu indicativul 2, respectiv, ultimul spectacol
programat este spectacolul cu indicativul 4.
Referint e bibliograce. Pentru detalii legate de tehnica Greedy am utilizat [1]
 si [2].

Bibliograe
[1] T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introducere ^ n Algoritmi , Ed. Com-
puter Libris Agora, Cluj-Napoca, 2000 (traducere).
[2] A. Levitin, Introduction to The Design and Analysis of Algorithms-3rd Edition ,
Ed. Pearson, 2012.
[3] D. Lucanu, M. Craus, Proiectarea Algoritmilor , Ed. Polirom, 2008.
[4] D. Zaharie, Introducere ^ n Proiectarea  si Analiza Algoritmilor , Ed. Eubeea, 2008.
52