Lucrare de licent a [605827]

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

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

2
(d) Metoda Counting Sort
(e) Metoda Radix Sort
IIMetodele avansate se bazeaz ˘a pe algoritmi put ¸in mai complicat ¸i, dar care nu
necesit ˘a cunos ¸tint ¸e avansate de algoritmic ˘a. Aici se reg ˘ases ¸te:
Analiza algoritmilor de sortare bazat ¸i pe metoda Divide-et-Impera care la r ˆandul
lor cuprind:
(a) Metoda MergeSort
(b) Metoda HeapSort
(c) Metoda QuickSort
Orice programator trebuie s ˘a cunoasc ˘a metodele de sortare s ¸i s ˘a aleag ˘a folosirea
unei metode, ˆın funct ¸ie de criteriul de eficient ¸ ˘a urm ˘arit. Eficient ¸a metodelor de
sortare, dup ˘a cum am precizat mai sus pentru algoritmi ˆın general, se m ˘asoar ˘a
dup ˘a tipul de execut ¸ie s ¸i memoria folosit ˘a.

Cuprins
Introducere 1
1 Analiza algoritmilor de sortare elementari 5
1.1 Metoda prin Select ¸ie (Select Sort) . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Metoda prin select ¸ie elementului minim . . . . . . . . . . . . . 6
1.1.2 Metoda prin select ¸ie elementului maxim . . . . . . . . . . . . 8
1.1.3 Verificarea corectitudinii . . . . . . . . . . . . . . . . . . . . . . 8
1.1.4 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Metoda prin Insert ¸ie (Insert Sort ) . . . . . . . . . . . . . . . . . . . . . 9
1.2.1 Metoda prin insert ¸ie direct ˘a . . . . . . . . . . . . . . . . . . . . 9
1.2.2 Metoda prin insert ¸ie cu pas variabil (shellsort) . . . . . . . . . 11
1.2.3 Verificarea corectitudinii . . . . . . . . . . . . . . . . . . . . . . 14
1.2.4 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3 Metoda prin Interschimbare(Bubble Sort) . . . . . . . . . . . . . . . . 16
1.3.1 Verificarea corectitudinii . . . . . . . . . . . . . . . . . . . . . . 18
1.3.2 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4 Metoda Counting Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4.1 Verificarea corectitudinii . . . . . . . . . . . . . . . . . . . . . . 22
1.4.2 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 22
1.5 Metoda Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.5.1 Verificarea corectitudinii . . . . . . . . . . . . . . . . . . . . . . 25
1.5.2 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 25
2 Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 26
2.1 Metoda Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1.1 Verificarea corectitudinii . . . . . . . . . . . . . . . . . . . . . . 26
2.1.2 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2 Metoda Heap Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.1 Verificarea corectitudinii . . . . . . . . . . . . . . . . . . . . . . 26
2.2.2 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 26
3

Cuprins 4
2.3 Metoda Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.1 Verificarea corectitudinii . . . . . . . . . . . . . . . . . . . . . . 26
2.3.2 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.3 Metoda Quick Sort aleator . . . . . . . . . . . . . . . . . . . . . 26
Bibliografie 27

Capitolul 1
Analiza algoritmilor de sortare
elementari
ˆIn acest capitol vom presupune o secven ˘ct˘a finit ˘a format ˘a din nelemente a0; a1; :::; a n1,
rearanjat ˘a cresc ˘ator. Limbajul formal pentru sortarea cresc ˘atoare este de forma:
Input: O secvent ¸ ˘a de n numere [a0; a1; :::; a n1].
Output: O permutarea a secvent ¸ei de intrare, [a00; a01: : : ; a0n1], cua00a01: : :a0n1.
Vom introduce ˆın acest capitol c ˆat ¸iva algoritmi elementari de sortare, bazat ¸i
pe compararea elementelor secvent ¸ei de sortat, ˆın general cu performant ¸e sc ˘azute
pentru tablouri de dimensiune mare :
I Metoda prin Select ¸ie
II Metoda prin Insert ¸ie
III Metoda prin Interschimbare
IV Metoda Counting Sort
V Metoda Radix Sort.
1.1 Metoda prin Select ¸ie (Select Sort)
Este o metod ˘a de sortare pentru a afla cel mai mic element sau cel mai mare element
dintr-o anumit ˘a list ˘a stabilit ˘a init ¸ial la ˆınceputul problemei dezb ˘atute. Aceast ˘a me-
tod˘a este simpl ˘a de utilizat. Fiecare element este mutat cel put ¸in o data.
Pseudocodul este urm ˘atorul:
1begin
2 integer i ,j,n,min
5

Capitolul 1. Analiza algoritmilor de sortare elementari 6
3 real aux ,v[n]
4 read n ,v
5 for i= 0 to n 1do
6 min=i
7 for j=i+1to n do
8 ifv[j]<v[min ]then
9 min=j
10 end if
11 end for
12 ifmin !=i then
13 aux=v[min ]
14 v[min ]=v[i]
15 v[i]=aux
16 end if
17 end for
18 write a
19end
1.1.1 Metoda prin select ¸ie elementului minim
Prima dat ˘a, metoda presupune determinarea celui mai mic element dintr-un ta-
blou, notat cu mdenumit s ¸i indice astfel ˆıncˆata[i]> a[m];8i= 0;1; : : : ; n1:ˆIn
acest caz, cel mai mic element este plasat pe prima pozit ¸ie ˆın s ¸irul sortat. Se re-
pet˘a aceeas ¸i operat ¸ie p ˆan˘a cˆand ram ˆane doar un singur element sau este s ¸irul este
aranjat cresc ˘ator.
Algoritmului de sortarea prin select ¸ie elementului minim scris sub form ˘a unui
cod in C++ este urm ˘atorul:
1#include <iostream >
2using namespace std ;
3int main ( )
4f//se c i t e s c d a t e l e de i n t r a r e
5 int n,a[ 1 0 0 ] , i,j,k,max ,min ;
6 for (i=0; i<n;i++)
7 cin>>n;
8f
9 cout <<"a["<<i< <"]="<<endl ;
10 cin>>a[i] ;

Capitolul 1. Analiza algoritmilor de sortare elementari 7
11g
12 for (i=0; i<n;i++)
13f
14 min=a[i] ;
15 k=i;
16 for (j=i+1; j<n;j++)
17 if(a[j]<min )
18f// se s o r t e a z a v e c t o r u l
19 min=a[j] ;
20 k=j;
21g
22 max=a[j] ;
23 a[k]=a[i] ;
24 a[i]=max ;
25g
26 for (i=0; i<n;i++)
27 cout <<a[i]<<" "<<endl ; //se a f i s e a z a r e z u l t a t e l e
28g
Vom ar ˘ata un exemplu pentru a ˆıntelege mai bine codul de mai sus. Consider ˘am
urm ˘atorul s ¸ir pe care ne propunem s ˘a-l sort ˘am cresc ˘ator:
10, 91, 2, 6, 11, 56, 23, 15, 19, 0.
Pas 1: Se determin ˘a indicele elementului minim, m = 9 s ¸i se interschimb ˘a ele-
mentele a[0] s ¸i a[9].
S ¸irul devine: 0, 91, 2, 6, 15, 56, 23, 11, 19, 10.
Pas 2: Se determin ˘a indicele elementului minim din subs ¸irul a[1..9], m = 2 s ¸i se
interschimb ˘a elementele a[1] s ¸i a[2].
S ¸irul este acum: 0, 2, 91, 6, 15, 56, 23, 11, 19, 10.
Pas 3: Se determin ˘a indicele elementului minim din subs ¸irul a[2..9], m = 3 s ¸i se
interschimb ˘a elementele a[2] s ¸i a[3].
S ¸irul este acum: 0, 2, 6, 91, 15, 56, 23, 11, 19, 10.
Pas 4: Se determin ˘a indicele elementului minim din subs ¸irul a[3..9], m = 3 s ¸i se
interschimb ˘a elementele a[3] s ¸i a[9].
S ¸irul este acum: 0, 2, 6, 10, 15, 56, 23, 11, 19, 91.
Pas 5: Se determin ˘a indicele elementului minim din subs ¸irul a[4..9], m = 3 s ¸i se
interschimb ˘a elementele a[4] s ¸i a[7].
S ¸irul este acum: 0, 2, 6, 10, 11, 56, 23, 15, 19, 91.
Pas 6: Se determin ˘a indicele elementului minim din subs ¸irul a[5..9], m = 7 s ¸i se

Capitolul 1. Analiza algoritmilor de sortare elementari 8
interschimb ˘a elementele a[5] s ¸i a[7].
S ¸irul este acum: 0, 2, 6, 10, 11, 15, 23, 56, 19, 91.
Pas 7: Se determin ˘a indicele elementului minim din subs ¸irul a[6..9], m = 8 s ¸i se
interschimb ˘a elementele a[6] s ¸i a[9].
S ¸irul este acum: 0, 2, 6, 10, 11, 15, 19, 56, 23, 91.
Pas 8: Se determin ˘a indicele elementului minim din subs ¸irul a[7..9], m = 8 s ¸i se
interschimb ˘a elementele a[7] s ¸i a[8].
S ¸irul este acum: 0, 2, 6, 10, 11, 15, 19, 23, 56, 91, care este complet sortat cresc ˘ator.
1.1.2 Metoda prin select ¸ie elementului maxim
Metoda este similar ˘a cu sortarea prin select ¸ie elementului minim, doar c ˘a acum
vom determina elementul maxim al tabloului, deci a indicelui M pentru care a[i]<
a[M],8i= 0;1; :::; n1. Apoi sunt interschimbate elementele a[n-1] s ¸i a[M] (ele-
mentul maxim este plasat pe ultima pozit ¸ie ˆın s ¸ir). Procedeul se repet ˘a pentru
subs ¸irul format din elementele a[0], a[1],…, a[n-2]. Se caut ˘a elementul cel mai mare
din acest subs ¸ir s ¸i se interschimb ˘a cu a[n-2] s ¸.a.m.d., p ˆan˘a cˆand subs ¸irul va cont ¸ine
un singur element.
1.1.3 Verificarea corectitudinii
S˘a ar˘at˘am c ˘a proprietatea
Inv1 =fa[0]a[1]: : :a[i1]s ¸ia[i1]a[j];8j=i; : : : ; n1g
este inavariant ˘a pentru ciclul fordup ˘ai. Init ¸ial, i= 0, deci Inv1este satisf ˘acut ˘a la
intrare ˆın structura repetitiv ˘a(s ¸irul sortat este vid). Pentru fiecare i,ˆın ciclul for j ,
se caut ˘a minimul elementelor a[i]; a[i+1]; : : : ; a [n1], care apoi se interschimb ˘a cu
elementul a[i]. Un invariant pentru ciclul interior este deci
Inv2 =fa[m]a[k]; k= 1; : : : ; j1g;
adev ˘arat la intrarea ˆın bucl ˘a, p˘astrat adev ˘arat pe parcursul iterat ¸iei, iar la ies ¸irea
din bucl ˘a,Inv2 =fa[m]a[k]; k=i; : : : ; n1g:As ¸adar,
a[0]a[1]: : :a[i]s ¸ia[i]a[j];8j=i+ 1; : : : ; n1:
Cum ieste incrementat la sf ˆars ¸itul fiec ˘arei iterat ¸ii, reg ˘asim proprietatea invariant ˘a.
La ies ¸irea din bucla for i , invariantul conduce la postcondit ¸ie, pentru c ˘a
i=n1s ¸ia[0]a[1]: : :a[n2]s ¸ia[n2]a[n1]:

Capitolul 1. Analiza algoritmilor de sortare elementari 9
Pentru fiecare dintre cele dou ˘a cicluri for, variabila contor de iterat ¸ie este in-
crementat ˘a la fiecare iterat ¸ie, deci pot fi identificate funct ¸ii de terminare cores-
punz ˘atoare. Pentru ciclul exterior, consider ˘am funct ¸ia de terminare t(k) =n
1ik, iar pentru ciclul interior, t(k) = njk. Deci, dup ˘a un num ˘ar finit de
iterat ¸ii condit ¸iile de contiunuare nu vor mai fi ˆındeplinite, execut ¸ia algoritmului
ˆıncheindu-se. Prin urmare, algoritmul se va termina ˆıntr-un num ˘ar finit de pas ¸i, de-
monstr ˆandu-se astfel total corectitudinea algoritmului. Asem ˘anator se realizeaz ˘a s ¸i
pentru elementul maxim.
1.1.4 Analiza complexit˘ at ¸ii
Num ˘arul de comparat ¸ii nu depinde de distribut ¸ia init ¸ial ˘a a elementelor, fiind egal
cu
TC(n) = (n1) + ( n2) +


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


6a[i2]. Cum ne ajut ˘a aceast ˘a mic ˘a problem ˘a s˘a afl ˘am prin-
cipala problem ˘a adic ˘a a elementului a[i1]? Evident, c ˘autarea pozit ¸iei lui a[i]se
realizeaz ˘a folosind algoritmul de c ˘autare secvent ¸ial ˘a. Astfel, a[i]se compar ˘a cu
a[i1]; a[i2]; : : : , pˆan˘a cˆand se g ˘ases ¸te un element a[j],ˆın subs ¸irul deja ordonat,
astfel ˆıncˆata[j]6a[i]. Se insereaz ˘a elementul a[i]dup ˘aa[j], nuˆınainte de a deplasa

Capitolul 1. Analiza algoritmilor de sortare elementari 10
elementele a[i1]; a[i2]; : : : ; a [j+ 1] cu o pozit ¸ie la dreapta. Rezultatul acestui
algoritm se numes ¸te sortare prin insert ¸ie direct˘ a sau mai simplu spus sortare prin
insert ¸ie .
La acest tip de sortare prin insert ¸ie se baseaz ˘a clar pe o idee recursiv ˘a, care este
mult mai eficient ˘a fat ¸ ˘a de ideea iterativ ˘a.
Algoritmul ˆın pseudocod este urm ˘atorul:
1begin
2 int i,j,N
3 real aux ,a[N]
4 for i=1to N 1do
5 aux=a[i]
6 j=i1
7 while j>=0 & a[j]>aux
8 a[j+1]= a[j]
9 j=j1
10 end while
11 a[j+1]= aux
12 end for
13end
Presupunem c ˘a vrem s ˘a sort ˘am un s ¸ir de elemente cu numere ˆıntregi, care sunt
memorate ˆıntr-un tablou. Consider ˘am urm ˘atorul s ¸ir de elemente:
20 7 3 5 6 2 11 10
Lista de elemente sortate se va construi ˆın partea din st ˆanga a tabloului init ¸ial.
Laˆınceputul problemei suntem ˆın cazul ˆın care lista noastr ˘a de elemente este vid ˘a.
Algoritmul va alege c ˆate un element din s ¸irul init ¸ial s ¸i ˆıl va insera ˆın lista de
elemente sortate. Elementele din s ¸irul init ¸ial se aleg ˆın ordinea ˆın care apar ele ˆın
s ¸ir.ˆIn exemplul nostru le vom alege ˆın ordinea 20, 7, 3, 5, etc.
ˆIncepem cu elementul 20. Cum lista de elemente sortate este vid ˘a, insert ¸ia lui
va fi foarte simpl ˘a. Vom obt ¸ine:
20 7 3 5 6 2 11 10
Urmeaz ˘a elementul 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 eficient spat ¸iul de memorie ˆıl vom aduce pe 20 ˆın locul lui 7 s ¸i pe
urm ˘aˆıl vom pune pe 7 ˆınaintea lui 20. Vom obt ¸ine:
7 20 3 5 6 2 11 10
Urmeaz ˘a 3. Pe 3 ar trebui s ˘aˆıl inser ˘amˆınaintea lui 7. Din nou, pentru a folosi
eficient spat ¸iul de memorie, deplas ˘am pe 7 s ¸i pe 20 spre dreapta cu o pozit ¸ie, s ¸i pe

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

Capitolul 1. Analiza algoritmilor de sortare elementari 12
(are aceeas ¸i complexitate ˆın cel mai defavorabil caz):
1;4;13;40;121;364;1093;3280; : : :
As ¸adar, dup ˘a cum se observ ˘a, cel de-al i-lea increment este egal cu de 3 ori in-
crementul al (i1)lea+1. Sunt multe alte secvent ¸e de increment ¸i care pot conduce
la algoritmi de sortare mai efcient ¸i. De exemplu, Sedgewick propune secvent ¸a
1;8;23;77;281; : : : ; (4k+1+ 32k+ 1;k0;la care se adaug ˘a incrementul 1):
Algoritmul corespunz ˘ator are o performant ¸ ˘a de O(n4=3),ˆın cazul cel mai de-
favorabil. Anumite secvent ¸e de increment ¸i ar trebui evitate, av ˆand performant ¸e
slabe. Un exemplu de astfel de secvent ¸ ˘a este
1;2;4;8;16;32;64;128;256; : : :(puterile lui 2 );
deoarece elementele de pe pozit ¸iile pare nu sunt comparate cu cele de pe pozit ¸iile
impare p ˆan˘a la pasul final.
Pseudocodul este urm ˘atorul:
1begin
2 int n,i,j,h
3 real a [n] ,aux
4 read n ,a
5 h= 1
6 while h<n/3do
7 h= 3h+ 1 // s i r u l de incrementi sugerat de Knuth
8 end while
9 while h>= 1 do
10 for i=h to n 1do
11 aux =a[i]
12 j=i
13 while j>=h&&a[j h ]>aux do
14 a[j] = a[j h ]
15 j=j h
16 end while
17 a[j] = aux
18 end for
19 2 h=h/ 3
20 end while

Capitolul 1. Analiza algoritmilor de sortare elementari 13
21 write a
22end
Exemplu 1. Sortat ¸i 19, 5, 2, 1.
I . shellsort cu pasul h=2: 1 s ¸i 3, 2 s ¸i 4
)19, 5, 2, 1
2, 1, 19, 5
II . shellsort cu pasul h=1:
)2, 1, 19, 5
1, 2, 19, 5
1, 2, 19 , 5
1, 2, 5, 19
Implementarea acestui tip de sortare ˆın C++:
1#include <iostream >
2using namespace std ;
3int shellSort (int arr [ ] ,int n)
4f
5 for (int gap =n/2; gap >0 ;gap /= 2)
6f
7 for (int i=gap ;i<n;i+= 1)
8f
9 int temp =arr [i] ;
10 int j;
11 for (j=i;j>=gap &&arr [j gap ]>temp ;j=gap )
12 arr [j] = arr [j gap ] ;
13 arr [j] = temp ;
14g
15g
16 return 0 ;
17g
18void printArray (int arr [ ] ,int n)
19f
20 for (int i=0; i<n;i++)
21 cout <<arr [i]<<" " ;

Capitolul 1. Analiza algoritmilor de sortare elementari 14
22g
23int main ( )
24f
25 int arr [ ] =f12 , 34 , 54 , 2 , 3 g,i;
26 int n=sizeof (arr )/sizeof (arr [ 0 ] ) ;
27 cout <<"Sirul inainte de sortare:" <<endl ;
28 printArray (arr ,n) ;
29 shellSort (arr ,n) ;
30 cout <<"Sirul dupa sortare:" <<endl ;
31 printArray (arr ,n) ;
32 return 0 ;
33g
34Output :
35Sirul inainte de sortare :
36 12 34 54 2 3
37Sirul dupa sortare :
38 2 3 12 34 54
Avantajul metodei const ˘aˆın faptul c ˘a elementele sunt mutate mai repede mai aproape
de pozit ¸iile lor corecte, sortarea realiz ˆandu-se la distant ¸e mai mari.
1.2.3 Verificarea corectitudinii
S˘a ar˘at˘am c ˘a
Inv1 =fa[0]a[1]: : :a[i1]g
este inavariant pentru ciclul fordup ˘ai(elementele s ¸irului sortat, a[0]; : : : ; a [i1],
sunt elementele s ¸irului original de la 0lai1, permutate). Init ¸ial, i= 1, deci
precondit ¸ia implic ˘a faptul c ˘a s ¸irul format dintr-un singur element poate fi consi-
derat sortat cresc ˘ator. S ˘a ar˘at˘am c ˘a proprietatea r ˘amˆane adev ˘arat˘a prin execut ¸ia
prelucr ˘arilor din ciclul for.
Fie proprietatea
Inv2 =fa[0]a[1]: : :a[j]s ¸iauxa[j+ 1] = a[j+ 2]: : :a[i]g:
Vom ar ˘ata c ˘a aceasta este o proprietate invariant ˘a pentru structura repetitiv ˘awhile .
La intarea ˆın ciclu, j=i1; aux =a[i] =a[j+1], iar s ¸irul a[0]a[1]: : :a[i1]
este deja ordonat, deci proprietatea este adev ˘arat˘a la intrarea ˆın ciclu. Apoi, daca
aux < a [j], din a[j+ 1] = a[j]rezult ˘a c˘aaux < a [j] =a[j+ 1]: : :a[i]. Dup ˘a
execut ¸ie prelucr ˘ariij=j1; a[0]a[1]: : :a[j]s ¸iaux < a [j+ 1] = a[j+ 2]

Capitolul 1. Analiza algoritmilor de sortare elementari 15
: : :a[i]. Deci, Inv2este un invariant pentru ciclul while .
La sf ˆars ¸itul buclei while este adev ˘arat˘a una dintre relat ¸iile:
a[0]: : :a[j]auxa[j+ 1] = a[j+ 2]: : :a[i];
dac˘a ciclul s-a ˆıncheiat deoarece auxa[j]sau
auxa[0] = a[1]: : :a[i];
dac˘a ciclul s-a ˆıncheiat deoarece j=1. Dar,dup ˘a atribuirea a[j+ 1] = aux; a [0]
: : :a[j]a[j+ 1]a[j+ 2]: : :a[i], iar prin incrementarea contorului i,
reg˘asim proprietatea invariant ˘a. La ies ¸irea din bucla for; i =n, invariantul implic ˘a
postcondit ¸ia.
Justificarea termin ˘ariiˆın timp finit a algoritmului este aceeas ¸i ca ˆın cazul algorit-
mului de sortare prin select ¸ia minimului, consider ˆand funct ¸ia de terminare pentru
cuclul exterior t(k) =nik, iar pentru cazul interior
t(k) =8
<
:jk+ 1;dac˘aaux < a [jk]
0;dac˘aauxa[jk]
1.2.4 Analiza complexit˘ at ¸ii
Aˆat num ˘arul comparat ¸iilor, c ˆat s ¸i num ˘arul mut ˘arilor depinde de distribut ¸ia init ¸ial ˘a
a elementelor ˆın secvent ¸ ˘a.ˆIn cazul cel mai favorabil, pentru fiecare i= 1;2; : : : ; n
1, are loc o singur ˘a comparat ¸ie s ¸i dou ˘a mut ˘ari(aux=a[i]; a[j+ 1] = a[i]). Lu ˆand
ˆın calcul s ¸i mut ˘arile s ¸i comparat ¸ile, se obt ¸ine o margine inferioar ˘a pentru timpul de
execut ¸ie,
3(n1)T(n):
ˆIn cazul cel mai defavorabil, pentru fiecare i= 1;2; : : : ; n1, au loc icomparat ¸ii s ¸i
i+ 2mut ˘ari. Obt ¸inem o margine superioar ˘aa timpului de execut ¸ie,
T(n)n1X
i=1(2i+ 2) = ( n1)(n+ 2):
Putem scrie
3(n1)T(n)(n1)(n+ 2):
DeciT(n)2
(n)s ¸iT(n)2O(n2):

Capitolul 1. Analiza algoritmilor de sortare elementari 16
1.3 Metoda prin Interschimbare(Bubble Sort)
Este unul dintre cei mai simplu algoritmi de sortare, ˆıns˘a nu este cel mai eficient.
Se consider ˘a dat ˘a o secvent ¸ ˘aa1; a2; : : : ; a nde n elemente, pe care este definit ˘a
o relat ¸ie de ordine liniar ˘a<. Init ¸ial ordinea elementelor ˆın cadrul acestei secvent ¸e
este aleatoare. Interschimb ˘arile au loc p ˆan˘a cˆand elementele vectorului sunt com-
plet ordonate. Aceast ˘a variant ˘a de sortare se mai numes ¸te s ¸i metoda bulelor sau
BubbleSort .
Scopul acestui tip de sortare const ˘aˆın compararea elementelor a[i]s ¸ia[i+ 1];
dac˘aa[i]< a[i+ 1] , atunci se trece la urm ˘atoarea comparare, adic ˘aa[i+ 1] cu
a[i+2], dac ˘a nu, se interschimb ˘aa[i]cua[i+1] s ¸i apoi se compar ˘aa[i+1] cua[i+2].
Dup ˘a prima parcurgere a vectorului, pe ultima pozit ¸ie va fi cu sigurant ¸ ˘a elementul
avˆand valoarea cea mai mare, dup ˘a a doua parcurgere, pe penultima pozit ¸ie va
ajunge urm ˘atorul element ca valoare, etc. O singur ˘a parcurgere a vectorului nu
este suficient ˘a, ci trebuie continuat p ˆan˘a cˆand nu se mai efectueaz ˘a interschimb ˘ari.
Algoritmul este urm ˘atorul:
1begin
2 int n,i,j
3 real a [n] ,aux
4 read n ,a
5 for i=n 1downto 1do
6 for j= 0 to i 1do
7 ifa[j]>a[j+1] then
8 aux =a[j]
9 a[j] = a[j+1]
10 a[j+1] = aux
11 end if
12 end for
13 end for
14 write a
15end
Exemplu. S˘a consider ˘am c ˘a s ¸irul de sortat este:
79, 40, 65, 81, 25, 38, 13.
Pasul 1:
79$4065 81 25 38 13 (prin ” $” am indicat o interschimbare)
4079$6581 25 38 13
40 65 79 81$2538 13

Capitolul 1. Analiza algoritmilor de sortare elementari 17
40 65 79 25 81$3813
40 65 79 25 38 81$13
40 65 79 25 38 13 81
La finalul primului pas, cel mai mare element din s ¸ir se afl ˘a pe ultima pozit ¸ie
a s ¸irului. Deci, acesta nu va mai face parte din subsecvent ¸a ce va fi parcurs ˘aˆın
continuare.
Pasul 2:
40 65 79$25 38 13
40 65 25 79$38 13
40 65 25 38 79$13
40 65 25 38 13 79
La finalul acestui pas, cel mai mare element al s ¸irului este pozit ¸ionat acum pe
penultima pozit ¸ie a s ¸irului init ¸ial. Prin urmare, acesta nu mai poate fi parcurs ˆın
contiunuare.
Pasul 3:
40 65$25 38 13
40 25 65$38 13
40 25 38 65$13 40 25 38 13 65
La finalul celui de-al treilea pas, num ˘arul 65se afl ˘a pe pozit ¸ia corect ˘aˆın s ¸irul
sortat.
Pasul 4:
40$25 38 13
25 40$38 13
25 38 40$13
25 38 13 40
Num ˘arul 40se afl ˘aˆın pozit ¸ia corect ˘aˆın s ¸irul sortat.
Pasul 5:
25 38$13
25 13 38
Elementul 38este pe pozit ¸ia sa final ˘aˆın s ¸irul sortat.
Pasul 6:
25$13 13 25
ˆIn acest moment, am terminat procesul de sortare deoarece s ¸irul s-a aranjat ˆın
ˆıntregime: 13 25 38 40 65 79 81
Vom implementa aceast ˘a metod ˘a s ¸iˆın limbajul C++:
1 # include <iostream >

Capitolul 1. Analiza algoritmilor de sortare elementari 18
2 using namespace std ;
3 int main ( )f
4 int N;
5 cin> >N;
6 int v[ 1 0 0 ] ;
7 int i;
8 for (i= 1 ; i<=N;i++)
9 cin> >v[i] ;
10 int j;
11 int sortat ;
12 dof
13 sortat = 1 ;
14 for (i= 1 ; i<=N1 ;i++)f
15 if (v[i]>v[i+1])f
16 int aux =v[i] ;
17 v[i] = v[i+ 1 ] ;
18 v[i+1] = aux ;
19 sortat = 0 ;
20 g
21g
22gwhile (sortat == 0 ) ;
23 for (i= 1 ; i<=N;i++)
24 cout < <v[i]<<" " ;
25 return 0 ;
26g
1.3.1 Verificarea corectitudinii
Consider ˘am proprietatea
Inv1 =fa[j]a[k]; k= 0; : : : ; jg:
S˘ar˘at˘am c ˘a aceast ˘a proprietate este invariant ˘a pentru ciclul interior (forj). La intra-
reaˆın ciclu, (j= 0) , proprietatea este adev ˘arat˘a, pentru c ˘aa[0]a[0]. Presupunem
c˘a proprietatea este adev ˘arat˘a laˆınceputul iterat ¸iei. Dac ˘aa[i]> a[j+ 1], atunci se
realizeaz ˘a interschimbarea elementelor s ¸i acestea vor fi ˆın ordinea a[j]< a[j+ 1],
iar dac ˘aa[j]a[j+ 1] , nu se efectueaz ˘a interschimb ˘ari, dar proprietatea este
adev ˘arat˘a. As ¸adar, proprietatea Inv1r˘amˆane adev ˘arat˘a la sf ˆars ¸itul iterat ¸iei. Dup ˘a

Capitolul 1. Analiza algoritmilor de sortare elementari 19
incrementarea variabilei jreg˘asim proprietatea Inv1. Ceea ce se realizeaz ˘aˆın ci-
clul interior este plasarea celui mai mare element din secvent ¸a a[0]; a[1]; : : : ; a [i]pe
pozit ¸ia i.
Fie proprietatea
Inv2 =fa[i+ 1]: : :a[n1];cua[i+ 1]a[j]; j= 0; : : : ; ig:
Proprietatea este invariant ˘a pentru ciclul exterior (fori): la intrarea ˆın ciclu, i=
n1, deci proprietatea este adev ˘arat˘a (s ¸ir vid), apoi r ˘amˆane adev ˘arat˘aˆın bucl ˘a
conform celor demonstrate anterior, iar la ies ¸irea din bucl ˘a,i= 0, deci proprietatea
devine Inv2 =fa[1]: : :a[n1];cua[1]a[0]g, ceea ce implic ˘a postcondit ¸ia.
Pentru a demonstra c ˘a ambele cicluri sunt finite, consider ˘am funct ¸ia de termi-
nare pentru ciclul exterior, t(k) =ik, iar pentru ciclul interir, t(k) =ikjk.
1.3.2 Analiza complexit˘ at ¸ii
1.4 Metoda Counting Sort
Aceast ˘a metod ˘a presupune c ˘a fiecare dintre cele nelemente ale datelor intrate se
afl˘a un num ˘arˆıntreg ˆıntre 1 s ¸i m, pentru un num ˘arˆıntreg m luat oarecare. Atunci
cˆandm=O(n), sortarea se execut ˘aˆın timpul O(n).
Ideea principal ˘aˆın sortarea prin num ˘arare este determinarea numa ˘arului de
elemente mai mici dec ˆaty, pentru fiecare element ydin datele de intrare. Aceast ˘a
informat ¸ie poate fi utilizat ˘a pentru a pozit ¸iona elementul ydirect ˆın pozit ¸ia sa din
tabloul de ies ¸ire.
Presupunem c ˘a datele noastre de intrare formeaz ˘a un tablou a[1: : : n], s ¸i deci
lungime [a] =n. Sunt necesare alte dou ˘a tablouri suplimentare, tabloul b[1: : : n],
care cuprinde datele de ies ¸ire sortate, s ¸i tabloul c[1: : : m ], pentru stocarea tempo-
rar˘aˆın timpul lucrului. Avem urm ˘atorul algoritm:
1 begin
2 int i,j,m,n,a[ ] ,b[ ] ,c[ ]
3 for i= 0 to m do
4 c[i] = 0
5 end for
6 for j= 0 to n do
7 c[a[j] ] = c[a[j] ] + 1
8 end for
9 for i= 1 to m do
10 c[i] = c[i] + c[i1 ]

Capitolul 1. Analiza algoritmilor de sortare elementari 20
11 end for
12 for j=n1downto 0do
13 b[c[a[j] ] 1 ] = a[j]
14 c[a[j] ] = c[a[j] ] 1
15 end for
16 end
O proprietate important ˘a a sort ˘arii prin num ˘arare este stabilitatea : numerele cu
aceeas ¸i valoare apar ˆın tabloul de ies ¸ire ˆın aceeas ¸i ordine ˆın care se g ˘asesc ˆın tabloul
de intrare. Bine ˆınt ¸eles, stabilitatea este important ˘a numai c ˆand datele ˆınvecinate
sunt deplasate ˆımpreun ˘a cu elementul ˆın curs de sortare.
Un exemplu in C++ este urm ˘atorul:
1 # include <iostream >
2 using namespace std ;
3 int m=0;
4 /Metoda de s o r t a r e /
5 void Counting_Sort (int a[ ] ,int b[ ] ,int n)
6f
7 int c[m] ;
8 for (int i=0;i<m+1;i++)
9f
10 C[i] = 0 ;
11g
12 for (int j=1;j<=n;j++)
13f
14 c[a[j] ] + + ;
15g
16 for (int i=1;i<=k;i++)
17f
18 c[i]+=c[i1 ] ;
19g
20 for (int j=n;j>=1;j)
21f
22 b[c[a[j] ] ] =a[j] ;
23 c[a[j] ] =c[a[j] ] 1 ;
24g
25g
26 int main ( )

Capitolul 1. Analiza algoritmilor de sortare elementari 21
27f
28 int n;
29 cout < <"Introduceti dimensiunea vectorului :" ;
30 cin> >n;
31 int a[n] ,b[n] ;
32 for (int i=1;i<=n;i++)
33f
34 cin> >a[i] ;
35 if(a[i]>m)
36f
37 m=a[i] ;
38g
39g
40 Counting_Sort (a,b,n) ;
41 for (int i=1;i<=n;i++)
42f
43 cout < <b[i]<<" " ;
44g
45 cout < <endl ;
46 return 0 ;
47g
48
49 Output
50
51 Primul Run :
52 Introduceti dimensiunea vectorului : 1 0
53 12 345 89 100 23 0 18 44 111 1
54 0 1 12 18 23 44 89 100 111 345
55
56 Al doilea Run :
57 Introduceti dimensiunea vectorului : 5
58 999 87 12 90 567
59 12 87 99 567 999

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

(nlgn)nu se aplic ˘a atunci c ˆand nu mai urm ˘arim modelul sort ˘arii prin comparat ¸ii.
1.5 Metoda Radix Sort
Este un algoritm de sortare ce pune accent pe cifrele individuale ale elementelor
sortate. Aceste elemente pot fi reprezentate prin orice alt caracter ce se poate scrie
prin numere ˆıntregi. Marea majoritate a calculatoarelor digitale sunt reprezentate
pe date ˆın memorie sub form ˘a de numere binare, pentru c ˘a este cea mai convena-
bil˘a reprezentare. Avem 2 tipuri de astfel de sortare: LSD(least significant digit) s ¸i
MSD(most significant digit). Cel din urm ˘a proceseaz ˘a reprezent ˘arile de la cea mai
semnficativ ˘a spre cea mai put ¸in semnificativ ˘a, iar LSD proceseaz ˘a invers.
O variant ˘a mai simpl ˘a a radix sort-ului este aceea care foloses ¸te 10 cozi, adic ˘a
foloses ¸te c ˆate una pentru fiecare cifr ˘a de la 0 la 9. Fiecare coad ˘a va ret ¸ine la fiecare
pas acele numere care au cifra potrivit ˘a rangului curent(*). Elementele se scot din
cozi ˆın oridinea cresc ˘atoare a indicelui cozii dup ˘a ce a avut loc ˆımp˘art ¸irea (*). Dup ˘a
se pun ˆıntr-un vector, care acum devine noua secvent ¸ ˘a de sortat.
Algoritmul poate fi descris astfel:
1repeta for k= 1 to d // pentru f i e c a r e rang
2initializare vector de liste t
3repeta for i= 1 to n // d i s t r i b u i e elem . din x in 10 l i s t e
4extrage in c cifra din pozitia k a lui x [i]
5adauga x [i]la lista t [c]
6repeta for j= 0 to9 // reunire l i s t e in v e c t o r u l x
7adauga toata lista j la vectorul x
De exemplu:
Secvent ¸a init ¸ial ˘a: 180, 55, 65, 80, 2, 34, 902, 56
Avem urm ˘atoarele cozi ˆın prima iterat ¸ie:
0: 180, 080

Capitolul 1. Analiza algoritmilor de sortare elementari 23
1: nimic
2: 002, 902
3: nimic
4: 034
5: 055, 065
6: 056
7-9: nimic
Noua secvent ¸ ˘a de sortat: 180, 080, 002, 902, 034, 055, 065, 056
Sort ˘am acum dup ˘a a doua cifr ˘a. Avem:
0: 002, 902
1: nimic
2: nimic
3: 034
4: nimic
5: 055, 056
6: 065
7: nimic
8: 180, 080
9: nimic
Noua secvent ¸ ˘a: 002, 902, 034, 055, 056, 065, 180, 080
Acum sort ˘am dup ˘a a treia cifr ˘a s ¸i avem:
0: 002, 034, 055, 056, 065, 080
1: 180
2-8: nimic
9: 902
Noua secvent ¸ ˘a: 002, 034, 055, 056, 065, 080, 180, 902 care este sortat ˘a. Acest
exemplu ˆıl implement ˘am s ¸i ˆın limbajul C++:
1 # include <iostream >
2 using namespace std ;
3 int getMax (int arr [ ] ,int n)
4f
5 int mx=arr [ 0 ] ;
6 for (int i=1; i<n;i++)
7 if (arr [i]>mx)
8 mx=arr [i] ;
9 return mx;
10g
11 void countSort (int arr [ ] ,int n,int exp )

Capitolul 1. Analiza algoritmilor de sortare elementari 24
12f
13 int output [n] ;
14 int i,count [10]=f0g;
15 for (i=0;i<n;i++)
16 count [ (arr [i]/exp )%10]++;
17 for (i=1;i<10;i++)
18 count [i]+=count [i1 ] ;
19 for (i=n1 ;i>=0;i)
20f
21 output [count [ (arr [i]/exp ) % 1 0 ] 1 ] = arr [i] ;
22 count [ (arr [i]/exp ) % 1 0 ] ;
23g
24 for (i=0;i<n;i++)
25 arr [i]=output [i] ;
26g
27 void radixsort (int arr [ ] ,int n)
28f
29 int m=getMax (arr ,n) ;
30 for (int exp =1; m/exp>0;exp=10)
31 countSort (arr ,n,exp ) ;
32g
33 void print (int arr [ ] ,int n)
34f
35 for (int i=0;i<n;i++)
36 cout < <arr [i]<<" " ;
37g
38 int main ( )
39f
40 int arr [ ] =f180 , 55 , 65 , 80 , 2 , 34 , 902 , 5 6 g;
41 int n=sizeof (arr )/sizeof (arr [ 0 ] ) ;
42 radixsort (arr ,n) ;
43 print (arr ,n) ;
44 return 0 ;
45g

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

Capitolul 2
Analiza algoritmi de sortare bazat ¸i
pe medota Divide-et-Impera
2.1 Metoda Merge Sort
2.1.1 Verificarea corectitudinii
2.1.2 Analiza complexit˘ at ¸ii
2.2 Metoda Heap Sort
2.2.1 Verificarea corectitudinii
2.2.2 Analiza complexit˘ at ¸ii
2.3 Metoda Quick Sort
2.3.1 Verificarea corectitudinii
2.3.2 Analiza complexit˘ at ¸ii
2.3.3 Metoda Quick Sort aleator
26

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