Tabloul privit ca structură recursivă

Tablourile sunt structuri recursive, deoarece: 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 scrie
C(n) = 2(2C(n/4)+n/2)+n = 4C(n/4) + n + n
Algoritmul se oprește după log2(n) astfel de pași, când se obține
C(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)).



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați