Analiza Algoritmilor

Problema 1:

Consideram algoritmii InsertionSort, BubbleSort si MergeSort din Tema 1.

Cerinte: alegeti unul dintre algoritmii InsertionSort si BubbleSort si aratati ca este partial corect. Aratati ca algoritmul MergeSort este partial corect. Pentru functia 'Merge' considerati varianta dezvoltata de voi in Tema 1 .

Demonstratie prin deductie directa

I=Zn Pi(A,n)= A  vector cu n elemente

O=Zn Po(A,n)= A - vector sortat cu n elemente

Op 1. La fiecare ciclu din primul for (pentru i=k) se aduce pe pozitia A[k] cel mai mic element din subvectorul A[k:n-1]

Dem:

Fie i=k.

Pornind de la pozitia n-1, va compara fiecare element cu cel dinaintea lui si le va interschimba, daca acesta este mai mic. Asfel se va aduce in pozitia k elementul cel mai mic din subvectorul A[k :n-1]

Op 2. Efectuand Op 1 pentru i=0 : n-1 va rezulta un vector ce are pe pozitia i cel mai mic din subvectorul A[i,n-1] A=[p0,p1,p2,p3,p4,p5&.pn-1] cu proprietatea ca:

pi=min(pi:n-1) pi pj , i<j p0 p1 &pi &pn-1 vectorul este sortat

BubbleSort este partial corect

analiza algoritmilor tema 2