curs 5 - agendadlucanu/cursuri/ap/resurse/curs5.pdf · "heap sort" (sortare prin selectie...

Dorel Lucanu Algoritmica si programare

Curs 5 - Agenda

sortare interna“buble sort”sortare prin insertiesortare pri selectie

naivasistematica (“heap sort”)

sortare prin interclasare (“merge sort”)sortare rapida (“quick sort”)

cautarein liste liniarecautare binara – aspectul dinamicarbori AVL

Dorel Lucanu Algoritmica si programare

Problema sortarii

Forma 1Intrare: n, (R0, . . . , Rn-1) cu cheile

k0, . . . , kn-1Iesire: (R’0, . . . , R’n-1) astfel incit(R’0, . . . , R’n-1) este o permutare a (R0, . . . , Rn-1 ) si R’0.k0 ≤ . . . ≤ R’n-1.kn-1

Forma 2Intrare: n, (v0, . . . , vn-1)Iesire: (w0, . . . , wn-1) astfel incit(w0, . . . , wn-1) este o permutare a (v0, . . . , vn-1), si w0 ≤ . . . ≤ wn-1

structura de datearray a[0..n-1]a[0] = v0, . . . , a[n-1] = vn-1

Dorel Lucanu Algoritmica si programare

Bubble sort I

idee:(∀i) 0 ≤ i < n-1 ⇒ a[i] ≤ a[i+1]

algoritmprocedure bubbleSort (a, n)begin

ultim ← n-1while ultim > 0 do

ntemp ← ultim – 1ultim ← 0for i ← 0 to ntemp do

if a[i] > a[i+1]then swap(a[i], a[i+1])

ultim ← iend

Dorel Lucanu Algoritmica si programare

Bubble sort II

exempluanaliza

cazul cel mai nefavorabila[0] > a[1] > ... > a[n-1]TbubleSort(n) = O(n2)

Dorel Lucanu Algoritmica si programare

Sortare prin insertie directa I

ideepresupunem a[0..i-1] sortatinsereaza a[i] astfel incit a[0..i] devine sortat

algoritmprocedure insertSort(a, n)begin

for i ← 1 to n-1 doj ← i – 1temp ← a[i]while ((j ≥ 0) and (a[j] > temp)) do

a[j+1] ← a[j]j ← j – 1

if (a[j+1] ≠ temp) then a[j+1] ←temp

end

Dorel Lucanu Algoritmica si programare

Sortare prin insertie directa II

exempluanaliza

cazul cel mai nefavorabila[0] > a[1] > ... > a[n-1]TinsertSort(n) = O(n2)

Dorel Lucanu Algoritmica si programare

Sortare prin selectie

ideea de bazapasul curent: selecteaza un element si-lduce pe pozitia sa finala din tabloul sortatrepeta pasul curent pana cnd toateelementele ajung pe locurile finale

Dorel Lucanu Algoritmica si programare

Sortare prin selectie naiva

idee(∀i ) 0 ≤ i < n ⇒ a[i] = max{a[0],…,a[i]}

algoritmprocedure naivSort(a, n)begin

for i ← n-1 downto 0 doimax ← ifor j ← i-1 downto 0 do

if (a[j] > a[imax])then imax ← j

if (i ≠ imax) then swap(a[i], a[imax])end

complexitatea timp toate cazurile: TnaivSort(n) = Θ(n2)

Dorel Lucanu Algoritmica si programare

"Heap sort" (sortare prin selectie sistematica)

etapa Iorganizeaza tabloul ca un max-heapinitial tablou satisface proprietatea max-heap incepand cu n/2 introduce in max-heap elementele de pepozitiile n/2-1, n/2 -1, …, 1, 0

etapa IIselecteaza elementul maxim si-l duce la locul lui prin interschimbare cu ultimulmicsoreaza cu 1 si apoi reface max-heapulrepeta pasii de mai sus pana cand toateelementele ajung pe locul lor

Dorel Lucanu Algoritmica si programare

Operatia de introducere in heap al t-lea

procedure insereazaAlTlea(a, n, t)begin

j ← theap ← falsewhile ((2*j+1 < n) and not heap) do

k ← 2*j+1if ((k < n-1) and (a[k] < a[k+1]))then k ← k+1if (a[j] < a[k])then swap(a[j], a[k])

j ← kelse heap ← true

end

Dorel Lucanu Algoritmica si programare

"Heap sort" (sortare prin selectie sistematica)

procedure heapSort(a, n)begin

// construieste maxheap-ulfor t ← (n-1)/2 downto 0 do

insereazaAlTlea(a, n, t)// eliminar ← n-1while (r > 0) do

swap(a[0], a[r])insereazaAlTlea(a, r, 0)r ← r-1

end

Dorel Lucanu Algoritmica si programare

"Heap sort" - complexitate

formarea heap-ului (pp. )

eliminare din heap si refacere heap

complexitate algoritm de sortare

)1(222)1(2 11

0

+−=−− +−

=∑ kik kik

i

12 −= kn

42)2(22 11

0

+−= +−

=∑ kik

i

ki

)log(2log2)(heapSort nnOnnnnT =−=

Dorel Lucanu Algoritmica si programare

Timpul de executie empiric

Intel Pentium III 1.00 Ghz

0.01600.57800.40603.094010000

0.01600.35900.25001.95308000

0.01600.09300.06300.48404000

0.00000.03200.01500.11002000

0.00000.01500.00000.03101000

0.00000.00000.00000.0000100

0.00000.00000.00000.000010

heapSortnaivSortinsertSortbubbleSortn

Dorel Lucanu Algoritmica si programare

Paradigma divide-et-impera

P(n): problema de dimensiune nbaza

daca n ≤ n0 atunci rezolva P prin metodeelementare

divide-et-imperadivide P in a probleme P1(n1), ..., Pa(na) cu ni ≤ n/b, b > 1rezolva P1(n1), ..., Pa(na) in aceeasimaniera si obtine solutiile S1, ..., Sa

asambleaza S1, ..., Sa pentru a obtinesolutia S a problemei P

Dorel Lucanu Algoritmica si programare

Paradigma divide-et-impera: algoritm

procedure DivideEtImpera(P, n, S)begin

if (n <= n0)then determina S prin metode

elementareelse imparte P in P1, ..., Pa

DivideEtImpera(P1, n1, S1)...DivideEtImpera(Pa, na, Sa)Asambleaza(S1, ..., Sa, S)

end

Dorel Lucanu Algoritmica si programare

Sortare prin interclasare (Merge sort)

generalizare: a[p..q]baza: p ≥ q

divide-et-imperadivide: m = [(p + q)/2]subprobleme: a[p..m], a[m+1..q]

asamblare: interclaseaza subsecventele sortatea[p..m] si a[m+1..q]

initial memoreaza rezultatul interclasarii in tempcopie din temp[0..p+q-1] in a[p..q]

complexitate:timp : T(n) = O(n log n) (T(n) = 2T(n/2)+n)spatiu suplimentar: O(n)

Dorel Lucanu Algoritmica si programare

Interclasarea a doua secvente sortate

problema:date a[0] ≤ a[1] ≤ … ≤ a[m-1],

b[0] ≤ b[1] ≤ … ≤ b[n-1],sa se construiasca c[0] ≤ c[1] ≤ … ≤ c[m+n-1]a.i. (∀ k)((∃i)c[k]=a[i]) ∨ (∃j)c[k]=b[j])

solutiainitial: i ← 0, j ← 0, k ← 0pasul curent:

daca a[i] ≤ b[j]atunci c[k] ← a[i], i ← i+1 daca a[i] > b[j]atunci c[k] ← b[j], j ← j+1k ← k+1

conditia de terminare: i > m-1 sau j > n-1daca e cazul, copie elementele din tabloul neterminat

Dorel Lucanu Algoritmica si programare

Sortare rapida (Quick sort)

generalizare: a[p..q]baza: p ≥ q

divide-et-imperadivide: determina k intre p si q prininterschimbari a.i. dupa determinarea lui kavem:

p ≤ i ≤ k ⇒ a[i] ≤ a[k]k < j ≤ q ⇒ a[k] ≤ a[j]

subprobleme: a[p..k-1], a[k+1..q]asamblare: nu exista

xkp q

≤ x ≥ x

Dorel Lucanu Algoritmica si programare

Quick sort: partitionare

initial:x ← a[p] (se poate alege x arbitrar din a[p..q])i ← p+1 ; j ← q

pasul curent:daca a[i] ≤ x atunci i ← i+1daca a[j] ≥ x atunci j ← j-1daca a[i] > x > a[j] si i < j atunci

swap(a[i], a[j])i ← i+1j ← j-1

terminare:conditia i > joperatii k ← i-1

swap(a[p], a[k])

Dorel Lucanu Algoritmica si programare

Cautare

in liste liniarecautare binara – aspectul dinamicarbori AVL

Dorel Lucanu Algoritmica si programare

Problema cautarii

aspectul staticU multime universS ⊂ U

operatia de cautare:Instanta: a ∈ UIntrebare: a ∈ S?

aspectul dinamicoperatia de inserareIntrare: x ∈ U, SIesire: S ∪ {x}operatia de stergereIntrare: x ∈ U, SIesire: S − {x}

Dorel Lucanu Algoritmica si programare

Cautare in liste liniare - complexitate

O(1)O(n)O(n)Liste inlantuite

O(n)O(n)O(log n)TablouriListaliniaraordonata

O(1)O(1)O(n)Liste inlantuite

O(n)O(1)O(n)TablouriListaliniara

StergereInserareCautareImplementareTip de date

Dorel Lucanu Algoritmica si programare

Cautare binara – aspect static - context

multimea univers este total ordonata: (U, ≤)structura de data utilizata:

array s[0..n-1]s[0]< ... < s[n-1]

Dorel Lucanu Algoritmica si programare

Cautare binara – aspect static - algoritm

function Poz(s, n, a)begin

p ← 0; q ← n-1m ← [(p+q)/2]while (s[m] != a && p < q) do

if (a < s[m])then q ← m-1else p ← m+1m ← [(p+q)/2]

if (s[m] = a)then return melse return -1;

end

Dorel Lucanu Algoritmica si programare

Arborele binar asociat cautarii binare

T(p,q)m

T(p,m-1) T(m+1,q)

T = T(0,n-1)

n = 6

1 3 5

4

2

0

Dorel Lucanu Algoritmica si programare

Cautare binara: aspect dinamic

arbore binar de cautarearbore binar cu proprietatea ca pentruorice nod v, valorile memorate in subarborele la stinga lui v

<valoarea din v

< valorile memorate in subarborele la

dreapta lui v.

Dorel Lucanu Algoritmica si programare

Cautare binara: aspect dinamic - cautare

function Poz(t, a)begin

p ← twhile (p != NULL && p->val != a) do

if (a < p->val)then p ← p->stgelse p ← p->drp

return pend

Dorel Lucanu Algoritmica si programare

Cautare binara: aspect dinamic - inserare

procedure insArbBinCautare(t, x)begin

if (t = NULL)then t ← (x) /*(x) e arborele cu 1 nod */else p ← t

while (p != NULL) dopredp ← pif (x < p->val) then p ← p->stgelse if (x > p->val)then p ← p->drpelse p ← NULL

if (predp->val != x) thenif (x < predp->val) then adauga x ca fiu stinga a lui predpelse adauga x ca fiu dreapta a lui predp

end

Dorel Lucanu Algoritmica si programare

Cautare binara: aspect dinamic - eliminare

se cauta pentru x in arborele t; daca-l gasestese disting cazurile:• cazul 1: nodul p care memoreaza x nu are fii• cazul 2: nodul p care memoreaza x are un

singur fiu• cazul 3: nodul p care memoreaza x are ambii

fii– determina nodul q care memoreaza cea

mai mare valoare y mai mica decit x(coboara din p la stinga si apoi coboara la dreapta cit se poate)

– interschimba valorile din p si q– sterge q ca in cazul 1 sau 2

Dorel Lucanu Algoritmica si programare

Cautare binara: aspect dinamic - eliminare

cazul 1 sau 2procedure elimCaz1sau2(t, predp, p)begin

if (p = t)then t devine vid sau unicul fiu al lui t devine

radacinaelse if (p->stg = NULL)

then inlocuieste in predp pe p cu p->drpelse inlocuieste in predp pe p cu p->stg

end

Dorel Lucanu Algoritmica si programare

Cautare binara: aspect dinamic - eliminare

procedure elimArbBinCautare(t, x)begin

if (t != NULL)then p ← t

while (p != NULL && p->val != x) dopredp ← pif (x < p->val) then p ← p->stgelse p ← p->drp

if (p != NULL)if (p->stg = NULL || p->drp = NULL)then elimCaz1sau2(t, predp, p)else q ← p->stg; predq ← pwhile (q->drp != NULL)

predq ← q; q ← q->drpp->val ← q->valelimCaz1sau2(t, predq, q)

end

Dorel Lucanu Algoritmica si programare

Degenerarea cautarii binare in cautare liniara

30 50

40

10

0

20

30 50

40

20

30 50

400

20

30

40

20

30

40

20

35

30

40

20

35

32

elimina(10) elimina(0) elimina(50)

insereaza(35) insereaza(32)

Dorel Lucanu Algoritmica si programare

Arbori AVL

un arbore binar de cautare t este un arboreAVL-echilibrat daca pentru orice virf v,

h(v→stg) − h(v→drp)≤ 1Lemat AVL-echilibrat ⇒ h(t) = Θ(log n).

Dorel Lucanu Algoritmica si programare

Arbori AVL

TeoremaClasa arborilor AVL-echilibrati este O(log n)

stabila.algoritmul de inserare

nodurile au memorate si factorii de echilibrare (∈ {−1, 0, 1})se memoreaza drumul de la radacina la nodul adaugat intr-o stiva (O(log n))se parcurge drumul memorat in stiva in sens invers si se reechilibeaza noduriledezichilibrate cu una dintre operatiile: rotatie stinga/dreapta simpla/dubla(O(log n)).

Dorel Lucanu Algoritmica si programare

Rotatii

x

y x

y

A

A

B BC

C

Rotatie dreapta simpla

Rotatie dreapta dubla

x

y

z

x

y

zA

AB

BC

C

D

D