Lucrare de licent a [605835]

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 . . . . . . . . . . . . 5
1.1.2 Metoda prin select ie elementului maxim . . . . . . . . . . . . 7
1.1.3 Vericarea 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 Vericarea corectitudinii . . . . . . . . . . . . . . . . . . . . . 14
1.2.4 Analiza complexit at ii . . . . . . . . . . . . . . . . . . . . . . 15
1.3 Metoda prin Interschimbare(Bubble Sort) . . . . . . . . . . . . . . . 15
1.3.1 Vericarea corectitudinii . . . . . . . . . . . . . . . . . . . . . 18
1.3.2 Analiza complexit at ii . . . . . . . . . . . . . . . . . . . . . . 18
1.4 Metoda Counting Sort . . . . . . . . . . . . . . . . . . . . . . . . . . 19
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 Vericarea corectitudini . . . . . . . . . . . . . . . . . . . . . 29
2.1.2 Analiza complexit at ii . . . . . . . . . . . . . . . . . . . . . . 30
2.2 Metoda Quicksort (rapid a) . . . . . . . . . . . . . . . . . . . . . . . 30
2.2.1 Vericarea corectitudinii . . . . . . . . . . . . . . . . . . . . . 35
2.2.2 Analiza complexit at ii . . . . . . . . . . . . . . . . . . . . . . 35
3 Aplicat ie practic a 37
1

Cuprins 2
Bibliograe 38

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
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 cuprinde:
(a) Metoda prin Select ie
(b) Metoda prin Insert ie
(c) Metoda prin Interschimbare
(d) Metoda Counting Sort
3

Cuprins 4
(e) Metoda Radix 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
cuprinde:
(a) Metoda MergeSort
(b) 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 secvent  a nit a format a din nelemente a0; a1; :::; a n1,
rearanjat a cresc ator. Limbajul formal pentru sortarea cresc atoare este de forma.
Ace stia 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 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.
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,
5

Capitolul 1. Analiza algoritmilor de sortare elementari 6
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  sirul 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 sort (int a[], int n) {
4 int i, min , k, j, temp ;
5 for (i = 1; i<n; i++)
6 {
7 min = a[i];
8 k = i;
9 for (j = i + 1; j <= n; j++)
10 if (a[j]< min)
11 {
12 min = a[j];
13 k = j;
14 }
15 temp = a[i];
16 a[i] = a[k];
17 a[k] = temp ;
18 }
19 return 1;
20}
21int main ()
22{
23 int a[20] , n, i;
24 cout << " Introduceti dimensiunea vectorului : n=";cin >>
n;
25 cout << " Introduceti elementele vectorului :" << endl ;
26 for (i = 1; i <= n; i++)
27 {
28 cout << "a[" << i << "]=";
29 cin >> a[i];
30 }
31 sort (a, n);
32 cout << " Dupa sortarea prin selectie , vectorul este : ";
33 for (i = 1; i <= n; i++)

Capitolul 1. Analiza algoritmilor de sortare elementari 7
34 cout << a[i] << " ";
35 return 0;
36}
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].
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
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]  si a[M]

Capitolul 1. Analiza algoritmilor de sortare elementari 8
(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
S a ar at am c a proprietatea
Inv1 =fa[0]a[1]: : :a[i1]  sia[i1]a[j];8j=i; : : : ; n1g
este invariant a pentru ciclul fordup a i. Init ial, i= 0, deci Inv1 este satisf acut a la
intrare ^ n structura repetitiv a( sirul sortat este vid). Pentru ecare 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 ie sirea
din bucl a, Inv2 =fa[m]a[k]; k=i; : : : ; n1g:A sadar,
a[0]a[1]: : :a[i]  sia[i]a[j];8j=i+ 1; : : : ; n1:
Cum ieste incrementat la sf^ ar situl ec arei iterat ii, reg asim proprietatea invariant a.
La ie sirea din bucla for i , invariantul conduce la postcondit ie, pentru c a
i=n1  sia[0]a[1]: : :a[n2]  sia[n2]a[n1]:
Pentru ecare dintre cele dou a cicluri for, variabila contor de iterat ie este in-
crementat a la ecare iterat ie, deci pot  identicate funct ii de terminare cores-
punz atoare. Pentru ciclul exterior, consider am funct ia de terminare t(k) =n1ik,
iar pentru ciclul interior, t(k) =njk. Deci, dup a un num ar nit de iterat ii condit iile
de contiunuare nu vor mai  ^ ndeplinite, execut ia algoritmului ^ ncheindu-se. Prin
urmare, algoritmul se va termina ^ ntr-un num ar nit de pa si, demonstr^ andu-se ast-
fel total corectitudinea algoritmului. Asem anator se realizeaz a  si pentru elementul
maxim.

Capitolul 1. Analiza algoritmilor de sortare elementari 9
1.1.4 Analiza complexit at ii
Num arul de comparat ii nu depinde de distribut ia init ial a a elementelor, ind egal
cu
TC(n) = (n1) + ( n2) +


+ 1 =n(n1)
2:
^In schimb, num arul mut arilor depinde de repartizarea init ial a a elementelor ^ n
secvent  a, ca atare vom analiza cazurile extreme. ^In cazul cel mai favorabil, num arul
interschimb arilor este 0, deci TM(n) = 0 :^In cazul cel mai defavorabil, la ecare
iterat ie ise efectueaz a o interschimbare, deci TM(n) = 3( n1). A sadar,
0TM(n)3(n1):
Cum T(n) =TC(n) +TM(n), obt inem c a
n(n1)
2T(n)(n1)(n+ 6)
2;
 si deci T(n)2(n2), deoarece T(n)2
(n2)  siT(n)2O(n2).
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  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 bazeaz a clar pe o idee recursiv a, care este
mult mai ecient a fat  a de ideea iterativ a.
Algoritmul de sortarea prin insert ie direct a scris sub form a unui cod in C++
este urm atorul:
1 # include <iostream >
2 using namespace std;

Capitolul 1. Analiza algoritmilor de sortare elementari 10
3 void insert ( int a[], int n)
4 {
5 cout << " Introduceti vectorul :" << endl ;
6 for (int i = 1; i <= n; i++)
7 {
8 cout << "a[" << i << "]= ";
9 cin >> a[i];
10 int j = i;
11 while (a[j]<a[j – 1] && j >1)
12 {
13 int aux = a[j];
14 a[j] = a[j – 1];
15 a[j – 1] = aux;
16 j –;
17 }
18 }
19 }
20 int main ()
21 {
22 int a[100] , n, i;
23 cout << " Introduceti dimensiunea vectorului , n= ";
24 cin >> n;
25 insert (a, n);
26 cout << " Vectorul sortat este : ";
27 for (i = 1; i <= n; i++)
28 cout << a[i] << " ";
29 return 0;
30 }
31
Presupunem c a vrem s a sort am un  sir de elemente cu numere ^ ntregi, care sunt
memorate ^ ntr-un tablou. Consider am urm atorul  sir 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  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

Capitolul 1. Analiza algoritmilor de sortare elementari 11
 sir.^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  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 ecient spat iul de memorie ^ l vom aduce pe
20 ^ n locul lui 7  si pe urm a ^ l vom pune pe 7 ^ naintea lui 20. 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 ecient spat iul de memorie, deplas am pe 7  si pe 20 spre dreapta cu
o pozit ie,  si 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  si 7. Vom
deplasa pe 7 si 20 spre dreapta cu o pozit ie. ^In felul acesta se va elibera o pozit ie
^ ntre 3  si 7, loc unde ^ l vom 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  si ultimul element din
 sirul original este plasat pe pozit ia corect a ^ n  sirul ordonat.
Putem vedea cum  sirul ordonat se construie ste treptat peste  sirul 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-

Capitolul 1. Analiza algoritmilor de sortare elementari 12
portant a. Increment ii pot  ale si dup a o putere a lui 2 sau putem folosi un tablou de
increment i cu valori descresc atoare, ultima dintre acestea ind obligatoriu 1. Pentru
aumite alegeri ale secvent ei de increment i se pot obt ine algoritmi de complexitate
mai mic a dec^ at cea a algoritmului de sortare prin insert ie direct a. Un astfel de  sir
de increment i este
1;3;7;15;31;63;127;255;511; : : : ; (2k1;k1);
pentru care s-a demonstrat c a, ^ n cazul cel mai defavorabil, T(n)2O(n3=2). D. E.
Knuth recomand a urm atorul  sir de increment i, deoarece este u sor de implementat
(are aceea si complexitate ^ n cel mai defavorabil caz):
1;4;13;40;121;364;1093;3280; : : :
A sadar, dup a cum se observ a, cel de-al i-lea increment este egal cu de 3 ori 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 defavo-
rabil. Anumite secvent e de increment i ar trebui evitate, av^ and performant e slabe.
Un exemplu de astfel de secvent  a este
1;2;4;8;16;32;64;128;256; : : :(puterile lui 2) ;
deoarece elementele de pe pozit iile pare nu sunt comparate cu cele de pe pozit iile
impare p^ an a la pasul nal.
Algoritmul de sortarea prin insert ie cu pas variabil (shellsort) scris sub form a
unui cod in C++ este urm atorul:
1 # include <iostream >
2 using namespace std;
3 int shellSort (int a[], int n)
4 {
5 for (int i = n / 2; i > 0; i /= 2)
6 {
7 for (int j = i; j < n; j += 1)
8 {
9 int temp = a[j];

Capitolul 1. Analiza algoritmilor de sortare elementari 13
10 int k;
11 for (k = j; k >= i && a[k – i] > temp ; k -= i)
12 a[k] = a[k – i];
13 a[k] = temp ;
14 }
15 }
16 return 0;
17 }
18 int main ()
19 {
20 int a[100] , i, n;
21 cout << " Introduceti dimensiunea vectorului pe care
doriti sa -l sortati : ";
22 cin >> n;
23 for (i = 0; i < n; i++)
24 {
25 cout << " Introduceti elementul vectorului " <<i+1<<"
:";
26 cin >> a[i];
27 }
28 shellSort (a, n);
29 cout << " Vectorul sortat este : ";
30 for (i = 0; i < n; i++)
31 cout << a[i] << " ";
32 return 0;
33 }
34
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

Capitolul 1. Analiza algoritmilor de sortare elementari 14
1, 2, 19 , 5
1, 2, 5, 19
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
S a ar at am c a
Inv1 =fa[0]a[1]: : :a[i1]g
este inavariant pentru ciclul fordup a i(elementele  sirului sortat, a[0]; : : : ; a [i1],
sunt elementele  sirului original de la 0 la i1, permutate). Init ial, i= 1, deci
precondit ia implic a faptul c a  sirul format dintr-un singur element poate  consi-
derat sortat cresc ator. S a ar at am c a proprietatea r am^ ane adev arat a prin execut ia
prelucr arilor din ciclul for.
Fie proprietatea
Inv2 =fa[0]a[1]: : :a[j]  siauxa[j+ 1] = a[j+ 2]: : :a[i]g:
Vom ar ata c a aceasta este o proprietate invariant a pentru structura repetitiv a while .
La intarea ^ n ciclu, j=i1; aux =a[i] =a[j+1], iar  sirul a[0]a[1]: : :a[i1]
este deja ordonat, deci proprietatea este adev arat a la intrarea ^ n ciclu. Apoi, daca
aux < a [j], din a[j+ 1] = a[j] rezult a c a aux < a [j] =a[j+ 1]: : :a[i]. Dup a
execut ie prelucr arii j=j1; a[0]a[1]: : :a[j]  siaux < a [j+ 1] = a[j+ 2]
: : :a[i]. Deci, Inv2 este un invariant pentru ciclul while .
La sf^ ar situl buclei while este adev arat a una dintre relat iile:
a[0]: : :a[j]auxa[j+ 1] = a[j+ 2]: : :a[i];
dac a ciclul s-a ^ ncheiat deoarece auxa[j] sau
auxa[0] = a[1]: : :a[i];
dac a ciclul s-a ^ ncheiat deoarece j=1. Dar,dup a atribuirea a[j+ 1] = aux; a [0]
: : :a[j]a[j+ 1]a[j+ 2]: : :a[i], iar prin incrementarea contorului i,
reg asim proprietatea invariant a. La ie sirea din bucla for; i =n, invariantul implic a
postcondit ia.
Justicarea termin arii ^ n timp nit a algoritmului este aceea si ca ^ n cazul algo-
ritmului de sortare prin select ia minimului, consider^ and funct ia de terminare pentru

Capitolul 1. Analiza algoritmilor de sortare elementari 15
cuclul exterior t(k) =nik, iar pentru cazul interior
t(k) =8
<
:jk+ 1;dac a aux < a [jk]
0;dac a auxa[jk]
1.2.4 Analiza complexit at ii
At^ at num arul comparat iilor, c^ at  si num arul mut arilor depinde de distribut ia init ial a
a elementelor^ n secvent  a. ^In cazul cel mai favorabil, pentru ecare i= 1;2; : : : ; n1,
are loc o singur a comparat ie  si dou a mut ari( aux=a[i]; a[j+ 1] = a[i]). Lu^ and ^ n
calcul  si mut arile  si comparat ile, se obt ine o margine inferioar a pentru timpul de
execut ie,
3(n1)T(n):
^In cazul cel mai defavorabil, pentru ecare i= 1;2; : : : ; n1, au loc icomparat ii  si
i+ 2 mut ari. Obt inem o margine superioar 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)  siT(n)2O(n2):
1.3 Metoda prin Interschimbare(Bubble Sort)
Este una dintre cele mai simple metode de sortare, ^ ns a nu este cea mai ecient a.
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 a
a[i]< a[i+ 1], atunci se trece la urm atoarea comparare, adic a a[i+ 1] cu a[i+ 2],
dac a nu, se interschimb a a[i] cua[i+ 1]  si apoi se compar a a[i+ 1] cu a[i+ 2].
Dup a prima parcurgere a vectorului, pe ultima pozit ie va  cu sigurant  a elementul
av^ and valoarea cea mai mare, dup a a doua parcurgere, pe penultima pozit ie va
ajunge urm atorul element ca valoare, etc. O singur a parcurgere a vectorului nu este
sucient a, ci trebuie continuat p^ an a c^ and nu se mai efectueaz a interschimb ari.
Algoritmul de sortarea prin Interschimbare(Bubble Sort) scris sub form a unui

Capitolul 1. Analiza algoritmilor de sortare elementari 16
cod in C++ este urm atorul:
1 # include <iostream >
2 using namespace std;
3 int bubble (int a[], int n)
4 {
5 int j, i;
6 int sortat ;
7 do {
8 sortat = 1;
9 for (i = 1; i <= n – 1; i++) {
10 if (a[i] > a[i + 1]) {
11 int aux = a[i];
12 a[i] = a[i + 1];
13 a[i + 1] = aux;
14 sortat = 0;
15 }
16 }
17 } while ( sortat == 0);
18 return 1;
19 }
20 int main () {
21 int n,a[100] , i;
22 cout << " Introduceti dimensiunea vectorului : n="; cin
>> n;
23 cout << " Introduceti elementele vectorului :" << endl ;
24 for (i = 1; i <= n; i++)
25 {
26 cout << "a[" << i << "]=";
27 cin >> a[i];
28 }
29 bubble (a, n);
30 cout << " Vectorul sortat este :";
31 for (i = 1; i <= n; i++)
32 cout << a[i] << " ";
33 return 0;
34 }
35

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

Capitolul 1. Analiza algoritmilor de sortare elementari 18
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.
1.3.1 Vericarea 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 a a[0]a[0]. Presupu-
nem c a proprietatea este adev arat a la ^ nceputul iterat iei. Dac a a[i]> a[j+1], atunci
se realizeaz a interschimbarea elementelor  si acestea vor ^ n ordinea a[j]< a[j+1], iar
dac aa[j]a[j+1], nu se efectueaz a interschimb ari, dar proprietatea este adev arat a.
A sadar, proprietatea Inv1 r am^ ane adev arat a la sf^ ar situl iterat iei. Dup a incremen-
tarea variabilei jreg asim proprietatea Inv1. Ceea ce se realizeaz a ^ n ciclul interior
este plasarea celui mai mare element din secvent a a[0]; a[1]; : : : ; a [i] pe pozit ia i.
Fie proprietatea
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 ( sir vid), apoi r am^ ane adev arat a ^ n bucl a
conform celor demonstrate anterior, iar la ie sirea din bucl a, i= 0, deci proprietatea
devine Inv2 =fa[1]: : :a[n1];cua[1]a[0]g, ceea ce implic a postcondit ia.
Pentru a demonstra c a ambele cicluri sunt nite, consider am funct ia de terminare
pentru ciclul exterior, t(k) =ik, iar pentru ciclul interior, t(k) =ikjk.
1.3.2 Analiza complexit at ii
Num arul de comparat ii nu depinde de propriet at ile datelor de intrare, acesta ind
TC(n) =n1X
i=1i1X
j=01 =n1X
i=1i=n(n1)
2:
Num arul de interschimb ari depinde de repartizarea init ial a a elementelor ^ n  sir, deci
vom analiza cazurile extreme. ^In cazul cel mai favorabil num arul de mut ari ale
elementelor ^ n vederea sort arii este TM(n) = 0, iar ^ n cazul cel mai defavorabil se

Capitolul 1. Analiza algoritmilor de sortare elementari 19
obt ine TM(n) =3n(n1)
2:A sadar, 0TM(n)3n(n1)
2:Cum T(n) =TC(n) +
TM(n))n(n1)
2T(n)2n(n1);deciT(n)2(n2).
Algoritmul poate  ^ mbun at at it, implic^ and o variabil a boolean a care s a indice
dac a la iterat ia precedent a au existat interschimb ari. Scopul este de a reduce
num arul de comparat ii.
^In acest caz, num arul de comparat ii ^ n cazul cel mai favorabil este TC(n) =n1,
iar ^ n cazul cel mai defavorabil este la fel ca ^ n cazul general. ^In ceea ce prive ste
num aarul de mut ari, se obt ine aceea si estimare ca ^ n cazul general. Deci, n1
T(n)2n(n1). Prin urmare, avem c a T(n)2
(n)  siT(n)2O(n2).
1.4 Metoda Counting Sort
Aceast a metod a presupune c a ecare dintre cele nelemente ale datelor intrate se
a
 a un num ar ^ ntreg ^ ntre 1  si m, pentru un num ar ^ ntreg m luat oarecare. Atunci
c^ and m=O(n), sortarea se execut a ^ n timpul O(n).
Ideea principal a ^ n sortarea prin num arare este determinarea num arului de ele-
mente mai mici dec^ at y, pentru ecare element ydin datele de intrare. Aceast a
informat ie poate  utilizat a pentru a pozit iona elementul ydirect ^ n pozit ia sa din
tabloul de ie sire.
Presupunem c a datele noastre de intrare formeaz a un tablou a[1: : : n],  si deci
lungime [a] =n. Sunt necesare alte dou a tablouri suplimentare, tabloul b[1: : : n],
care cuprinde datele de ie sire sortate,  si tabloul c[1: : : m ], pentru stocarea temporar a
^ n timpul lucrului. Avem urm atorul algoritm:
O proprietate important a a sort arii prin num arare este stabilitatea : numerele cu
aceea si valoare apar ^ n tabloul de ie sire ^ n aceea si 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.
Algoritmul de sortarea Counting Sort scris sub form a unui cod in C++ este
urm atorul:
1 # include < iostream >
2 using namespace std;
3 int m = 0;
4 /* Metoda de sortare */
5 void Counting_Sort ( int a[], int b[], int n)
6 {
7 int c [100];
8 for (int i = 0; i<m + 1; i++)
9 {

Capitolul 1. Analiza algoritmilor de sortare elementari 20
10 c[i] = 0;
11 }
12 for (int j = 1; j <= n; j++)
13 {
14 c[a[j ]]++;
15 }
16 for (int i = 1; i <= m; i++)
17 {
18 c[i] += c[i – 1];
19 }
20 for (int j = n; j >= 1; j –)
21 {
22 b[c[a[j]]] = a[j];
23 c[a[j]] = c[a[j]] – 1;
24 }
25 }
26 int main ()
27 {
28 int n;
29 cout << " Introduceti dimensiunea vectorului : ";
30 cin >> n;
31 int a[100] , b [100];
32 cout << " Introduceti vectorul :" <<endl ;
33 for (int i = 1; i <= n; i++)
34 {
35 cout << "a[" << i << "]=";
36 cin >> a[i];
37 if (a[i]>m)
38 {
39 m = a[i];
40 }
41 }
42 Counting_Sort (a, b, n);
43 cout << " Vectorul sortat este :";
44 for (int i = 1; i <= n; i++)
45 {
46 cout << b[i] << " ";
47 }

Capitolul 1. Analiza algoritmilor de sortare elementari 21
48 cout << endl ;
49 return 0;
50 }
51
52
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 folose ste
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  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 convenabil a
reprezentare. Avem 2 tipuri de astfel de sortare: LSD(least signicant digit)  si
MSD(most signicant digit). Cel din urm a proceseaz a reprezent arile de la cea mai
semncativ a spre cea mai put in semnicativ a, iar LSD proceseaz a invers.
O variant a mai simpl a a Radix sortului este aceea care folose ste 10 cozi, adic a
folose ste c^ ate una pentru ecare cifr a de la 0 la 9. Fiecare coad a va ret ine la ecare
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 de sortarea Radix Sort scris sub form a unui cod in C++ este urm atorul:
1 # include <iostream >
2 using namespace std;
3 int getMax (int a[], int n)
4 {
5 int max = a [0];
6 for (int i = 1; i < n; i++)

Capitolul 1. Analiza algoritmilor de sortare elementari 22
7 if (a[i] > max)
8 max = a[i];
9 return max ;
10 }
11 void countSort ( int a[], int n, int exp )
12 {
13 int output [100] , i, count [10] = { 0 };
14 for (i = 0; i < n; i++)
15 count [(a[i] / exp) % 10]++;
16 for (i = 1; i < 10; i++)
17 count [i] += count [i – 1];
18 for (i = n – 1; i >= 0; i –)
19 {
20 output [ count [(a[i] / exp ) % 10] – 1] = a[i];
21 count [(a[i] / exp) % 10] – -;
22 }
23 for (i = 0; i < n; i++)
24 a[i] = output [i];
25 }
26 void radixsort ( int arr [], int n)
27 {
28 int exp , m;
29 m = getMax (arr , n);
30 for (exp = 1; m / exp > 0; exp *= 10)
31 countSort (arr , n, exp);
32 }
33 int main ()
34 {
35 int n, i;
36 cout << " Introduceti dimensiunea vectorului : ";
37 cin >> n;
38 int a [100];
39 for (i = 0; i < n; i++)
40 {
41 cout << " Introduceti elementele vectorului " << i +
1 << ": ";
42 cin >> a[i];
43 }

Capitolul 1. Analiza algoritmilor de sortare elementari 23
44 radixsort (a, n);
45 cout << " Vectorul sortat este : ";
46 for (i = 0; i < n; i++)
47 cout << a[i]<<" ";
48 return 0;
49 }
50
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  si avem:
0: 002, 034, 055, 056, 065, 080
1: 180
2-8: nimic
9: 902

Capitolul 1. Analiza algoritmilor de sortare elementari 24
Noua secvent  a: 002, 034, 055, 056, 065, 080, 180, 902 care este sortat a.
1.5.1 Analiza complexit at ii
Pentru a  ecient Radix sortul trebuie s a folosim structuri de date potrivite. Ele-
mentele de sortat ar  preferabil s a e ^ ntr-o list a ^ nl ant uit a ^ n loc de o simpl a
tabel 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 ecient  a c^ at mai
bun a avem nevoie de pointeri la sf^ ar situl ec 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
algoritmilor. Aceast a strategie de proiectare presupune ^ mpart irea programul ^ n cel
put in dou a subprograme independente, ^ ns a acestea sunt asem an atoare cu problema
init ial a. Aceste mici probleme, de regul a sunt rezolvate ^ n mod recursiv  si dup a se
regrupeaz a rezultatele pentru a crea o solut ie problemei init iale.
Pentru a rezolva o astfel de problem a trebuie parcur si trei pa si 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.
Exemplele specice acestei metode sunt algoritmii de parcurgere a arborilor bi-
nari  si algoritmul de c autare binar a ^ n mult imi total ordonate. Deoarece descrierea
strategiei 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)
 si sortarea rapid a(Quicksort).
25

Capitolul 2. Analiza algoritmi de sortare bazat i pe medota Divide-et-Impera 26
Vom enunt a un rezultat important pentru analiza ecient ei algoritmilor
bazat i pe tehnica diviz arii , numit Teorema master . Presupunem c a o problem a
de dimensiune neste descompus a ^ n bsubprobleme de aceea si dimensiune, egal a cu
n/b. De asemenea, presupunem c a doar aprobleme dintre acestea necesit a s a e
rezolvate, ab(a sibsunt constante, a1,b >1). Consider am c a divizarea pro-
blemei init iale ^ n bsubprobleme de dimensiune n/b si compunerea solut iilor acestor
subprobleme au ^ mpreun a costul f(n), iar costul rezolv arii cazului elementar este o
constant a T0. Astfel, timpul de execut ie al algoritmului general satisface recurent a
T(n) =8
<
:T0;dac a nn0
aT(n=b) +f(n);dac a n > n 0:
^In mod evident, ordinul de cre stere al lui T(n) depinde de ordinul de cre stere a lui
f(n)  si de valorile constatelor a sib.
Teorema 1. (Teorema master) Dac a f(n)2(nd); d0, atunci
T(n) =8
>>><
>>>:(nd);dac a a < bd
(ndlogn);dac a a=bd
(nlogba);dac a a > bd:
2.1 Metoda Mergesort (prin interschimbare)
Mergesort este un exemplu bun pentru aplicarea tehnicii Divide-et- Impera. Fie un
 sir pe care ^ l imp art im ^ n dou a sub siruri de lungimi aproximativ egale. Cele dou a
 siruri sunt ordonate recursiv folosind acelea si tehnici de sortare, adic a mergesort .
Apoi rezultatele sunt combinate (interclasate), obt in^ and astfel tabloul init ial sortat.
Prin interclasare se ^ ntelege parcurgerea celor dou a secvent e ordonate  si extragerea
de elemente din acestea astfel ^ n^ at s a obt inem  sirul init ial sortat. Aceste subsecvent e
sunt parcurse simultan cu dou a contoare  si se compar a elementele curente. Cel mai
mic element dintre cele dou a este plasat ^ n  sirul nal, iar contorul utlizat pentru
parcurgerea sub sirului din care a fost preluat elementul este incrementat. Procesul
continu a p^ an a c^ and una dintre secvent e a fost preluat ^ n ^ ntregime  si elementele care
r am^ an ^ n cealalt a secvent  a sunt plasate direct ^ n  sirul nal.
Algoritmul de sortarea Mergesort (prin interschimbare) scris sub form a unui cod
in C++ este urm atorul:
1# include <iostream >
2using namespace std;
3

Capitolul 2. Analiza algoritmi de sortare bazat i pe medota Divide-et-Impera 27
4void Merge (int a[], int l, int h, int m)
5{
6 int i, j, k, temp [50];
7 i = l;
8 k = 0;
9 j = m + 1;
10 while (i <= m && j <= h)
11 {
12 if (a[i] < a[j])
13 {
14 temp [k] = a[i];
15 k++;
16 i++;
17 }
18 else
19 {
20 temp [k] = a[j];
21 k++;
22 j++;
23 }
24 }
25 while (i <= m)
26 {
27 temp [k] = a[i];
28 k++;
29 i++;
30 }
31 while (j <= h)
32 {
33 temp [k] = a[j];
34 k++;
35 j++;
36 }
37 for (i = l; i <= h; i++)
38 {
39 a[i] = temp [i – l];
40 }
41}

Capitolul 2. Analiza algoritmi de sortare bazat i pe medota Divide-et-Impera 28
42void MergeSort (int a[], int l, int h)
43{
44 int m;
45 if (l< h)
46 {
47 m = (l + h) / 2;
48 MergeSort (a, l, m);
49 MergeSort (a, m + 1, h);
50 Merge (a, l, h, m);
51 }
52}
53
54int main ()
55{
56 int n, i;
57 cout << " Introduceti dimensiunea vectorul pe care
doriti sa -l sortati : ";
58 cin >> n;
59 int a [100];
60 for (i = 0; i < n; i++)
61 {
62 cout << " Introduceti elementele vectorului " << i + 1
<< ": ";
63 cin >> a[i];
64 }
65 MergeSort (a, 0, n – 1);
66 cout << " Vectorul sortat este : ";
67 for (i = 0; i < n; i++)
68 cout << a[i]<<" ";
69 return 0;
70}
71
Un exemplu clar care ^ ndeplinet e condit iile acestui algoritm:
Fie vectorul: 9, 8, 10, 4, 7, 5, 18, 17 .
Pasul 1. Se ^ njum at at e ste vectorul, form^ andu-se dou a secvent e:(9, 8, 10, 4)  si
(7, 5, 18, 17).

Capitolul 2. Analiza algoritmi de sortare bazat i pe medota Divide-et-Impera 29
Pasul 2. ^In continuare proced am la fel pentru prima secvent  a:(9,8)  si (10, 4).
Pasul 3. Proced am la fel pentru prima subsecvent  a din prima secvent a:(9), (8).
Pasul 4. Similar  si pentru secvent a: (10, 4).
Pasul 5. Am obt inut vectori de dimensiune unu care se interclaseaz a:(9) cu (7)
 si (10) cu (4). Deci, am obt inut secvent a: (3, 8, 9, 10).
Pasul 6. Se procedeaz a analog  si pentru secvent a: (7, 5, 18, 17). S i obit inem:
(5, 7, 17, 18).
Pasul 7. Am obt iunut vectorul: 3, 8, 9, 10, 5, 7, 17, 18 .Cu ajutorul interclas arii
se obt ine vectorul sortat: 4, 5, 7, 8, 9, 10, 17, 18 .
2.1.1 Vericarea corectitudini
Pornim de la stabilirea precondit iilor  si 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 inva-
riant a I=ftemp [k]a[l]; l=i; : : : ; mijloc  sitemp [k]a[l]; lj; : : : ; dreptg
pentru prima strunctur a while . Astfel spus, elementul pe care tocmai l-am co-
piat ^ n temo [k] este cel mai mic dintre elementele r amase netransferate din cele
dou a p art i ale vectorului a. Acum toate elementele r amase ^ n avor  transfe-
rate ^ n temp [k+ 1]; : : : ; temp [dreptstang ], pentru c a vectorul temp este com-
pletat la st^ anga. Deci, la ^ ncheierea algoritmului merge , va  vericat a condit ia
temp [k]temp [l];8k < l , ceea se ^ nseamn a c a, dup a copierea elementelor din temp
^ na, tabloul va  corect sortat de 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
stang lamijloc  si de la mijloc ladrept , sunt deja sortate. Deci, a[i]a[l]; l=
i+ 1; : : : ; mijloc  sia[j]a[l]; l=j+ 1; : : : ; drept . A sadar, a[i]  sia[j] sunt cele
mai mici elemente r amase netransferate. Dac a a[i]a[j], atunci temp [k] va primi
valoarea a[i]  si deci va  adev arat a relat ia a[i]a[l]; l=j; : : : ; drept . Asem anator
este  si 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.
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. Presupunem
c a algoritmul mergesort sorteaz a corect orice vector de lungime strict mai mic dec^ at
n. Presupunem c a algoritmul funct ioneaz a pentru un vector de dimensiune n. Astfel,
algoritmul mergesort se apeleaz a pentru doi subvectori de lugimen
2
 sinn
2
.

Capitolul 2. Analiza algoritmi de sortare bazat i pe medota Divide-et-Impera 30
Conform ipotezei inductive, aceste dou a subtablouri vor  sortate corect  si, cum
algoritmul de interclasare este corect, rezult a c a, dup a apelul acetuia, va rezulta un
tablou corect sortat.
2.1.2 Analiza complexit at ii
Ne focaliz am pe comparat iile  si transferurile de elemente. Consider am c a T(n) este
num arul de prelucr ari efecutate de c atre algoritmul de sortare prin interclasare  si
Tmerge (n) num arul de prelucr ari efectuate de algoritmul de interclasare. Presupunem
c a dimensiunea problemei este o putere a lui 2. Din punct de vedere al comparat iilor
 si trasferurilor de elemente, sortarea prin interclasare a unui element nu necisit a mult
timp, adic a T(1) = 0. Pentru n >1, num arul maxim de operat ii de baz a efectuate
^ n algoritmul de interclasare este de ordinul ( n). Deci, Tmerge2(n) ^ n cel mai
defavorabil caz. Avem urm atoarea relat ie de recurent  a privit a din punctul de vedere
al comparat iilor  si transferurilor de elemente:
T(n) =8
<
:2Tn
2
+ (n);dac a n >1
0;dac a n= 1;
pentru timpul de execut ie al algoritmului mergeSort , ^ n cel mai defavorabil caz.
Aplic am Teorema master , a=b=2, d=1  si a=bd, rezult a c a T(n)2(nlogn), ^ n
cel mai defavorabil caz. Deci, putem spune c a T(n)2(nlogn).
2.2 Metoda Quicksort (rapid a)
A fost inventat de Hoare ^ n 1962  si se bazeaz a de asemenea pe tehnica Divide-
et-Impera, dar ^ n plus are la baz a  si metoda interschimb arii. Spre deosebire de
mergesort , partea iterativ a a algoritmului este pentru a construi subcazuri, nu de
a combina solut iile lor. Este considerat unul dintre cei mai rapizi  si mai utilizat i
algoritmi de sortare p^ an a ^ n acest moment.
Quicksort are o list a de sortat pe care o ^ mparte ^ n dou a subliste deoarece sunt
mai u sor de sortat. Pentru a rezlva o astfel de problem a trebuie sa urm arim urm atorii
pa si:
Alegerea unui element al listei pe care ^ l vom numi pivot  si astfel am ^ mpart it
lista ^ n dou a subliste
Elementele mai mici dec^ at pivotul se reordoneaz a ^ n a sa fel ^ nc^ at s a e plasate
^ naintea pivotului, iar elementele mai mari s a e dup a pivot. F ac^ and aceast a
partit ie putem spune c a pivotul se a
 a ^ n pozit ia sa nal a

Capitolul 2. Analiza algoritmi de sortare bazat i pe medota Divide-et-Impera 31
Se sorteaz a cele dou a p at i prin tehnica recursiv a, p^ an a c^ and ^ n subliste r am^ ane
doar un singur element.
Astfel, putem spune acum c a lista init ial a a fost sortat a corect.
Quicksort partit ioneaz a lista init ial a. Fie un tablou a, partit ionarea ^ nseamn a
aranjarea elementelor vectorului init ial astfel ^ nc^ at elementele a
ate la st^ anga s a e
mai mici sau egale cu a[s] si elementele a
ate la dreapta de a[s]s a e mai mari
sau egale cu acesta. Deci, a[0]; : : : ; a [s1]a[s]  sia[s+ 1]; : : : ; a [n1]a[s].
Elementul a[s]este pivotul. ^In contiunuare, cele dou a subtablouri sunt sortate ^ n
mod independent prin apeluri recursive ale algoritmului. S a remarc am c a la qui-
cksort partit ionarea este prelucrarea cea mai important a a algoritmului, deoarece
aceata presupune identicarea pivotului , adic a a acelui element a[s] pentru care
a[k]a[s];cuk < s  sia[k]a[s];cuk > s . Aceast a metod a de sortare se nume ste
sortarea prin partit ionare . Dac a nu exist a un pivot, atunci strategia este s a cre-
eze unul. Sunt mai multe strategii de alegere a pivotului. Dar, vom discuta despre
pivotul selectat elementul subtabloului drept, deci pivot =a[stang ]  si presupunem
c a algoritmul de partit ionare este apelat pentru subtabloul a[stang : : : drept ]. Se
porne ste din ambele capete ale sale  si se compar a elementele cu pivotul. ^Ins a par-
curgerea de la st^ anga la dreapta se realizeaz a de la al doilea element. Astfel, pentru
aceasta vom folosi un indice i. Pentru c a dorim ca elementele mai mici dec^ at pi-
vot s a e ^ n partea st^ anga a subtabloului, se sare peste elementele mai mici dec^ at
pivotul  si se opret e la primul element mai mare sau egal cu acesta, a[i]. Invers,
parcurgerea se ^ ncepe cu ultimul element al subtabloului  si folosim un indice j.
^In acest caz, dorim ca elementele mai mari dec^ at pivotul s a e aranjate ^ n partea
dreapt a a subtabloului  si parcurgerea sare peste elementele mai mari dec^ at pivotul
 si se opre ste atunci c^ and primul element ^ nt^ alnit este mai mic sau egal cu acesta,
a[j]. Dup a realizarea acestor parcurgeri se opresc  si avem trei situat ii posibile s a
apar a: dac a i < j , atunci se interschimb a elementele a[i]  sia[j]  si se reia parcurgerea
increment^ and indicele i si decrement^ and indicele j; dac a i > j , atunci vom obt ine
partit ionarea subtabloului dup a interschimbarea pivotului cu elementul a[i]; dac a
i=j, atunci i=j=s si am obt inut partit ionarea. Dar, ultimele dou a cazuri pot
scrise ^ mpreun a, interschimb^ and pivotul cu a[j], pentru ij.
Se aplic a procedeul ^ n continuu de la st^ anga  si de la dreapta pivotului, p^ an a c^ and
aceste subliste sunt sucient de mici, adic a se reduc la un singur element.
Algoritmul de sortarea Quicksort (rapid a) scris sub form a unui cod in C++ este
urm atorul:
1# include < iostream >
2using namespace std;
3void schimb (int *x, int *y)

Capitolul 2. Analiza algoritmi de sortare bazat i pe medota Divide-et-Impera 32
4{
5 int variabila ;
6 variabila = *x;
7 *x = *y;
8 *y = variabila ;
9}
10int Partitie (int a[], int l, int h)
11{
12 int pivot , index , i;
13 index = l;
14 pivot = h;
15 for (i = l; i < h; i++)
16 {
17 if (a[i] < a[ pivot ])
18 {
19 schimb (&a[i], &a[ index ]);
20 index ++;
21 }
22 }
23 schimb (&a[ pivot ], &a[ index ]);
24 return index ;
25}
26int RandomPivotPartition (int a[], int l, int h)
27{
28 int pvt , n, temp ;
29 n = rand ();
30 pvt = l + n % (h – l + 1);
31 schimb (&a[h], &a[pvt ]);
32 return Partitie (a, l, h);
33}
34int QuickSort (int a[], int l, int h)
35{
36 int pivindex ;
37 if (l < h)
38 {
39 pivindex = RandomPivotPartition (a, l, h);
40 QuickSort (a, l, pivindex – 1);
41 QuickSort (a, pivindex + 1, h);

Capitolul 2. Analiza algoritmi de sortare bazat i pe medota Divide-et-Impera 33
42 }
43 return 0;
44}
45int main ()
46{
47 int n, i;
48 cout << " Introduceti dimensiunea vectorului pe care
doriti sa -l sortati : ";
49 cin >> n;
50 int a [100];
51 for (i = 0; i < n; i++)
52 {
53 cout << " Introduceti elementul vectorului " <<i+1<<":
";
54 cin >> a[i];
55 }
56 QuickSort (a, 0, n – 1);
57 cout << " Vectorul sortat este : ";
58 for (i = 0; i < n; i++)
59 cout <<a[i]<<" ";
60 return 0;
61}
S a observ am mai bine ^ n urm atorul exemplu cum se realizeaz a metoda quicksort .
S a consider am urm atorul vector de sortat: 6, 4, 2, 10, 9, 3, 5, 7 .
Conform algoritmului de partit ionare, pivot= 6 ,astfel c a vectorul va  partit ionat
^ n dou a subtablouri: unul a c arui elemente mai mici sau egale cu 6, iar cel alalt va
avea elementele mai mari sau egale cu 5. Pornim cu doi indici i sijce vor
deplasat i spre mijlocul vectorului, p^ an a c^ and se returneaz a pozit ia de partit ionare
s, iar pivotul este interschimbat cu a[s]:
6 4 2 10 9 3 5 7 (pivot=6)
i j
6 4 2 10 9 3 5 7
i j
Elementele a[i] sia[j]vor  interschimbate, rezult^ and vectorul:

Capitolul 2. Analiza algoritmi de sortare bazat i pe medota Divide-et-Impera 34
6 4 2 5 9 3 10 7
i j
6 4 2 5 9 3 10 7
i j
6 4 2 5 3 9 10 7
j i
Pentru c a am ajuns ^ n situat ia ij, se interschimb a pivortul cu a[s], unde
s=j= 4 este pozit ia de partit ionare:
3 4 2 5 6 9 10 7
S a remarc am c a toate elementele mai mici dec^ at pivotul sunt la st^ anga aces-
tuia, iar cele mai mari, la dreapta. Se aplic a recursiv algoritmul de sortare pentru
sub sirurile a[0: : :3] =f3;4;2;5g sia[5: : :7] =f9;10;7g:
3 4 2 5 (pivot =3)
i j
3 4 2 5
i j
3 2 4 5
j i .
Se interschimb a pivotul cu a[s], unde s=j= 1 este pozit ia de partit ionare:
2 3 4 5
Se aplic a recursiv algoritmul de sortare pentru sub sirurile a[0: : :0] =f2g si
a[2: : :3] =f4;5g. Primul caz este elementar,  sirul format dintr-un singur element
ind implicit sortat.
4 5 (pivot =3)
i j
4 5
j i
Se returneaz a pozit ia de interschimbare, s=j= 2.Apoi se apeleaz a recursiv
algoritmul de sortare pentru sub sirurile: a[2: : :1] sia[3: : :3]. Primul caz este cores-
punz ator unui sub sir vid, iar al doilea este un caz elementar.
Apelul algoritmului de sortare pentru subsecvent a a[5: : :7] =f9;10;7g:
9 10 7 (pivot =9)
i j
Elementele a[i] sia[j]vor  interschimbate, rezult^ and vectorul:
9 7 10
i j
Indicii vor iar a si deplasat i,
9 7 10
j i

Capitolul 2. Analiza algoritmi de sortare bazat i pe medota Divide-et-Impera 35
Se interschimb a pivotul cu elementul a[s] si se returneaz a pozit ia de interschim-
bare, s=j= 6.
7 9 10
Se apeleaz a recursiv algoritmul de sortare pentru sub sirurile: a[5: : :5]  sia[7: : :7].
Ambele sunt cazuri elementare. Algoritmul se opre ste.
2.2.1 Vericarea corectitudinii
Pentru a verica corectitudinea algoritmului de partit ionare, identic am precondit ia
 si postcondit ia: Pin=fstang < dreptg, iar Pout=fa[k]a[s] pentru k=
stang; : : : ; s1  sia[k]a[s] pentru k=s+ 1; : : : ; dreptg. Fie proprietatea
I=fdac a i < j; atunci a[k]pivot; k =stang; : : : ; i; iara[k]pivot pentru k=
j; : : : ; drept; iar dac a ij;atunci a[k]pivot pentru k=stang; : : : ; i1;iara[k]
pivot pentru k=j+ 1; : : : ; dreptg. Cum i < j , proprietatea Ieste invariant a ^ n ra-
port cu structura repetitiv a while , iar dup a ultima interschimbare a pivotului cu
elementul a[s], cus=j, se obt ine postcondit ia. Pentru c a avem condit iile de oprire
din cele dou a structuri repeat , asta asigur a c a indicii i sijr am^ an ^ ntre limitele stang
 sidrept .
Corectitudinea algoritmului recursiv se face prin induct ie: cazul c^ and n= 1 este
corect, deoarece un vector cu un singur element este considerat sortat. Presupunem
c a algoritmul quicksort sorteaz a corect orice vector de lungime strict mai mic a dec^ at
n. Presupunem c a se apleaz a algoritmul pentru un vector de lungime n. Astfel,
obit inem partit ia s. Acum vom verica c a oricare ar  dou a elemente de indici i si
jsunt ^ n ordinea corect a: dac a i < js1 sau s+ 1i < j; atunci a[i]a[j],
conform ipotezei inductive; dac a i < s < j , atunci a[i]pivota[j], datorit a
faptului c a algoritmul de partit ionare este corect.
2.2.2 Analiza complexit at ii
Consider am drep operat ii de baz a doar comparat iile, deoarece ^ n algoritmul de
partit ionare, num arul acestora este mai mare, ^ n general dec^ at num arul interschim-
b arilor.
Cazul cel mai defavorabil se obt ine atunci c^ and la ecare partit ionare se obt ine
una din subprobleme de dimensiune 1. Deoarece operat ia de partit ionare necesit a
O(qp) comparat ii, rezult a c a pentru acest caz num arul de comparat ii este O(n2).
Acest rezultat este oarecum surprinz ator, av^ and ^ n vedere c a numele metodei este
"sortarea rapid a". A sa cum vom vedea, ^ ntr-o distribut ie normal a, cazurile pentru
care quicksort execut a n2comparat ii sunt rare, fapt care conduce la o complexitate
medie foarte bun a a algoritmului. ^In contiunuare determin am num arul mediu de
comparat ii. Presupunem c a q+ 1p=nlungimea secvent ei  si c a probabilitatea

Capitolul 2. Analiza algoritmi de sortare bazat i pe medota Divide-et-Impera 36
ca pivotul xs a e al k-lea element este1
n. Rezult a c a probabilitatea obt inerii
subproblemelor de dimensiune kp=i1  siqk=nieste1
n.^In procesul de
partit ionare, un element al tabloului,pivotul, este comparat cu toate celelalte, astfel
c a sunt necesare n1 comparat ii. Acum num arul mediu de comparat ii se calculeaz a
prin urm atoarea formul a:
Tmediu (n) =8
>><
>>:(n1) +1
nnX
i=1(Tmediu (i1) +Tmediu (ni));dac a n1
1 ;dac a n= 0:
Rezolv am aceast a recurent  a. Avem:
Tmediu (n) = (n1) +2
n(Tmediu (0) +


+Tmediu (n1))
nTmediu (n) =n(n1) + 2( Tmediu (0) +


+Tmediu (n1)).
Trecem pe n^ nn-1:
(n1)Tmediu (n1) = ( n1)(n2)+2( Tmediu (0)+


+Tmediu (n2)). Sc adem:
nTmediu (n) = 2( n1)+( n+1)Tmediu (n1).^Imp art im prin n(n1)  si rezolv am
recurent a obt inut a:
Tmediu (n)
n+1=Tmediu (n1)
n+2
n12
n(n+1)
=Tmediu (n1)
n1+2
n+2
n+1
2
(n1)n+2
n(n+1)
=: : :
=Tmediu (0)
1+2
1+


+2
n+1
2
1


2+


+2
n(n+1)
= 1 + 2
1
1+1
2+


+1
n+12
1
1


1+


+1
n(n+1)
:
Deoarece 1 +1
2+


+1
n=O(log2n)  si seriaP1
k(k+1)este convergent a, rezult a
c aT(n) =O(nlog 2n).
Prin urmare, complexitatea medie a algoritmului quicksort esteO(nlog 2n).
Amintim o metod a mai ecient a de a alege pivotul (alegerea aleatoare a pivotului,
metoda "medianei celor 3 valori"- ^ n care se alege elementul mijlociu ca m arime,
dintre trei elemente alese la ^ nt^ amplare din vector etc.), utilizarea algoritmului de
sortare prin insert ie direct a pentru subtablourile de dimensiune mic a (^ ntre 5  si 15
elemente) sau renunt area la soratarea subtabloului de dimensiune mic a  si ^ ncheierea
algoritmului de sortare prin insert ie direct a a^ ntregului tablou ce este aproape sortat,
modicarea algoritmului de partit ionare (de exemplu, partit iona- rea vectorului ^ n
trei p art i: elementele mai mici dec^ at pivotul ^ ntr-o parte, cele egale cu pivotul ^ n
cea de-a doua parte  si cele mai mari ^ n cea de-a treia parte).
Un dezavantaj al algoritmului quicksort este faptul c a nu este stabil.

Capitolul 3
Aplicat ie practic a
37

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).
38