Algoritmi si complexitate [605847]

Algoritmi  si complexitate
Curs 5. Algoritmi elementari de sortare
Consider am o secvent  a nit a a0; a1; : : : ; a n1denelemente dintr-o mult ime total ordonat a. Pro-
blema sort arii const a ^ n rearanjarea componentelor secvent ei ^ ntr-o ordine specic a, printr-o permutare
a acestora. Vom presupune c a elementele secvent ei sunt memorate ^ n ^ ntregime ^ n memoria intern a
a calculatorului, av^ and deci acces aleator la acestea. A sadar, vom analiza doar algoritmi de sortare
intern a . Pentru sortarea unor date memorate pe un suport ce nu permite accesul aleator la date,
sunt necesari algoritmi speciali, de sortare extern a . De asemenea, vom simplica problema general a a
sort arii, presupun^ and c a secvent a dat a este memorat a ^ ntr-un tablou unidimensional. Sortarea poate
cresc atoare saudescresc atoare . Formal, problema sort arii cresc atoare poate  denit a astfel:
1Input: O secvent  a de nnumere [a0; a1; : : : ; a n1].
2Output: O permutare a secvent ei de intrare, [a0
0; a0
1; : : : ; a0
n1], cu
a0
0a0
1


 a0
n1.
Exist a mult i algoritmi prin care se rezolv a problema sort arii interne. Vom introduce ^ n acest curs
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 (sortarea prin select ie, prin insert ie, prin
interschimbarea elementelor vecine), urm^ and ca, ulterior, atunci c^ and vom studia tehnica \Divide et
Impera", s a analiz am algoritmi ecient i de sortare (sortarea rapid a  si cea prin interclasare). Vom verica
corectitudinea algoritmilor descri si  si vom analiza complexitatea asimptotic a a acestora. Precondit ia
problemei de sortare este
Pin=fn2Ng(vectorul are m acar un element),
iar postcondit ia este
Pout=fa[0]a[1]


a[n-1]g,
cu precizarea c a secvent a de ie sire reprezint a o permutare a secvent ei de intrare. Ecient a unei metode
de sortare este determinat a de num arul de comparat ii  si de num arul de mut ari ale elementelor din
tablou. Num arul de elemente ale tabloului (dimensiunea problemei)  si caracteristicile datelor de intrare
sunt determinante ^ n alegerea uneia sau alteia dintre metodele de sortare. Vom nota cu TC(n)  siTM(n)
num arul de comparat ii, respectiv num arul de mut ari efectuate pentru a sorta cresc ator secvent a de
numere. Pentru algoritmii elementari ce vor  descri si ^ n continuare, cazul cel mai favorabil corespunde
 sirului ordonat cresc ator, iar cel mai defavorabil caz corespunde  sirului ordonat descresc ator.
1 Sortarea prin select ie
Aceast a metod a de sortare se bazeaz a pe selectarea, la ecare pas al algoritmului, a unui anumit
element din secvent  a  si apoi plasarea sa pe pozit ia corect a ^ n  sir. Algoritmii de sortare ce au la baz a
aceast a metod a difer a ^ n funct ie de criteriul de select ie a elementului: algoritmul de sortare prin select ia
minimului/maximului, prin select ia sistematic a (heapsort) etc. Ne vom ocupa ^ n aceast a sect iune doar
de algoritmii de sortare prin select ia minimului  si de cel prin select ia maximului.
1

Algoritmi  si complexitate Curs 5
1.1 Sortarea prin select ia elementului minim
La primul pas, metoda presupune determinarea elementului minim al tabloului, de fapt a indicelui m
pentru care a[i] > a[m],8i = 0, 1,…, n – 1 . Elementul minim trebuie plasat pe prima pozit ie
^ n  sirul sortat. A sadar se schimb a ^ ntre ele (se interschimb a) elementele a[0]  sia[m] . Se repet a operat ia
pentru sub sirul de elemente a[1], a[2],…, a[n-1] . Se caut a elementul cel mai mic din acest sub sir
 si se interschimb a cu a[1]  s.a.m.d., p^ an a c^ and sub sirul va cont ine un singur element.
1algorithm Sortarea prin select ia minimului
2begin
3integer i, j, m, n
4real a[n], aux
5read n, a
6for i = 0 to n – 2 do
7m = i
8for j = i + 1 to n – 1 do
9 if a[m] > a[j] then
10 m = j
11 end if
12end for
13if m != i then
14 aux = a[m]
15 a[m] = a[i]
16 a[i] = aux
17end if
18end for
19write a
20end
De exemplu, consider am urm atorul  sir pe care ne propunem s a-l sort am cresc ator:
9, 4, 8, 10, 2, 3, 7, 0.
Pas 1: Se determin a indicele elementului minim, m = 7  si se interschimb a elementele a[0]  sia[7] .
S irul devine 0, 4, 8, 10, 2, 3, 7, 9.
Pas 2: Se determin a indicele elementului minim din sub sirul a[1..7] ,m = 4  si se interschimb a elemen-
telea[1]  sia[4] .
S irul este acum 0, 2, 8, 10, 4, 3, 7, 9.
Pas 3: Se determin a indicele elementului minim din sub sirul a[2..7] ,m = 5  si se interschimb a elemen-
telea[2]  sia[5] .
S irul devine 0, 2, 3, 10, 4, 8, 7, 9.
Pas 4: Se determin a indicele elementului minim din sub sirul a[3..7] ,m = 4  si se interschimb a elemen-
telea[3]  sia[4] .
Noul  sir este 0, 2, 3, 4, 10, 8, 7, 9.
Pas 5: Se determin a indicele elementului minim din sub sirul a[4..7] ,m = 6  si se interschimb a elemen-
telea[4]  sia[6] .
S irul devine 0, 2, 3, 4, 7, 8, 10, 9.
Pas 6: Se determin a indicele elementului minim din sub sirul a[5..7] ,m = 5 ; nu are loc nicio in-
terschimbare.
Pas 7: Se determin a indicele elementului minim din sub sirul a[6..7] ,m = 7  si se interschimb a elemen-
telea[6]  sia[7] .
2

Algoritmi  si complexitate Curs 5
S irul devine 0, 2, 3, 4, 7, 8, 9, 10 , care este complet sortat cresc ator.
1.1.1 Vericarea corectitudinii
S a ar at am c a proprietatea
Inv1 =fa[0]a[1]


a[i-1]  si a[i-1] a[j],8j = i,…, n – 1 g
este invariant a pentru ciclul fordup ai. Init ial,i = 0 , deciInv1 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[n-1] , care apoi se interschimb a cu elementul a[i] . Un invariant pentru ciclul interior
este deci
Inv2 =fa[m]a[k], k = i,…, j – 1 g,
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,…, n – 1 g. A sadar,
a[0]a[1]


a[i]  sia[i]a[j],8j = i + 1,…, n – 1 .
Cumieste 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, deoarce
i = n – 1  sia[0]a[1]


a[n-2]  sia[n-2]a[n-1] .
Pentru ecare dintre cele dou a cicluri for, variabila contor de iterat ie este incrementat a la ecare
iterat ie, deci pot  identicate funct ii de terminare corespunz 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 continuare nu vor mai  ^ ndeplinite, execut ia algoritmului ^ ncheindu-se.
A sadar, algoritmul se va termina^ ntr-un num ar nit de pa si, demonstr^ andu-se astfel total corectitudinea
algoritmului.
1.1.2 Analiza complexit at ii
Num arul de comparat ii (pasul 9) 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 (3 atribuiri: pa sii 14,
15, 16 ), 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 Sortarea prin select ia elementului maxim
Metoda este similar a precedentei, doar c a presupune determinarea elementului maxim al tabloului, deci a
indicelui Mpentru care a[i] < a[M],8i = 0, 1,…, n – 1 . Apoi sunt interschimbate elementele
a[n-1]  sia[M] (elementul maxim este plasat pe ultima pozit ie ^ n  sir). Procedeul se repet a pentru
sub sirul format din elementele a[0], a[1],…, a[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.
3

Algoritmi  si complexitate Curs 5
1algorithm Sortarea prin select ia maximului
2begin
3integer i, j, M, n
4real a[n], aux
5read n, a
6for i = n – 1 downto 1 do
7M = i
8for j = 0 to i – 1 do
9 if a[M] < a[j] then
10 M = j
11 end if
12end for
13if M != i then
14 aux = a[M]
15 a[M] = a[i]
16 a[i] = aux
17end if
18end for
19write a
20end
Desigur, clasa de complexitate a algoritmului este tot ( n2).
2 Sortarea prin insert ie
2.1 Sortarea prin insert ie direct a
Metoda const a ^ n determinarea pozit iei corecte a ec arui element a[i] , ^ ncep^ and cu al doilea (cu a[1] ),
^ n sub sirul care ^ l precede, a[0]a[1]…a[i-1] , deja ordonat. C autarea pozit iei lui a[i] se
realizeaz a folosind algoritmul de c autare secvent ial a. Astfel, a[i] se compar a cu a[i-1] ,a[i-2] , . . . ,
p^ an a c^ and se g ase ste un element a[j] , ^ n sub sirul deja ordonat, astfel ^ nc^ at a[j]a[i] . Se insereaz a
elementul a[i] dup aa[j] , nu ^ nainte de a deplasa elementele a[i-1] ,a[i-2] , . . . ,a[j+1] cu o pozit ie
la dreapta.
De exemplu, consider am  sirul de sortat: 5, 2, 1, 4, 3, 0 .
Pas 1: Primul element pentru care se caut a pozit ia corect a este 2. Sub sirul care ^ l precede este format
doar din elementul 5. Astfel singura comparat ie este^ ntre cele dou a elemente. Cum 2 < 5 , se deplaseaz a
elementul 5cu o pozit ie la dreapta  si elementul 2se plaseaz a pe pozit ia corect a.
Noul  sir este 2, 5, 1, 4, 3, 0 .
Pas 2: Se caut a pozit ia elementului 1^ n sub sirul 2, 5 . Cum ambele elemente ale sub sirului sunt mai
mari dec^ at 1, acestea sunt deplasate cu o pozit ie la dreapta.
S irul devine 1, 2, 5, 4, 3, 0 .
Pas 3: Se caut a pozit ia elementului 4^ n sub sirul 1, 2, 5 . Cum doar elementul 5al sub sirului este mai
mare dec^ at 4, acesta va  deplasat cu o pozit ie la dreapta.
S irul este 1, 2, 4, 5, 3, 0 .
Pas 4: Se caut a pozit ia elementului 3^ n sub sirul 1, 2, 4, 5 . Cum doar elementele 4 si5ale sub sirului
sunt mai mari dec^ at 3, acestea vor  deplasate cu o pozit ie la dreapta.
S irul este acum 1, 2, 3, 4, 5, 0 .
Pas 5: Se caut a pozit ia elementului 0^ n sub sirul 1, 2, 3, 4, 5 . Cum toate elementele sub sirului sunt
4

Algoritmi  si complexitate Curs 5
mai mari dec^ at 0, acestea vor  deplasate cu o pozit ie la dreapta.
S irul sortat este 0, 1, 2, 3, 4, 5 .
Se observ a c a, pe parcursul sort arii,  sirul este ^ mp art it (imaginar) ^ n dou a subtablouri: sub sirul sortat
a[0], a[1], …, a[i-1] , ^ n care urmeaz a s a e inserat elementul curent a[i]  si secvent a nesortat a
a[i+1], a[i+2], …, a[n-1] , din care urmeaz a s a se extrag a elemente ce vor  inserate pe pozit iile
corecte ^ n secvent a sortat a.
1algorithm Sortarea prin insert ie direct a
2begin
3integer n, i, j
4real a[n], aux
5read n, a
6for i = 1 to n – 1
7j = i – 1
8aux = a[i]
9while j >= 0 && aux < a[j]
10 a[j+1] = a[j]
11 j = j – 1
12end while
13a[j+1] = aux
14end for
15write a
16end
2.1.1 Vericarea corectitudinii
S a ar at am c a
Inv1 =fa[0]a[1]


a[i-1]g
este un invariant pentru ciclul fordup ai(elementele  sirului sortat, a[0],…, a[i-1] , sunt elementele
 sirului original de la 0lai-1, permutate). Init ial, i = 1 , deci precondit ia implic a faptul c a  sirul format
dintr-un singur element poate  considerat sortat cresc ator. S a ar at am c a proprietatea r am^ ane adev arat a
prin execut ia prelucr arilor din ciclu for.
Fie proprietatea
Inv2 =fa[0]a[1]


a[j]  si auxa[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 intrarea ^ n
ciclu,j = i – 1, aux = a[i] = a[j+1] , iar  sirul a[0]a[1]…a[i-1] este deja ordonat,
deci proprietatea este adev arat a la intrarea ^ n ciclu. Apoi, dac a aux < a[j] , dina[j+1] = a[j]
rezult a c a aux < a[j] = a[j+1] …a[i] . Dup a execut ia prelucr arii j = j – 1 ,a[0]a[1]



 a[j]  siaux < a[j+1] = a[j+2] …a[i] . DeciInv2 este un invariant pentru ciclul
while .
La sf^ ar situl buclei while este adev arat a una dintre relt 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 deoarce 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 algoritmului de sortare
prin select ia minimului, consider^ and funct ia de terminare pentru ciclul exterior t(k) =nik, iar pentru
5

Algoritmi  si complexitate Curs 5
ciclul interior consider am
t(k) =(
jk+ 1;dac a aux < a [jk]
0; dac a auxa[jk]
2.1.2 Analiza complexit at ii
At^ at num arul comparat iilor, c^ at  si cel al mut arilor depinde de distribut ia init ial a a elementelor ^ n
secvent  a. ^In cazul cel mai favorabil, pentru ecare i = 1, 2,…, n – 1 , 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 comparat iile  si mut arile, 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,…, n – 1 , au locicomparat ii  si i + 2 mut ari.
Obt inem o margine superioar a a 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).
2.2 Sortarea prin insert ie cu pas variabil
Metoda a fost introdus a de Donald L. Shell, ^ n anul 1959  si este cunoscut a  si sub numele de sortare prin
mic sorarea incrementului saushellsort . Ideea metodei este de a sorta elementele vectorului pe grupe,
ecare grup a av^ and elementele distant ate la un anumit pas h. Acest proces poart a numele de h-sortare .
Dac a cei tincrement i (pa si) sunt h1,h2, . . .ht, cuht= 1 sihi+1< h i, ecare hi-sortare se poate
implementa ca  si o sortate prin insert ie direct a. Exist a mai multe modalit at i de a alege increment ii
(pa sii), de alegerea acestora depinz^ and performant a algoritmului. Increment ii pot  ale si dup a o putere
a lui 2 sau putem folosi un tablou de increment i cu valori descresc atoare, ultima dintre acestea ind
obligatoriu 1. Pentru 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 incrementul al ( i1){lea
+ 1. Sunt multe alte secvent e de increment i care pot conduce la algoritmi de sortare mai ecient i. De
exemplu, Sedgewick propune secvent a
1, 8, 23, 77, 281, … (4k+1+ 3
2k+ 1; k0, la care se adaug a incrementul 1).
Algoritmul corespunz ator are o performant  a de O(n4=3), ^ n cazul cel mai defavorabil.
Anumite secvent e de increment i ar trebui evitate, av^ and performant e slabe. Un 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.
6

Algoritmi  si complexitate Curs 5
S a consider am un exemplu. Fie  sirul
10, 22, 16, 45, 34, 48, 7, 65, 19, 51, 5, 20, 43, 31, 56
pentru care ne propunem s a folosim algoritmul de sortare prin mic sorarea incrementului folosind secvent a
de increment i 7, 4, 1 .
Pas 1: Grupele de sortat, la distant a de 7pa si sunt:f10, 65, 56g,f22, 19g,f16, 51g,f45, 5g,
f34, 20g,f48, 43g,f7, 31g. Sortate prin inserare direct a, devin: f10, 56, 65g,f19, 22g,f16,
51g,f5, 45g,f20, 34g,f43, 48g,f7, 31g.
Noul tablou este: 10, 19, 16, 5, 20, 43, 7, 56, 22, 51, 45, 34, 48, 31, 65 .
Pas 2: Grupele de sortat, la distant a de 4pa si sunt:f10, 20, 22, 48g,f19, 43, 51, 31g,f16, 7,
45, 65g,f5, 56, 34g. Grupele sortate prin insert ie direct a: f10, 20, 22, 48g,f19, 31, 43, 51g,
f7, 16, 45, 65g,f5, 34, 56g.
Tabloul devine: 10, 19, 7, 5, 20, 31, 16, 34, 22, 43, 45, 56, 48, 51, 65 .
Pas 3: Sortarea la distant a de 1pas duce la sortarea ^ ntregului tablou, de fapt ind vorba de sortarea
prin insert ie direct a aplicat a ^ ntregului tablou.
Avantajul metodei const a ^ n faptul c a elementele sunt mutate mai repede mai aproape de pozit iile
lor corecte, sortarea realiz^ andu-se la distant e mai mari.
1algorithm Sortarea prin insert ie cu pas variabil
2begin
3integer n, i, j, h
4real a[n], aux
5read n, a
6h = 1
7while h < n/3 do
8h = 3 * h + 1 //sirul de incrementi sugerat de Knuth
9end while
10while h >= 1 do
11for i = h to n – 1 do
12 aux = a[i]
13 j = i
14 while j >= h && a[j-h] > aux do
15 a[j] = a[j-h]
16 j = j – h
17 end while
18 a[j] = aux
19end for
20h = h / 3
21end while
22write a
23end
3 Sortarea prin interschimbare
Ne vom opri ^ n aceast a sect iune doar asupra metodei de sortare prin interschimb ari succesive ale elemen-
telor vecine ce nu sunt ^ n ordinea corect a. Interschimb arile au loc p^ an a c^ and elementele vectorului sunt
complet ordonate. Aceast a variant a de sortare mai poart a numele de metoda bulelor saububblesort .
Metoda bulelor const a ^ n compararea elementelor a[i]  sia[i+1] ; dac aa[i] < a[i+1] , atunci se
trece la compararea lui a[i+1] cua[i+2] , dac a nu, se interschimb a a[i] cua[i+1]  si apoi se compar a
7

Algoritmi  si complexitate Curs 5
a[i+1] cua[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  s.a.m.d. 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.
1algorithm Sortarea1 prin interschimbarea elementelor vecine
2begin
3integer n, i, j
4real a[n], aux
5read n, a
6for i = n – 1 downto 1 do
7for j = 0 to i – 1 do
8 if a[j] > a[j+1] then
9 aux = a[j]
10 a[j] = a[j+1]
11 a[j+1] = aux
12 end if
13end for
14end for
15write a
16end
S a consider am un exemplu. S irul de sortat este
89, 45, 68, 90, 29, 34, 17.
Pas 1:
89$45 68 90 29 34 17 (prin \$" am indicat o interschimbare)
45 89$68 90 29 34 17
45 68 89 90$29 34 17
45 68 89 29 90 $34 17
45 68 89 29 34 90 $17
45 68 89 29 34 17 90
La nalul primului pas, cel mai mare element al  sirului este ^ n pozit ia nal a  si anume, pe ultima pozit ie
a  sirului. Acesta nu va mai face parte din subsecvent a ce va  parcurs a ^ n continuare.
Pas 2:
45 68 89$29 34 17
45 68 29 89$34 17
45 68 29 34 89 $17
45 68 29 34 17 89
La nalul celui de-al doilea pas, cel mai mare element al sub sirului este ^ n pozit ia nal a  si anume, pe
penultima pozit ie a  sirului init ial. Acesta nu va mai face parte din subsecvent a ce va  parcurs a ^ n
continuare.
Pas 3:
45 68$29 34 17
45 29 68$34 17
45 29 34 68$17
45 29 34 17 68
La nalul acestui pas, 68se va a
a pe pozit ia corect a ^ n  sirul sortat.
Pas 4:
45$29 34 17
29 45$34 17
8

Algoritmi  si complexitate Curs 5
29 34 45$17
29 34 17 45
Elementul 45este pe pozit ia sa nal a ^ n  sirul sortat.
Pas 5:
29 34$17
29 17 34
Elementul 34este pe pozit ia sa nal a ^ n  sirul sortat.
Pas 6:
29$17
17 29
^In acest moment, ultimele dou a elemente ale  sirului sunt pe pozit iile lor corecte,  sirul ind sortat ^ n
^ ntregime: 17, 29, 34, 45, 68, 89, 90 .
3.1 Vericarea corectitudinii
Consider am proprietatea
Inv1 =fa[j]a[k], k = 0,…, j g.
S a ar at am c a aceast a proprietate este invariant a pentru ciclul interior ( for j ). La intrarea ^ n ciclu, ( j =
0), proprietatea este adev arat a, deoarece a[0]a[0] . Presupunem c a proprietatea este adev arat a la
^ nceputul iterat iei. Dac a a[j] > a[j+1] atunci se realizeaz a interschimbarea elementelor  si acestea vor
^ n ordinea a[j] < a[j+1] , iar dac a a[j]a[j+1] , nu se efectueaz a interschimb ari, dar proprietatea
este adev arat a. A sadar proprietatea Inv1 r am^ ane adev arat a la sf^ ar situl iterat iei. Dup a incrementarea
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[n-1], cu a[i+1] a[j], j = 0,…, i g.
Proprietatea este invariant a pentru ciclul exterior ( for i ): la intrarea ^ n ciclu, i = n – 1 , deci propri-
etatea 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[n-1], cu a[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.
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 obt ine
TM(n) =3n(n1)
2:
9

Algoritmi  si complexitate Curs 5
A sadar,
0TM(n)3n(n1)
2:
Cum T(n) =TC(n) +TM(n), obt inem c a
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.
1algorithm Sortarea2 prin interschimbarea elementelor vecine
2begin
3integer n, i, m
4bool schimb
5real a[n], aux
6read n, a
7m = n
8repeat
9schimb = false
10for i = 0 to m – 2 do
11 if a[i] > a[i+1] then
12 aux = a[i]
13 a[i] = a[i+1]
14 a[i+1] = aux
15 schimb = true
16 end if
17end for
18m = m – 1
19until schimb == false
20write a
21end
Pentru acest algoritm, num arul de comparat ii ^ n cazul cel mai favorabil este
TC(n) =n1;
iar ^ n cazul cel mai defavorabil este acela si ca ^ n cazul algoritmului precedent,
TC(n) =n(n1)
2:
^In ceea ce prive ste num arul mut arilor, se obt ine aceea si estimare:
0TM(n)3n(n1)
2:
A sadar,
n1T(n)2n(n1):
Obt inem c a T(n)2
(n)  siT(n)2O(n2).
10

Algoritmi  si complexitate Curs 5
O metod a de sortare este stabil a dac a p astreaz a ordinea relativ a a elementelor de aceea si valoare.
Aceast a proprietate presupune ca elementele de valoare egal a s a apar a ^ n  sirul sortat ^ n aceea si ordine
ca ^ n secvent a init ial a. Algoritmii de sortare prin insert ie  si prin interschimbarea elementelor vecine
sunt stabile, iar cel de sortare prin select ie nu este stabil.
Metodele de sortare prezentate sorteaz a elementele \pe loc", f ar a a  necesare tablouri suplimentare.
Dup a cum am v azut, metodele elementare de sortare au complexitate p atratic a^ n cel mai defavorabil
caz. Acestea sunt eciente doar pentru tablouri cu un num ar relativ mic de elemente. De ret inut este
faptul c a algoritmul de sortare prin insert ie este avantajos dac a tabloul este aproape de cazul cel mai
favorabil, iar cel de sortare prin select ie este avantajos c^ and se dore ste sortarea part ial a a unui tablou.
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] D. Zaharie, Introducere ^ n Proiectarea  si Analiza Algoritmilor , Ed. Eubeea, 2008.
11