2.1 algoritmi si tehnici de programare avansata

Tabloul privit ca structură recursivă

Tablourile sunt structuri recursive, deoarece:

componentele unui tablou cu n dimensiuni sunt tot tablouri, dar cu n-1 dimensiuni;

orice zonă compactă a unui tablou

unidimensional este, de asemenea, un tablou unidimensional.

Această proprietate permite ca multe operaţii de prelucrare ale datelor conţinute în tablouri să se

poată realiza folosind algoritmi recursivi.  Varianta recursivă a algoritmului de cautare binarăAm studiat deja varianta

iterativă a algoritmului de cautare binară a unei valori într-un tablou ordonat.

Considerăm că dorim să căutăm în tabloul tab cu componente de tip double, componenta de valoare val  în zona

de tablou situata intre indicii inf si sup. În acest scop, putem folosi urmatoarea funcţie recursivă: (scrisă în Java):

static int cautBinRec(double tab[], double val, int inf, int sup){   if(inf>sup) return -1; // interval greşit   int k=(inf+sup)/2; // se ia indicele de la mijlocul zonei   if(val==tab[k]) return k; // s-a găsit elementul căutat   if(val<tab[k]) return cautBinRec(tab, val, inf, k-1); /* se

caută 

    valoarea val in jumătatea din stânga a zonei */   else return cautBinRec(tab, val, k+1, sup); /* se caută valoarea     val in jumatatea din dreapta a zonei */ }

Dacă s-a definit funcţia de mai sus, pentru căutarea aceleeaşi valori în întregul tablou se poate folosi funcţia:

static int cautBinRec(double tab[], double val) { 

  return cautBinRec(tab, val, 0, tab.length-1); }

Cele două funcţii de mai sus sunt testate în programul din fişierul CautBinRec.java.

Programele pot fi modificate cu usurinţă pentru cazul când

componentele tabloului în care se face căutarea sunt de alt tip primitiv sau sunt obiecte.

Se poate constata cu usurinţă ca varianta iterativă prezentata anterior a fost obtinută pornind de la cea recursivă,

înlocuindu-se invocările de funcţii recursive prin cicluri.Interclasarea a două tablouri ordonate

Fie două tablouri ordonate  tab1 de lungime m şi tab2 de lungime n. Prin interclasare se obtine un nou tablou tab3 de

lungime p=m+n, procedând astfel:   - se compară primele elemente din tab1 şi tab2 şi se transferă cel mai mic dintre ele în tab3;   - se continuă astfel, comparând la fiecare pas primele dintre

elementele încă netransferate din cele două tablouri şi punândul în tab3 pe cel mai mic dintre ele;   - după ce componentele din unul din cele două tablouri date s-au epuizat, se adaugă la tab3 toate

componentele rămase în celălalt tablou. Tabloul tab3, astfel obţinut, conţine elementele din cele două tablouri date puse în ordine.  Algoritmul de

interclasare a tablourilor tab1 si tab2 poate fi descris în pseudocod astfel:

  Fie date tablourile tab1 de lungime m si tab2 de lungime n;   Fie tabloul de iesire tab3 de lungime p=m+n;   i=0; j=0; k=0;   cât timp (i<m si j<n) {     dacă (tab1[i] precede lui tab2[j])       atunci {         tab3[k]=tab1[i]; 

        i=i+1;       }       altfel {         tab3[k]=tab2[j];         j=j+1;       }     k=k+1;   }   /* în acest moment componentele din unul din tablourile tab1 si tab2 s-au terminat */

  /* Daca mai există componente în tab1, se adaugă la tab3 */   cât timp (i<m) {      tab3[k]=tab1[i]; 

    i=i+1; k+1;   }

  /* Daca mai exista componente in tab2, se adauga la tab3 */   cât timp (j<n) {     tab3[k]=tab2[j];     j=j+1; k=k+1;   }

In fişierul Interclasare.java este dat un exemplu de aplicaţie în care se testează acest

algoritm. Algoritmul de interclasare a fost implementat aici sub forma de funcţie, care primeşte ca argumente tablourile tab1 si tab2 şi intoarce tabloul interclasat. 

Se putea

implementa algoritmul de interclasare şi ca o procedură, care primeşte trei argumemte (tab1, tab2, tab3) şi obţine tabloul interclasat ca efect lateral. Atenţie însa: în acest caz, în Java, procedurii

trebuie sa i se dea ca argument un tablou tab3 gata creat, având lungimea cel puţin egală cu suma lungimilor tablourilor tab1 şi tab2.Algoritmi rapizi de sortare a tablourilor

Algoritmii de sortare studiaţi

anterior (prin selecţie, prin inserţie, prin metoda bulelor) aveau complexitatea O(n2), deci timpul de calcul creşte cu patratul numărului de componente din tablou. Pentru tablouri de

lungime mare, acesta este un dezavantaj important, astfel că s-au conceput algoritmi mai rapizi. Dintre aceştia, vom studia aici algoritmii de sortare prin

interclasare şi de sortare rapidă.Sortarea prin interclasare (Merge Sort)

Un tablou unidimensional poate fi sortat astfel:    - se împarte tabloul dat tab în doua zone de lungime aproximativ

egală;    - se sortează separat fiecare zonă;    - se interclasează cele doua zone, obţinându-se un tablou auxiliar ordonat tab1;    - se copiază tabloul tab1 în

tabloul tab şi se distruge tab1.Sortarea fiecăreia din cele două zone se poate face tot prin interclasare, procedându-se recursiv. Recursia se opreşte când se ajunge la zone formate din cel mult două

elemente, care se pot ordona simplu, prin interschimbare.  Sortarea unei zone din tabloul tab cuprinsă între indicii i1 şi i2 (inclusiv i1 şi i2) se poate face prin

urmatoarea procedură recursivă , în care se foloseşte şi tabloul auxiliar tab1 având acelaşi număr de componente cu tabloul de sortat tab:

private static void mergeSort(double tab[], int i1, int i2,     double tab1[]) {   if((i2-i1)>1) {// se împarte în două subzone 

    int k=(i1+i2)/2; // mijlocul intervalului     mergeSort(tab,i1,k-1,tab1); // sortare subzona stânga     mergeSort(tab, k,i2, tab1); // sortare subzona dreapta     interclasare(tab,i1, k, i2, tab1);   }   else { // au ramas cel mult doua elemente     if((i2-i1)==1){// se ordoneaza cele doua elemente       if(tab[i1]>tab[i2]) { // interschimbarea elementelor         double aux=tab[i1];         tab[i1]=tab[2];         tab[i2]=aux;       } 

    }   } }

Pentru interclasarea a doua zone de tablou sortate se poate folosi urmatoarea procedură:

private static void interclasare(double tab[], int i1, int k,        int i2, double tab1[]) { 

  int i=i1, j=k, q=i1;   while(i<k && j<=i2) {     if(tab[i]<tab[j]) tab1[q++]=tab[i++];     else tab1[q++]=tab[j++];   } // sfarsit while   while(i<k) tab1[q++]=tab[i++];   while(j<=i2) tab1[q++]=tab[j++];   for(q=i1; q<=i2; q++) tab[q]=tab1[q]; // mutare din tab1 in tab } // sfarsit metoda

Cele doua metode de mai sus au fost delcarate private, pentru a nu putea

fi folosite greşit de un utilizator neatent. Pentru sortarea tabloului în întregime se foloseşte urmatoarea metodă, care le invocă direct sau indirect pe cele precedente:

public static void mergeSort(double tab[]) { 

  double tab1[]=new double[tab.length];   mergeSort(tab, 0, tab.length-1, tab1); }

În această metodă se creează tabloul auxiliar tab1, având aceeaşi lungime cu tabloul tab care trebuie sortat, apoi se invocă metoda privată prezentată anterior. 

Testarea metodelor de mai sus se face în aplicaţia din fişierul MergeSort.java. 

Exemplul s-a dat pentru cazul unui tablou cu elemente de tip double, dar metodele folosite aici pot fi modificate cu

uşurinţă pentru tablouri de alte tipuri, inclusiv pentru tablouri de obiecte.

Pentru a stabili complexitatea algoritmului de sortare prin interclasare, remărcam

urmatoarele:   - pentru un tablou cu n elemente, numărul de înjumătăţiri succesive până se ajunge la zone de lungime 1 sau 2 este de aproximativ log2n; 

  - la fiecare din aceste divizări succesive, se mută din tab în tab1 şi invers în total n elemente. In consecinta, numarul de operatii elementare executate este de ordinul O(n.log(n)

).

Mai riguros, daca notam cu C(n) numarul de operaţii elementare pentru sortarea unui tablou cu n componente şi avem în vedere că, la fiecare pas al algoritmului, se fac

doua invocări recursive ale metodei de sortare şi o interclasare, iar interclasarea are complexitatea n, atunci

C(n) = 2.C(n/2)+n

Continuând acest raţionament,

putem scrieC(n) =

2(2C(n/4)+n/2)+n = 4C(n/4) + n + nAlgoritmul se opreşte după log2(n) astfel de paşi, când se obţineC(n) = nC(n/n) + n + n + ... + n =

n.log2(n)

In consecinţă, complexitatea algoritmului de sortare prin interclasare este O(n.log(n)).

Constatăm deci că, pentru tablouri cu numar mare de componente, timpul de calcul este mult mai mic

în cazul sortării prin interclasare, decât în cazul folosirii algoritmilor simpli, cum ar fi cel al selecţiei, inserţiei sau al bulelor, a căror complexitate este O(n2). Algoritmul de sortare prin

interclasare consumă însă de două ori mai multă memorie decât cei simpli mentionaţi, deoarece necesită spaţiu suplimentar pentru tabloul auxiliar tab1.Sortarea rapidă (Quick Sort)

Algoritmul Quick Sort are aceeaşi

complexitate cu Merge Sort, dar prezintă avantajul că ocupă memorie mai puţină, deoarece nu necesită folosirea unui tablou intermediar.

Fie tab un tablou cu n componente. Sortarea tabloului

tab decurge astfel:   - se ia una din aceste componente, fie ea pivot=tab[p], care se consideră element pivot;   - se fac în tablou interschimbări de componente,

astfel încât toate cele mai mici decât valoarea pivot sa treaca în stânga acesteia, iar elementele cu valoare mai mare decât pivot sa treacă în dreapta; prin această operaţie se va

deplasa şi valoarea pivot, astfel ca ea nu se va mai gasi pe pozitia de indice p;   - tabloul s-a impartit astfel în două zone: cea din stânga, cu elemente mai mici decat pivotul, si

cea din dreapta, cu elemente mai mari decat pivotuul. Se continuă sortarea, aplicând recursiv metoda pentru zona de tablou situată în stânga componentei pivot şi pentru cea din dreapta acesteia; 

  - oprirea recursiei se face când lungimea zonei de tablou care trebuie sortată devine egala cu 1.

Complexitatea algoritmului QuickSort este O(n.log(n)).

In

fişierul QuickSort.java se dă o aplicaţie în care se testează algoritmul QuickSort. Aplicaţia conţine două metode de sortare:    public static void quickSort(double tab[])    private static void quickSort(double tab[], int i1, int i2) Prima metodă este nerecursivă dar

publică, iar acţiunea ei constă numai în a invoca cea de a doua metodă, protejând-o contra invocării incorecte.

A doua metodă este recursivă şi face sortarea prin algoritmul QuickSort a unei zone din

tabloul tab cuprinsă între indicii i1 şi i2.

Metodele pot fi modificate cu uşurinţă, astfel încât să se sorteze tablouri cu componente de alte tipuri, inclusiv tablouri de obiecte.

Pentru a stabili complexitatea algoritmului Quick Sort aplicată unui tablou tab cu n componente, notăm cu C(n) numărul de comparaţii efectuate  şi remarcăm că, la fiecare pas al

algoritmului au loc n comparaţii însoţite de interschimbări ale elementelor şi două invocari recursive ale metodei de sortare, deci

C(n) = n + C(k)+C(n-k)

unde k este

numărul de componente din zona din stânga a tabloului, iar C(k) si C(n-k) sunt complexităţile pentru cele două subzone care urmează a fi sortate recursiv. Situaţia este asemanatoare cu

cea întalnită în cazul metodei MergeSort, cu deosebirea că, în acest caz, tabloul nu se mai împarte în două părţi egale. 

Cazul cel mai favorabil ar fi când, la fiecare recursie, cele două subzone

(cu elemente mai mici şi respectiv mai mari decat elementul pivot) ar fi egale. În acest caz, calculul complexităţii se face la fel ca la MergeSort şi deci complexitatea este O(n.log(n)). 

Cazul cel mai

defavorabil ar fi cel în care, la fiecare recursie, elementul pivot ar fi ales în mod atat de nefericit, încat una din cele două subzone obţinute după interschimbări ar fi vida. In acest caz

C(n) = n + C(n-1)

= n + (n-1) + C(n-2) = ...

sau, continuand pana la C(1)C(n) = n + (n-1) + (n-2) + ... + 1

= (n+1)n/2şi deci complexitatea algoritmului este O(n2). Acest caz "nefericit" este

însă foarte puţin probabil. Cel mai probabil este că, în realitate, complexitatea sa fie situată în jurul valorii O(n.log(n)).