Lucrare de licent a [605844]

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

Cuprins
Introducere 2
1 Analiza algoritmilor de sortare elementari 4
1.1 Metoda prin Select ¸ie (Select Sort) . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Metoda prin select ¸ie elementului minim . . . . . . . . . . . . . 5
1.1.2 Metoda prin select ¸ie elementului maxim . . . . . . . . . . . . 7
1.1.3 Verificarea corectitudinii . . . . . . . . . . . . . . . . . . . . . . 7
1.1.4 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Metoda prin Insert ¸ie (Insert Sort ) . . . . . . . . . . . . . . . . . . . . . 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 Verificarea corectitudinii . . . . . . . . . . . . . . . . . . . . . . 13
1.2.4 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Metoda prin Interschimbare(Bubble Sort) . . . . . . . . . . . . . . . . 15
1.3.1 Verificarea corectitudinii . . . . . . . . . . . . . . . . . . . . . . 17
1.3.2 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4 Metoda Counting Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4.1 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 21
1.5 Metoda Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.5.1 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 24
2 Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 25
2.1 Metoda Mergesort (prin interschimbare) . . . . . . . . . . . . . . . . . 26
2.1.1 Verificarea corectitudini . . . . . . . . . . . . . . . . . . . . . . 29
2.1.2 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2 Metoda Quicksort (rapid ˘a) . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2.1 Verificarea corectitudinii . . . . . . . . . . . . . . . . . . . . . . 31
2.2.2 Analiza complexit ˘at ¸ii . . . . . . . . . . . . . . . . . . . . . . . . 31
Bibliografie 32
1

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 tre-
buie 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
2

Cuprins 3
(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 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.

Capitolul 1
Analiza algoritmilor de sortare
elementari
ˆIn acest capitol vom presupune o secvent ¸ ˘a finit ˘a format ˘a din nelemente a0; a1; :::; a n1,
rearanjat ˘a cresc ˘ator. Limbajul formal pentru sortarea cresc ˘atoare este de forma.
Aces ¸tia sunt:
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
4

Capitolul 1. Analiza algoritmilor de sortare elementari 5
2 integer i ,j,n,min
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 repet ˘a
aceeas ¸i operat ¸ie p ˆan˘a cˆand ram ˆane doar un singur element sau s ¸irul este aranjat
cresc ˘ator.
Algoritmul 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 ;

Capitolul 1. Analiza algoritmilor de sortare elementari 6
10 cin>>a[i] ;
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.

Capitolul 1. Analiza algoritmilor de sortare elementari 7
Pas 6: Se determin ˘a indicele elementului minim din subs ¸irul a[5..9], m = 7 s ¸i se
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
Aceast ˘a 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]
(elementul 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 invariant ˘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:

Capitolul 1. Analiza algoritmilor de sortare elementari 8
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]:
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 cazurile 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-

Capitolul 1. Analiza algoritmilor de sortare elementari 9
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
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 bazeaz ˘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.
Pasul 1. Vom ˆıncepe 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.
Pasul 2. Dup ˘a 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

Capitolul 1. Analiza algoritmilor de sortare elementari 10
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.
Pasul 3. Apoi 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 urm ˘a punem pe 3 ˆınaintea lor. Vom obt ¸ine:
3, 7, 20, 5, 6, 2, 11, 10.
Pasul 4. Urmeaz ˘a elementul 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.
Pasul 5. Procedeul continu ˘aˆın mod similar p ˆan˘a cˆand s ¸i ultimul element din
s ¸irul original 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);

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

Capitolul 1. Analiza algoritmilor de sortare elementari 12
19 2 h=h/ 3
20 end while
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

Capitolul 1. Analiza algoritmilor de sortare elementari 13
20 for (int i=0; i<n;i++)
21 cout <<arr [i]<<" " ;
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

Capitolul 1. Analiza algoritmilor de sortare elementari 14
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]
: : :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
Atˆ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 15
1.3 Metoda prin Interschimbare(Bubble Sort)
Este una dintre cele mai simple metode de sortare, ˆıns˘a nu este cea mai eficient ˘a.
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 16
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 17
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˘a ar˘at˘am c ˘a aceast ˘a proprietate este invariant ˘a pentru ciclul interior (forj). La in-
trarea ˆın ciclu, (j= 0) , proprietatea este adev ˘arat˘a, pentru c ˘aa[0]a[0]. Presupu-
nem 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 18
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 interior, t(k) =ikjk.
1.3.2 Analiza complexit˘ at ¸ii
Num ˘arul de comparat ¸ii nu depinde de propriet ˘at ¸ile datelor de intrare, acesta fiind
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 s ¸ir,
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:As ¸adar, 0TM(n)3n(n1)
2:Cum T(n) =TC(n) +
TM(n))n(n1)
2T(n)2n(n1);deciT(n)2(n2).
Algoritmul poate fi ˆı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.
ˆ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
prives ¸te num ˘aarul de mut ˘ari, se obt ¸ine aceeas ¸i estimare ca ˆın cazul general. Deci,
n1T(n)2n(n1). Prin urmare, avem c ˘aT(n)2
(n)s ¸iT(n)2O(n2).
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).

Capitolul 1. Analiza algoritmilor de sortare elementari 19
Ideea principal ˘aˆın sortarea prin num ˘arare este determinarea num ˘arului de ele-
mente 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 ]
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++)

Capitolul 1. Analiza algoritmilor de sortare elementari 20
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 ( )
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 ;

Capitolul 1. Analiza algoritmilor de sortare elementari 21
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
1.4.1 Analiza complexit˘ at ¸ii
Sortarea prin num ˘arare are 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 sortului 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.

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

Capitolul 1. Analiza algoritmilor de sortare elementari 23
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 )
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]<<" " ;

Capitolul 1. Analiza algoritmilor de sortare elementari 24
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
1.5.1 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
Divide-et-Impera este o una dintre cele mai cunoscute metode de proiectare a al-
goritmilor. Aceast ˘a strategie de proiectare presupene ˆımpart ¸irea programul ˆın cel
put ¸in dou ˘a subprograme independente, ˆıns˘a acestea sunt asem ˘an˘atoare cu pro-
blema init ¸ial ˘a. Aceste mici probleme, de regul ˘a sunt rezolvate ˆın mod recursiv s ¸i
dup ˘a se regrupeaz ˘a rezultatele pentru a crea o solut ¸ie problemei init ¸iale.
Pentru a rezolva o astfel de problem ˘a trebuie parcurs ¸i trei pas ¸i la nivel de recur-
sivitate:
ˆımpart ¸irea problemei init ¸iale ˆın mai multe subprobleme, numit divide
rezolvarea subproblemelor ˆın mod recursiv, dar dac ˘a acestea au dimensiuni
foarte mici, atunci cel mai bine e s ˘a le rezolv ˘amˆın mod uzual. Acest pas
poart ˘a denumirea de impera(conquer)
gruparea rezultatelor astfel ˆıncˆat s˘a obt ¸iem solut ¸ia la problema init ¸ial ˘a.
Algoritmul general rezultat aplic ˆand tehnica diviz ˘arii este:
1DeI (P(n) )
2begin
3 ifn<=n1 then
4 rez=<rezolva direct P (n)>
5 else
6 <descompune P (n)in b subprobleme P (n1) , . . . , P(nb)>
7 for i=1to b do
8 rezi =DeI (P(ni) ) //rezolva subproblema P ( ni )
9 end for
10 //combinarea r e z u l t a t e l o r
25

Capitolul 2. Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 26
11 rez=combina (rez1 , . . . , rezb )
12 end if
13 return rez
14end
Exemplele specifice acestei metode sunt algoritmii de parcurgere a arborilor bi-
nari s ¸i algoritmul de c ˘autare binar ˘aˆın mult ¸imi total ordonate. Deoarece descrierea
stategiei este bazat ˘a pe recursivitate , trebuie pus accet pe o prelungire de tipul
problem ˘a7!subproblem ˘a unde dimensiunea devine o variabil ˘a liber ˘a.
Revenim la problema noastr ˘a, adic ˘a aceea a sort ˘ariiˆın ordinea cresc ˘atoare a unei
secvent ¸e de nnumere reale. Ne propunem s ˘a folosim tehnica diviz ˘arii pentru a
elabora alt ¸i algoritmi de sortare. Acet ¸ia sunt: sortarea prin interclasare(Mergesort)
s ¸i sortarea rapid ˘a(Quicksort).
2.1 Metoda Mergesort (prin interschimbare)
Mergesort este un exemplu bun pentru aplicarea tehnicii Divide-et- Impera. Fie un
s ¸ir pe care ˆıl imp ˘art ¸im ˆın dou ˘a subs ¸iruri de lungimi aproximativ egale. Cele dou ˘a
s ¸iruri sunt ordonate recursiv folosind aceleas ¸i tehnici de sortare, adic ˘amergesort .
Apoi rezultatele sunt combinate (interclasate), obt ¸in ˆand astfel tabloul init ¸ial sortat.
Prin interclasare se ˆıntelege parcurgerea celor dou ˘a secvent ¸e ordonate s ¸i extragerea
de elemente din acestea astfel ˆınˆat s˘a obt ¸inem s ¸irul init ¸ial sortat. Aceste subsecvent ¸e
sunt parcurse simultan cu dou ˘a contoare s ¸i se compar ˘a elementele curente. Cel mai
mic element dintre cele dou ˘a este plasat ˆın s ¸irul final, iar contorul utlizat pentru
parcurgerea subs ¸irului 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 s ¸i elementele
care r ˘amˆanˆın cealalt ˘a secvent ¸ ˘a sunt plasate direct ˆın s ¸irul final. Avem urm ˘atorul
algoritm:
1 // i n t e r c l a s a r e a
2 merge (int a[ ] ,int stang ,int mijloc ,int drept )
3 begin
4 int i,j,k
5 i=stang
6 j=mijloc +1
7 k=0
8 int temp [drept stang +1]
9 while (i<=mijloc &&j<=drept )
10 ifa[i]<a[j]

Capitolul 2. Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 27
11 temp [k]=a[i]
12 i=i+1
13 else
14 temp [k]=a[j]
15 j=j+1
16 end if
17 k=k+1
18 end while
19 while i<=mijloc
20 temp [k]=a[i]
21 i=i+1
22 k=k+1
23 end while
24 while j<=drept
25 temp [k]=a[j]
26 j=j+1
27 k=k+1
28 end while
29 for k=0to drept stang
30 a[stang +k]=temp [k]
31 end for
32 end
Implementarea acestui algoritm ˆın C++:
1 # include <iostream >
2 using namespace std ;
3 int main ( )
4f
5 int a[ 9 0 ] , b[ 9 0 ] , c[ 1 8 0 ] ;
6 int n,h,l= 0 ;
7 cout <<"Introduceti numarul de elemente
8 corespunzator vectorului a= " ;
9 cin>>n;
10 cout <<"Introduceti elementele vectorului a= " ;
11 for (int i= 0 ; i<n;i++)
12 cin>>a[i] ;
13 cout <<"Introduceti numarul de elemente
14 corespunzator vectorului b= " ;

Capitolul 2. Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 28
15 cin>>h;
16 cout <<"Introduceti elementele vectorului b=" ;
17 for (int i= 0 ; i<h;i++)
18 cin>>b[i] ;
19 int i= 0 , j= 0 ;
20 while (i<n&&j<h)
21f
22 if (a[i]<b[j] )
23f
24 c[l] = a[i] ;
25 l++;
26 i++;
27g
28 else
29f
30 c[l] = b[j] ;
31 l++;
32 j++;
33g
34g
35
36 if (i<=n)
37f
38 for (int p=i;p<n;p++)
39f
40 c[l] = a[p] ;
41 l++;
42g
43g
44 if (j<=h)
45f
46 for (int p=j;p<h;p++)
47f
48 c[l] = b[p] ;
49 l++;
50g
51g
52 for (int p= 0 ; p<l;p++)

Capitolul 2. Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 29
53 cout <<c[p]<<" " ;
54 return 0 ;
55g
Un exemplu clar care ˆındeplinet ¸e cont ¸iile acestui algoritm:
Figura 1: Realizarea algoritmului de sortare prin interclasare(din [6])
2.1.1 Verificarea corectitudini
Pornim de la stabilirea precondit ¸iilor s ¸i a postcondit ¸iilor: Pin=fa[stang : : : mijloc ]
este cresc˘ ator ¸ si a[mijloc +1: : : drept ]este cresc˘ atorg, iarPout=fa[stang : : : drept ]este cresc ˘atorg.
S˘a presupunem c ˘a, la interat ¸ia k, indicii ˆın cele dou ˘a p˘art ¸i ale vectorului sunt asunt
i, respectiv j. Astfel, vom considera proprietatea invariant ˘aI=ftemp [k]a[l]; l=
i; : : : ; mijloc s ¸itemp [k]a[l]; lj; : : : ; dreptgpentru prima strunctur ˘awhile . Ast-
fel spus, elementul pe care tocmai l-am copiat ˆıntemo [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 ˆınavor fi transferate ˆıntemp [k+ 1]; : : : ; temp [dreptstang ],
pentru c ˘a vectorul temp este completat la st ˆanga. Deci, la ˆıncheierea algoritmului
merge , va fi verificat ˘a condit ¸ia temp [k]temp [l];8k < l , ceea se ˆınseamn ˘a c˘a, dup ˘a
copierea elementelor din temp ˆına, tabloul va fi corect sortat de la stang ladrept .
Pentru a demonstra c ˘a invariantul este corect, ne reamintim c ˘a, atunci c ˆand
este apelat algoritmul de interclasare merge , cele dou ˘a subsecvent ¸e a lui a, de la

Capitolul 2. Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 30
stang lamijloc s ¸i de la mijloc ladrept , sunt deja sortate. Deci, a[i]a[l]; l=i+
1; : : : ; mijloc s ¸ia[j]a[l]; l=j+ 1; : : : ; drept . As ¸adar, a[i]s ¸ia[j]sunt cele mai
mici elemente r ˘amase netransferate. Dac ˘aa[i]a[j], atunci temp [k]va primi va-
loarea a[i]s ¸i deci va fi adev ˘arat˘a relat ¸ia a[i]a[l]; l=j; : : : ; drept . Asem ˘anator
este s ¸i pentru cel ˘alt caz. Aceast ˘a metod ˘a este stabil ˘a, dar are necesit ˘a un spat ¸iu de
memorie suplimentar ˆın etapa de interclasare.
1 //a l g o r r i t m u l r e c u r s i v de s o r t a r e
2 mergesort (int a[ ] ,int stang ,int drept )
3 begin
4 int mijloc
5 ifstang <drept then
6 mijloc =(stang +drept )/2
7 // s o r t a r e a s u b l i s t e l o r
8 mergesort (a,stang ,mijloc )
9 mergesort (a,mijloc +1 ,drept )
10 // i n t e r c l a s a r e a
11 merge (a,stang ,mijloc ,drept )
12 end if
13 end
Apelul algorimului pentru un vector ade dimensiune nse va face prin mergesort(a,0,n-
1).
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. Presu-
punem c ˘a algoritmul mergesort sorteaz ˘a corect orice vector de lungime strict mai
mic dec ˆatn. Presupunem c ˘a algoritmul funct ¸ioneaz ˘a pentru un vector de dimen-
siune n. Astfel, algoritmul mergesort se apeleaz ˘a pentru doi subvectori de lugime
n
2
s ¸inn
2
. Conform ipotezei inductive, aceste dou ˘a subtablouri vor fi sortate
corect s ¸i, cum algoritmul de interclasare este corect, rezult ˘a c˘a, dup ˘a apelul acetuia,
va rezulta un tablou corect sortat.
2.1.2 Analiza complexit˘ at ¸ii
Ne focaliz ˘am pe comparat ¸iile s ¸i transferurile de elemente. Consider ˘am c ˘aT(n)
este num ˘arul de prelucr ˘ari efecutate de c ˘atre algoritmul de sortare prin intercla-
sare s ¸i 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 ve-
dere al comparat ¸iilor s ¸i trasferurilor de elemente, sortarea prin interclasare a unui
element nu necisit ˘a mult timp, adic ˘aT(1) = 0 . Pentru n > 1, num ˘arul ma-

Capitolul 2. Analiza algoritmi de sortare bazat ¸i pe medota Divide-et-Impera 31
xim de operat ¸ii de baz ˘a efectuate ˆın algoritmul de interclasare este de ordinul
(n). Deci, Tmerge2(n)ˆın cel mai defavorabil caz. Avem urm ˘atoarea relat ¸ie
de recurent ¸ ˘a privit ˘a din punctul de vedere al comparat ¸iilor s ¸i transferurilor de ele-
mente:
T(n) =8
<
:2Tn
2
+ (n);dac˘an >1
0;dac˘an= 1
, pentru timpul de execut ¸ie al algoritmului mergeSort ,ˆın cel mai defavorabil caz.
Aplic ˘amTeorema master , a=b=2, d=1 s ¸i a=bd, rezult ˘a c˘aT(n)2(nlogn),ˆın cel
mai defavorabil caz. Deci, putem spune c ˘aT(n)2(nlogn).
2.2 Metoda Quicksort (rapid˘ a)
2.2.1 Verificarea corectitudinii
2.2.2 Analiza complexit˘ at ¸ii

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).
[6]https://www.geeksforgeeks.org/merge-sort/ .
32