Lucrare de licent a [605846]

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 3
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 Vericarea corectitudinii . . . . . . . . . . . . . . . . . . . . . 8
1.1.4 Analiza complexit at ii . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Metoda prin Insert ie (InsertSort ) . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Metoda prin insert ie direct a . . . . . . . . . . . . . . . . . . . 8
1.2.2 Metoda prin insert ie cu pas variabil (shellsort) . . . . . . . . 10
1.2.3 Vericarea corectitudinii . . . . . . . . . . . . . . . . . . . . . 12
1.2.4 Analiza complexit at ii . . . . . . . . . . . . . . . . . . . . . . 12
1.3 Metoda prin Interschimbare(BubbleSort) . . . . . . . . . . . . . . . . 12
1.3.1 Vericarea corectitudinii . . . . . . . . . . . . . . . . . . . . . 15
1.3.2 Analiza complexit at ii . . . . . . . . . . . . . . . . . . . . . . 15
1.4 Metoda Counting Sort . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.1 Vericarea corectitudinii . . . . . . . . . . . . . . . . . . . . . 15
1.4.2 Analiza complexit at ii . . . . . . . . . . . . . . . . . . . . . . 15
2 Analiza algoritmi de sortare bazat i pe medota Divide-et-Impera 16
2.1 Metoda MergeSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.1 Vericarea corectitudinii . . . . . . . . . . . . . . . . . . . . . 16
2.1.2 Analiza complexit at ii . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Metoda HeapSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1 Vericarea corectitudinii . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 Analiza complexit at ii . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Metoda RadixSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 Vericarea corectitudinii . . . . . . . . . . . . . . . . . . . . . 16
2.3.2 Analiza complexit at ii . . . . . . . . . . . . . . . . . . . . . . 16
1

2
2.4 Metoda QuickSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4.1 Vericarea corectitudinii . . . . . . . . . . . . . . . . . . . . . 16
2.4.2 Analiza complexit at ii . . . . . . . . . . . . . . . . . . . . . . 16
2.4.3 Metoda QuickSort aleator . . . . . . . . . . . . . . . . . . . . 16
Bibliograe 17

Introducere
Aceast a lucrare urm are ste analiza din punct de vedere teoretic, c^ at  si din punct de
vedere practic a unei categorie de algoritmi de sortare, ^ n diferite situat ii.
Elementele unei liste sunt aranjate ^ ntr-o anumit a ordine cu ajutorul unui algo-
ritm de sortare.
Ace sti algoritmi sunt folosit i pentru a sorta at^ at liste de tip numeric, c^ at  si liste
de tip alfabetic. ^Inc a de la ^ nceputurile informaticii, algoritmii de sortare au atras
un num ar mare de studii ^ n domeniu.
De si ideea de baz a a lor este aparent simpl a  si oarecum familiar a, complexitatea
rezolv arii eciente a sort arii este mare.
Existent a unor algoritmi de sortare ecient i este esent ial a pentru utilizarea op-
tim a a altor algoritmi, cum ar  cei de c autare, sau cei de interclasare.
Pentru a considera un algoritm ca ind de sortare, datele acestuia de ie sire ale
acestuia trebuie s a ^ ndeplineasc a dou a condit ii:
ordinea elementelor din datele de ie sire trebuie s a e ori cresc atoare, ori des-
cresc atoare
datele de ie sire trebuie s a e o rearanjare/permutare a celor de intrare, nu o
alterare a acestora.
^In continuare, vom prezenta unele dintre cele mai cunoscute metode de sortare.
Metodele de sortare cele mai frecvent folosite se pot clasica ^ n dou a marii cate-
gorii: metode directe  si metode avansate.
IMetodele directe se bazeaz a pe algoritmi de dicultate redus a, u sor de g asit
 si de ^ nt eles. ^In aceast a categorie se reg ase ste:
Analiza algoritmilor de sortare elementari care la r^ andul lor sunt clasicat i
^ n:
(a) Metoda prin Select ie
(b) Metoda prin Insert ie
(c) Metoda prin Interschimbare
3

4
(d) Metoda Counting Sort
IIMetodele avansate se bazeaz a pe algoritmi put in mai complicat i, dar care
nu necesit a cuno stint e avansate de algoritmic a. Aici se reg ase ste:
Analiza algoritmilor de sortare bazat i pe metoda Divide-et-Impera care la
r^ andul lor cuprind:
(a) Metoda MergeSort
(b) Metoda HeapSort
(c) Metoda RadixSort
(d) Metoda QuickSort
Orice programator trebuie s a cunoasc a metodele de sortare  si s a aleag a folosirea
unei metode, ^ n funct ie de criteriul de ecient  a urm arit. Ecient a metodelor de
sortare, dup a cum am precizat mai sus pentru algoritmi ^ n general, se m asoar a dup a
tipul de execut ie  si memoria folosit a.

Capitolul 1
Analiza algoritmilor de sortare
elementari
^In acest capitol vom presupune o secven ct a nit 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.
1.1 Metoda prin Select ie (Select Sort)
Este o metod a de sortare pentru a a
a 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
metod a este simpl a de utilizat. Fiecare element este mutat cel put in o data.
Pseudocodul este urm atorul:
begin
i n t i , j , n , min
r e a l aux , v [ n ]
read n , v
f o r i= 0 to n 1 do
5

Capitolul 1. Analiza algoritmilor de sortare elementari 6
min= i
f o r j=i+1 to n do
i f v [ j ] <v [ min ] then
min= j
end i f
end f o r
i f min != i then
aux= v [ min ]
v [ min]=v [ i ]
v [ i ]= aux
end i f
end f o r
write a
end
1.1.1 Metoda prin select ie elementului minim
Prima dat a, metoda presupune determinarea celui mai mic element dintr-un tablou,
notat cu mdenumit  si indice astfel ^ nc^ at a[i]> a[m];8i= 0;1; : : : ; n1:^In acest
caz, cel mai mic element este plasat pe prima pozit ie ^ n  sirul sortat. Se repet a
aceea si operat ie p^ an a c^ and ram^ ane doar un singur element sau este  sirul este aranjat
cresc ator.
Algoritmului de sortarea prin select ie elementului minim scris sub form a unui
cod in C++ este urm atorul:
#include <iostream >
using namespace std ;
i n t main ( )
f// se c i t e s c d a t e l e de i n t r a r e
i n t n , a [ 1 0 0 ] , i , j , k , max, min ;
f o r ( i =0; i <n ; i++)
cin>>n ;
f
cout <<"a["<<i<<"]="<< endl ;
cin>>a [ i ] ;
g
f o r ( i =0; i <n ; i++)
f

Capitolul 1. Analiza algoritmilor de sortare elementari 7
min=a [ i ] ;
k=i ;
f o r ( j=i +1; j <n ; j++)
i f ( a [ j ] <min )
f// se sorteaza v e c t o r u l
min=a [ j ] ;
k=j ;
g
max=a [ j ] ;
a [ k]=a [ i ] ;
a [ i ]=max ;
g
f o r ( i =0; i <n ; i++)
cout <<a [ i ]<<" "<<endl ; // se a f i s e a z a r e z u l t a t e l e
g
Vom ar ata un exemplu pentru a ^ ntelege mai bine codul de mai sus. Consider am
urm atorul  sir 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  si se interschimb a ele-
mentele a[0]  si a[9].
S irul devine: 0, 91, 2, 6, 15, 56, 23, 11, 19, 10.
Pas 2: Se determin a indicele elementului minim din sub sirul a[1..9], m = 2  si se
interschimb a elementele a[1]  si a[2].
S irul este acum: 0, 2, 91, 6, 15, 56, 23, 11, 19, 10.
Pas 3: Se determin a indicele elementului minim din sub sirul a[2..9], m = 3  si se
interschimb a elementele a[2]  si a[3].
S irul este acum: 0, 2, 6, 91, 15, 56, 23, 11, 19, 10.
Pas 4: Se determin a indicele elementului minim din sub sirul a[3..9], m = 3  si se
interschimb a elementele a[3]  si 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 sub sirul a[4..9], m = 3  si se
interschimb a elementele a[4]  si 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 sub sirul a[5..9], m = 7  si se
interschimb a elementele a[5]  si a[7].
S irul este acum: 0, 2, 6, 10, 11, 15, 23, 56, 19, 91.
Pas 7: Se determin a indicele elementului minim din sub sirul a[6..9], m = 8  si se
interschimb a elementele a[6]  si a[9].

Capitolul 1. Analiza algoritmilor de sortare elementari 8
S irul este acum: 0, 2, 6, 10, 11, 15, 19, 56, 23, 91.
Pas 8: Se determin a indicele elementului minim din sub sirul a[7..9], m = 8  si se
interschimb a elementele a[7]  si a[8].
S irul este acum: 0, 2, 6, 10, 11, 15, 19, 23, 56, 91, 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]  si a[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[n-2]. Se caut a elementul cel mai mare din acest
sub sir  si se interschimb a cu a[n-2]  s.a.m.d., p^ an a c^ and sub sirul va cont ine un singur
element.
1.1.3 Vericarea corectitudinii
1.1.4 Analiza complexit at ii
1.2 Metoda prin Insert ie (InsertSort )
1.2.1 Metoda prin insert ie direct a
^In aceast a sect iune, vom considera o aplicat ie descrec atoare  pentru  sirul a[0]; a[1]; : : : ; a [i
1]. Presupunem c a o problem a de sortare a  sirului a[0]; a[1]; : : : ; a [i2] a fost
deja rezolvat a pentru a putea rezolva  si pentru  sirul de dimensiune i1 av^ and:
a[0]6a[1]6


6a[i2]. Cum ne ajut a aceast a mic a problem a s a a
 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 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], nu ^ nainte de a deplasa
elementele a[i1]; a[i2]; : : : ; a [j+ 1] cu o pozit ie la dreapta. Rezultatul acestui
algoritm se nume ste 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 ecient a fat  a de ideea iterativ a.
Algoritmul ^ n pseudocod este urm atorul:
begin
i n t i , j , N

Capitolul 1. Analiza algoritmilor de sortare elementari 9
r e a l aux , a [N]
f o r i=1 to N 1 do
aux=a [ i ]
j=i 1
while j >=0 & a [ j ] >aux
a [ j +1]=a [ j ]
j=j 1
end while
a [ j +1]=aux
end f o r
end
S a presupunem c a vrem s a sort am un  sir de numere ^ ntregi, memorate ^ ntr-un
tablou. Fie  sirul de elemente:
10 5 2 3 4 1 8 7
Lista de elemente sortate se va construi ^ n partea din st^ anga a tabloului init ial.
La ^ nceput de tot suntem ^ n situat ia c^ and lista de elemente sortate este vid a.
Algoritmul va alege c^ ate un element din  sirul init ial  si ^ l va insera ^ n lista de
elemente sortate. Elementele din  sirul init ial se aleg ^ n ordinea ^ n care apar ele ^ n
 sir.^In exemplul nostru le vom alege ^ n ordinea 10, 5, 2, 3, etc.
^Incepem cu elementul 10. Cum lista de elemente sortate este vid a, insert ia lui
va  foarte simpl a. Vom obt ine:
10 5 2 3 4 1 8 7
Urmeaz a elementul 5. 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 10. Pentru
a folosi ^ n mod ecient spat iul de memorie ^ l vom aduce pe 10 ^ n locul lui 5  si pe
urm a ^ l vom pune pe 5 ^ naintea lui 10. Vom obt ine:
5 10 2 3 4 1 8 7
Urmeaz a 2. Pe 2 ar trebui s a ^ l inser am ^ naintea lui 5. Din nou, pentru a folosi
ecient spat iul de memorie, deplas am pe 5  si pe 10 spre dreapta cu o pozit ie,  si pe
urm a punem pe 2 ^ naintea lor. Vom obt ine:
2 5 10 3 4 1 8 7
Urmeaz a 3. Pe 3 trebuie s a ^ l inser am ^ ntre 2  si 5. Vom deplasa pe 5  si 10 spre
dreapta cu o pozit ie. ^In felul acesta se va elibera o pozit ie ^ ntre 2  si 5, loc unde ^ l
vom pune pe 3. Obt inem:
2 3 5 10 4 1 8 7
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.

Capitolul 1. Analiza algoritmilor de sortare elementari 10
Putem vedea cum  sirul ordonat se construie ste treptat peste  sirul sortat, ^ n
acela si spat iu de memorie cu acesta.
Ideea de principiu este c a la pasul k avem deja k-1 numere sortate  si 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  si toate numerele de la st^ anga lui sunt mai mici
ca el, rezult a c a avem acum k numere sortate  si 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  si care se execut a cu o vi-
tez a mai mare, permit ^ and schimburi de elemente care sunt foarte ^ ndep artate. Ideea
este de a rearanja un vector pe grupe  si ecare grup a av^ and elementele distant ate
la un anumit pas h. 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 xe: h1; h2; : : : ; h k= 1  si
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 dovede ste a  foarte im-
portant a. Sunt mai multe tipuri de increment ari, dar se pare c a cea mai bun a algere
este a sa numitele incrementele Hibbard .
Pseudocodul este urm atorul:
begin
i n t n , i , j , h
r e a l a [ n ] , aux
read n , a
h = 1
while h <n/3 do
h = 3h + 1 // s i r u l de incrementi sugerat de Knuth
end while
while h >= 1 do
f o r i = h to n 1 do
aux = a [ i ]
j = i
while j >= h && a [ j h ] >aux do
a [ j ] = a [ j h ]
j = j h
end while

Capitolul 1. Analiza algoritmilor de sortare elementari 11
a [ j ] = aux
end f o r
2h = h / 3
end while
write a
end
Exemplu 1. Sortat i 19, 5, 2, 1.
I . shellsort cu pasul h=2: 1  si 3, 2  si 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++:
#include <iostream >
using namespace std ;
i n t s h e l l S o r t ( i n t arr [ ] , i n t n)
f
f o r ( i n t gap = n /2; gap >0 ; gap /= 2)
f
f o r ( i n t i = gap ; i <n ; i += 1)
f
i n t temp = arr [ i ] ;
i n t j ;
f o r ( j= i ; j >= gap && arr [ j gap ] >temp ; j = gap )
arr [ j ] = arr [ j gap ] ;
arr [ j ] = temp ;
g
g
return 0 ;
g

Capitolul 1. Analiza algoritmilor de sortare elementari 12
void printArray ( i n t arr [ ] , i n t n)
f
f o r ( i n t i =0; i <n ; i++)
cout <<arr [ i ] <<" " ;
g
i n t main ( )
f
i n t arr [ ] =f12 , 34 , 54 , 2 , 3 g, i ;
i n t n = s i z e o f ( arr )/ s i z e o f ( arr [ 0 ] ) ;
cout <<" S i r u l i n a i n t e de s o r t a r e :" <<endl ;
printArray ( arr , n ) ;
s h e l l S o r t ( arr , n ) ;
cout <<"S i r u l dupa s o r t a r e :" <<endl ;
printArray ( arr , n ) ;
return 0 ;
g
Output :
S i r u l i n a i n t e de s o r t a r e :
12 34 54 2 3
S i r u l dupa s o r t a r e :
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 Vericarea corectitudinii
1.2.4 Analiza complexit at ii
1.3 Metoda prin Interschimbare(BubbleSort)
Este unul dintre cei mai simplu algoritmi de sortare, ^ ns a nu este cel mai ecient.
Se consider a dat a o secvent  a a1; a2; : : : ; a nde n elemente, pe care este denit 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 complet
ordonate. Aceast a variant a de sortare se mai nume ste  si metoda bulelor sau
BubbleSort .
Scopul acestui tip de sortare const a ^ n compararea elementelor a[i]  sia[i+ 1];
dac aa[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].

Capitolul 1. Analiza algoritmilor de sortare elementari 13
Algoritmul este urm atorul:
begin
i n t n , i , j
r e a l a [ n ] , aux
read n , a
f o r i = n 1 downto 1 do
f o r j = 0 to i 1 do
i f a [ j ] >a [ j +1] then
aux = a [ j ]
a [ j ] = a [ j +1]
a [ j +1] = aux
end i f
end f o r
end f o r
write a
end
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  sirului este pozit ionat acum pe
penultima pozit ie a  sirului init ial. Prin urmare, acesta nu mai poate  parcurs ^ n
contiunuare.
Pasul 3:

Capitolul 1. Analiza algoritmilor de sortare elementari 14
40 65$25 38 13
40 25 65$38 13
40 25 38 65$13 40 25 38 13 65
La nalul celui de-al treilea pas, num arul 65se 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 40se a
 a ^ n pozit ia corect a ^ n  sirul sortat.
Pasul 5:
25 38$13
25 13 38
Elementul 38este 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 s-a aranjat ^ n
^ ntregime: 13 25 38 40 65 79 81
Vom implementa aceast a metod a  si ^ n limbajul C++:
#include <iostream >
using namespace std ;
i n t main ()f
i n t N;
cin> >N;
i n t v [ 1 0 0 ] ;
i n t i ;
f o r ( i = 1 ; i <= N; i++)
cin> >v [ i ] ;
i n t j ;
i n t s o r t a t ;
dof
s o r t a t = 1 ;
f o r ( i = 1 ; i <= N 1 ; i ++)f

Capitolul 1. Analiza algoritmilor de sortare elementari 15
i f ( v [ i ] >v [ i +1])f
i n t aux = v [ i ] ;
v [ i ] = v [ i +1];
v [ i +1] = aux ;
s o r t a t = 0 ;
g
g
gwhile ( s o r t a t == 0 ) ;
f o r ( i = 1 ; i <= N; i++)
cout< <v [ i ]<<" " ;
return 0 ;
g
1.3.1 Vericarea corectitudinii
1.3.2 Analiza complexit at ii
1.4 Metoda Counting Sort
1.4.1 Vericarea corectitudinii
1.4.2 Analiza complexit at ii

Capitolul 2
Analiza algoritmi de sortare
bazat i pe medota
Divide-et-Impera
2.1 Metoda MergeSort
2.1.1 Vericarea corectitudinii
2.1.2 Analiza complexit at ii
2.2 Metoda HeapSort
2.2.1 Vericarea corectitudinii
2.2.2 Analiza complexit at ii
2.3 Metoda RadixSort
2.3.1 Vericarea corectitudinii
2.3.2 Analiza complexit at ii
2.4 Metoda QuickSort
2.4.1 Vericarea corectitudinii
2.4.2 Analiza complexit at ii
2.4.3 Metoda QuickSort aleator
16

Bibliograe
[1] T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introducere ^ n Algoritmi , Computer
Libris Agora, Cluj-Napoca, 2000 (traducere).
[2] D. Lucanu, M. Craus, Proiectarea Algoritmilor , Ed. Polirom, 2008.
[3] Cristian A.Giumale – Introducere in analiza algoritmilor .
[4] Anany Levitin Introduction to The Design and Analysis of Algorithms-3rd ed ,
Pearson.
[5] R azvan Andonie, Ilie G^ arbacea, Algoritmi Fundamentali O perspectiv a
C++ ,Computer Libris Agora, Cluj-Napoca, 1995 (traducere).
[6]http://www.cs.ubbcluj.ro/ vcioban/InformaticaDidactica/AlgoritmiSortare.pdf
17