Consultaii Admitere 15.02.2014

2. Algoritmi elementari (II)

2.1. Metode de ordonare metoda bulelor metoda inseriei metoda seleciei metoda numrrii

2.2. Interclasare

2.3. Metode de cutare cutare secvenial cutare binar

2.4. Analiza complexitii unui algoritm (considernd criteriile de eficien durata de executare i spaiu de memorie utilizat)

2.4. Analiza complexitii unui algoritm

Aspecte de interes privind algoritmii corectitudine (n raport cu specificaia) eficien

Eficiena algoritmilor se refer la cantitatea de resurse utilizate, viznd timpul de execuie necesar spaiul de memorie utilizat

Complexitatea timp de execuie

Timpul de execuie al unui algoritm nu este constant, ci depinde de dimensiunea datelor (este o funcie de n, unde n = dimensiunea intrrii)

O estimare bun a timpului real de execuie o reprezint numrul de operaii elementare efectuate de algoritm. Aceast estimare o numim complexitate timp a algoritmului, notat T(n) (n = dimensiunea datelor)

ideea principal = cum crete timpul de execuie cu dimensiunea intrrii la limit? => intereseaz doar ordinul de mrime al lui T

se va lua n considerare operaia predominant a algoritmului

Complexitatea n cazul cel mai favorabil = numrul minim de operaii pentru o

dimensiune fixat a intrrii medie = numrul mediu de operaii pentru o dimensiune fixat a intrrii n cazul cel mai defavorabil = numrul maxim de operaii pentru o

dimensiune fixat a intrrii

Complexitatea spaiu de memorare - estimeaz cantitatea de memorie necesar algoritmului pentru a reine datele de intrare, rezultatele finale i intermediare.

Algoritmii in place - spaiu suplimentar constant not in place

2.1. Metode de ordonare

Metodele de ordonare vizeaz reorganizarea elementelor unei colecii (unui ir) aflate n memoria intern, astfel nct cheile asociate acestor elemente s fie ordonate cresctor (sau descresctor).

Din punct de vedere al complexitii, problema se reduce la sortarea cheilor.

Pentru simplificare, elementele (cheile) se consider a fi numere ntregi.

Specificarea problemei de ordonare (cresctoare)Date: sPrecondiii: s este un ir nevid de numere ntregiRezultate: s'Postcondiii: s' este o permutare a lui s, avnd elementele ordonate cresctor

Metoda bulelor

Idee: Se parcurge irul, comparndu-se fiecare dou elemente consecutive. n cazul n care acestea nu sunt n relaia de ordine dorit, se interschimb. Procesul se repet pn cnd orice dou elemente consecutive sunt n relaia de ordine dorit.

AlgoRythmics: http://www.youtube.com/watch?v=lyZQPjUT5B4

Complexitate: O( n2 ), algoritm in place

Metoda bulelor - Implementare C++

------------------------------------------------------------------------------------------struct sir{

int n; //lungimea siruluiint e[100]; //elementele

};

void ordonareMetodaBulelor(sir& s){

bool ordonat;int aux;

do{

ordonat = true; //presupunem sirul ordonatfor (int i = 0; i < s.n - 1; i++)

if (s.e[i] > s.e[i + 1]) //elementele nu se afla in relatia dorita

{ordonat = false;//interschimbamaux = s.e[i];s.e[i] = s.e[i + 1];s.e[i + 1] = aux;

}} while (!ordonat);

}------------------------------------------------------------------------------------------

Metoda bulelor - Implementare Pascal

------------------------------------------------------------------------type sir = record n:integer; e:array[1..100] of integer;end;

procedure ordonareMetodaBulelor(var s:sir);var ordonat:boolean; i,aux:integer;begin repeat ordonat := true; {presupunem sirul ordonat} for i := 1 to s.n-1 do if s.e[i] > s.e[i+1] {ordine nerespectata} then begin ordonat := false; {interschimbam} aux := s.e[i]; s.e[i] := s.e[i+1]; s.e[i+1] := aux; end; until ordonat;end; ------------------------------------------------------------------------

Metoda inseriei

Idee: Se parcurge irul de la al doilea la ultimul element. Fiecare element curent este inserat n subirul deja ordonat al elementelor anterioare acestuia, astfel nct subirul s rmn ordonat. Dup parcurgere, toate elementele vor fi n ordinea corect.

AlgoRythmics: http://www.youtube.com/watch?v=ROalU379l3U

Complexitate: O( n2 ), algoritm in place

Metoda inseriei - Implementare C++

------------------------------------------------------------------------------------------void ordonareMetodaInsertiei(sir& s){

for (int i = 1; i < s.n; i++){

int aux = s.e[i];int j = i;while (j > 0 && s.e[j - 1] > aux){

s.e[j] = s.e[j - 1];j--;

}if (j != i)

s.e[j] = aux;}

}------------------------------------------------------------------------------------------

Metoda inseriei - Implementare Pascal

------------------------------------------------------------------------procedure ordonareMetodaInsertiei(var s:sir);var aux,i,j:integer;begin for i:=2 to s.n do begin aux := s.e[i]; j := i; while(j > 1) and (s.e[j-1] > aux) do begin s.e[j] := s.e[j-1]; j := j-1; end; if ji then s.e[j] := aux; end;end;------------------------------------------------------------------------------------------

Metoda seleciei

Idee: Se caut elementul cu valoare minim din ir i se interschimb cu primul element. n subirul rmas, se caut cel mai mic element i se interschimb cu cel de-al doilea element, etc.

AlgoRythmics: http://www.youtube.com/watch?v=Ns4TPTC8whw

Complexitate: O( n2 ), algoritm in place

Metoda seleciei - Implementare C++

------------------------------------------------------------------------------------------void ordonareMetodaSelectiei(sir& s){

for (int i = 0; i < s.n - 1; i++){

int poz_min = i;for (int j = i + 1; j < s.n; j++) if (s.e[j] < s.e[poz_min])

poz_min = j; if (poz_min != i) {

int aux = s.e[i]; s.e[i] = s.e[poz_min]; s.e[poz_min] = aux;

}}

}------------------------------------------------------------------------------------------

Metoda seleciei - Implementare Pascal

-----------------------------------------------------------------------procedure ordonareMetodaSelectiei(var s:sir);var i,j,poz_min,aux:integer;begin for i:=1 to s.n-1 do begin poz_min := i; for j := i+1 to s.n do if s.e[j] < s.e[poz_min] then poz_min := j; if(poz_min i) then begin aux := s.e[i]; s.e[i] := s.e[poz_min]; s.e[poz_min] := aux; end; end;end;-----------------------------------------------------------------------------------------

Metoda numrrii

Idee: irul ce se dorete a fi ordonat trebuie s conin elemente distincte. Pentru fiecare element al irului, se afl numrul elementelor mai mici dect el, numr ce d poziia final a elementului considerat n irul ordonat.

AlgoRythmics: none

Complexitate: O( n2 ), algoritm not in place (spaiu suplimentar liniar)

Metoda numrrii - Implementare C++

------------------------------------------------------------------------void ordonareMetodaNumararii(sir& s){

sir s1 = s;for (int i = 0; i < s1.n; i++){

int nrMaiMici = 0;for (int j = 0; j < s1.n; j++) if (s1.e[j] < s1.e[i]) nrMaiMici++;s.e[nrMaiMici] = s1.e[i];

}}------------------------------------------------------------------------

Metoda numrrii - Implementare Pascal

------------------------------------------------------------------------------------------procedure ordonareMetodaNumararii(var s:sir);var s1:sir; i,j,nrMaiMici:integer;begin s1 := s; for i:=1 to s1.n do begin nrMaiMici := 0; for j:=1 to s1.n do if s1.e[j] < s1.e[i] then nrMaiMici:=nrMaiMici+1; s.e[nrMaiMici + 1] := s1.e[i]; end;end; ------------------------------------------------------------------------------------------

2.2. Interclasare

Fiind date dou colecii de date, ordonate cresctor (sau descresctor) n raport cu o cheie, se cere s se obin o colecie sortat n acelai mod, coninnd doar elementele celor dou colecii iniiale.

Pentru simplificare, vom considera, din nou, elementele celor dou colecii ca fiind reprezentate prin cheile acestora (numere ntregi).

Specificarea problemei de interclasareDate: s1, s2Precondiii: s1, s2 - iruri de numere ntregi ordonate cresctorRezultate: s3Postcondiii: s3 - ir de numere ntregi, ordonat cresctor, coninnd elementele irurilor s1 i s2 i numai acestea

Soluii posibile concatenarea celor dou iruri, urmat de sortarea irului rezultat -

ineficient generarea irului cerut printr-o singur parcurgere a irurilor

iniiale parcurgere secvenial a celor dou iruri date, simultan cu

generarea irului cerut - prin compararea a dou elemente din irurile de intrare se decide care dintre ele va fi adaugat n irul rezultat

complexitate O(n + m), unde n i m sunt dimensiunile celor dou iruri de interclasat

Interclasare - Implementare C++

------------------------------------------------------------------------------------------void interclasare(sir s1, sir s2, sir& s3){

int i = 0, j = 0, k = 0;while (i < s1.n && j < s2.n) {

if (s1.e[i] < s2.e[j]){

s3.e[k] = s1.e[i];k++;i++;

}else{

s3.e[k] = s2.e[j];k++;j++;

}}while (i < s1.n){

s3.e[k] = s1.e[i];k++;i++;

}while (j < s2.n){

s3.e[k] = s2.e[j];k++;j++;

}s3.n = k;

}------------------------------------------------------------------------------------------

Interclasare - Implementare Pascal

------------------------------------------------------------------------------------------procedure interclasare(s1,s2:sir; var s3:sir);var i,j:integer;begin i := 1; j := 1; s3.n := 0; while (i

2.3. Metode de cutare

Se consider un ir de nregistrri aflate n memoria intern. Se cere s se identifice o nregistrare avnd o valoare specificat pentru un anumit cmp (cheie de cutare). n cazul n care o astfel de nregistrare exist, se va returna poziia acesteia n ir, altfel se va returna o poziie invalid.

n cazul n care elementele coleciei sunt ordonate i nu exist nici o nregistrare cu cheia cerut, ar fi util s se precizeze i poziia pe care ar trebui inserat o astfel de nregistrare, cu pstrarea ordinii ntre elemente.

Pentru simplificare, vom considera nregistrrile reprezentate doar prin cheile acestora i cheile numere ntregi.

Variante cutare secvenial - ir oarecare (neordonat) cutare binar - ir ordonat

Cutare secvenial

Se caut un element ntr-un ir dat, returnndu-se poziia acestuia, n cazul n care a fost gsit i o poziie invalid, n cazul n care elementul nu aparine irului.

Specificarea problemei de cutare secvenialDate: s, xPrecondiii: s - ir de numere ntregi x - numr ntregRezultate: pPostcondiii: p - poziia pe care apare x n s, dac x aparine lui s o poziie invalid, altfel

Idee: Se parcurg, pe rnd, elementele irului, pn la gsirea elementului dorit sau pn la terminarea acestuia

Complexitate: O(n)

Cutare secvenial - Implementare C++

---------------------------------------------------------------------------------------int cautareSecventiala(sir s, int x){

int poz = 0;while (poz < s.n && s.e[poz] != x)

poz++;if (poz >= s.n) poz = -1;return poz;

}---------------------------------------------------------------------------------------

Cutare secvenial - Implementare Pascal

------------------------------------------------------------------------function cautareSecventiala(s:sir; x:integer):integer;var poz:integer;begin poz := 1; while (poz s.n then poz := -1; cautareSecventiala := poz;end;------------------------------------------------------------------------

Cutare binar

Se caut un element ntr-un ir ordonat dat, returnndu-se poziia acestuia, n cazul n care a fost gsit, sau poziia pe care ar trebui inserat n ir pentru ca irul s rmn ordonat, n caz contrar.

Specificarea problemei de cutare binarDate: s, xPrecondiii: s - ir ordonat de numere ntregi x - numr ntregRezultate: gasit, pPostcondiii: gsit = adevrat i p = poziia pe care apare x n s, sau gsit = false i p = poziia pe care ar trebui inserat x n s, pentru ca s s rmn ordonat

Idee: Se compar elementul cutat cu elementul aflat la mijlocul irului i, funcie de rezultatul comparrii, cutarea se continu doar ntr-o jumatate a irului.

Complexitate: O( log2 n )

Cutare binar - Implementare C++-----------------------------------------------------------------------------------------int cautareBinaraRecursiva(sir s, int x, bool& gasit){

gasit = false;if (x s.e[s.n - 1])

return s.n;else

return cautBinRec(s, x, 0, s.n - 1, gasit);}

-----------------------------------------------------------------------------------------int cautBinRec(sir s, int x, int st, int dr, bool& gasit){

if (st >= dr - 1){

if (x == s.e[dr])gasit = true;

return dr;}else{

int m = (st + dr) / 2;if (x

Cutare binar - Implementare Pascal

------------------------------------------------------------------------function cautareBinaraRecursiva(s:sir; x:integer; var

gasit:boolean):integer;begin gasit := false; if x s.e[s.n] then cautareBinaraRecursiva := s.n + 1 else cautareBinaraRecursiva := cautBinRec(s,x,1,s.n,gasit);end;

------------------------------------------------------------------------------------------function cautBinRec(s:sir; x,st,dr:integer; var

gasit:boolean):integer;var m:integer;begin if st >= dr - 1 then begin if (x = s.e[dr]) then gasit := true; cautBinRec := dr; end else begin m := (st + dr) div 2; if x