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


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


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


Bubble sort II

exempluanaliza

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


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


Sortare prin insertie directa II

exempluanaliza

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


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


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)


"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


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


"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


"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 =−=


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


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


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


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)


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


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


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])


Cautare

in liste liniarecautare binara – aspectul dinamicarbori AVL


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}


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


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]


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


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


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.


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


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


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



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



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


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)


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


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


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

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

Documents