Tabloul privit ca structura recursiva

Tablourile sunt structuri recursive, deoarece: Aceasta proprietate permite ca multe operatii de prelucrare ale datelor continute in tablouri sa se poata realiza folosind algoritmi recursivi.
 

Varianta recursiva a algoritmului de cautare binara

Am studiat deja varianta iterativa a algoritmului de cautare binara a unei valori intr-un tablou ordonat.

Consideram ca dorim sa cautam in tabloul tab cu componente de tip double, componenta de valoare val in zona de tablou situata intre indicii inf si sup. In acest scop, putem folosi urmatoarea functie recursiva: (scrisa in Java):

static int cautBinRec(double tab[], double val, int inf, int sup){
  if(inf>sup) return -1; // interval gresit
  int k=(inf+sup)/2; // se ia indicele de la mijlocul zonei
  if(val==tab[k]) return k; // s-a gasit elementul cautat
  if(val<tab[k]) return cautBinRec(tab, val, inf, k-1); /* se cauta
    valoarea val in jumatatea din stanga a zonei */
  else return cautBinRec(tab, val, k+1, sup); /* se cauta valoarea
    val in jumatatea din dreapta a zonei */
}

Daca s-a definit functia de mai sus, pentru cautarea aceleeasi valori in intregul tablou se poate folosi functia:

static int cautBinRec(double tab[], double val) {
  return cautBinRec(tab, val, 0, tab.length-1);
}

Cele doua functii de mai sus sunt testate in programul din fisierul CautBinRec.java.

Programele pot fi modificate cu usurinta pentru cazul cand componentele tabloului in care se face cautarea sunt de alt tip primitiv sau sunt obiecte.

Se poate constata cu usurinta ca varuianta iterativa prezentata anterior a fost obtinuta pornind de la cea recursiva, inlocuindu-se invocarile de functii recursive prin cicluri.

Interclasarea a doua tablouri ordonate

Fie doua tablouri ordonate  tab1 de lungime m si tab2 de lungime n. Prin interclasare se obtine un nou tablou tab3 de lungime p=m+n, procedand astfel:
  - se compara primele elemente din tab1 si tab2 si se transfera cel mai mic dintre ele in tab3;
  - se continua astfel, comparand la fiecare pas primele dintre elementele inca netransferate din cele doua tablouri si punandul in tab3 pe cel mai mic dintre ele;
  - dupa ce componentele din unul din cele doua tablouri date s-au epuizat, se adauga la tab3 toate componentele ramase in celalalt tablou.
Tabloul tab3, astfel obtinut, contine elementele din cele doua tablouri date puse in ordine.
 
Algoritmul de interclasare a tablourilor tab1 si tab2 poate fi descris in 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;
  cat timp (i<m si j<n) {
    daca (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;
  }
  /* in acest moment componentele din unul din tablourile tab1 si tab2 s-au terminat */

  /* Daca mai exista componente in tab1, se adauga la tab3 */
  cat timp (i<m) { 
    tab3[k]=tab1[i];
    i=i+1; k+1;
  }

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

In fisierul Interclasare.java este dat un exemplu de aplicatie in care se testeaza acest algoritm. Algoritmul de interclasare a fost implementat aici sub forma de functie, care primeste ca argumente tablourile tab1 si tab2 si intoarce tabloul interclasat. 

Se putea implementa algoritmul de interclasare si ca o procedura, care primeste trei argumemte (tab1,tab2,tab3) si obtine tabloul interclasat ca efect lateral. Atentie insa, in acest caz, in Java, procedurii trebuie sa i se dea ca argument un tablou tab3 gata creat, avand lungimea cel putin egala cu suma lungimilor tablourilor tab1 si tab2.

Algoritmi rapizi de sortare a tablourilor

Algoritmii de sortare studiati anterior (prin selectie, prin insertie, prin metoda bulelor) aveau complexitatea O(n2), deci timpul de calcul creste cu patratul numarului de componente din tablou. Pentru tablouri de lungime mare, acesta este un dezavantaj important, astfel ca s-au conceput algoritmi mai rapizi. Dintre acestia, vom studia aici algoritmii de sortare prin interclasare si de sortare rapida.

Sortarea prin interclasare (Merge Sort)

Un tablou unidimensional poate fi sortat astfel:
   - se imparte tabloul dat tab in doua zone de lungime aproximativ egala;
   - se sorteaza separat fiecare zona;
   - se interclaseaza cele doua zone, obtinandu-se un tablou auxiliar ordonat tab1;
   - se copiaza tabloul tab1 in tabloul tab si se distruge tab1.
Sortarea fiecareia din cele doua zone se poate face tot prin interclasare, procedandu-se recursiv. Recursia se opreste cand se ajunge la zone formate din cel mult doua elemente, care se pot ordona simplu, prin interschimbare.
 
Sortarea unei zone din tabloul tab cuprinsa intre indicii i1 si i2 (inclusiv i1 si i2) se poate face prin urmatoarea procedura recursiva, in care se foloseste si tabloul auxiliar tab1 avand acelasi numar de componente cu tabloul de sortat tab:

private static void mergeSort(double tab[], int i1, int i2,
    double tab1[]) {
  if((i2-i1)>1) {// se imparte in doua subzone
    int k=(i1+i2)/2; // mijlocul intervalului
    mergeSort(tab,i1,k-1,tab1); // sortare subzona stanga
    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 procedura:

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 gresit de un utilizator neatent. Pentru sortarea tabloului in intregime se foloseste urmatoarea metoda, care le invoca 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);
}

In aceasta metoda se creeaza tabloul auxiliar tab1, avand aceeasi lungime cu tabloul tab care trebuie sortat, apoi se invoca metoda privata prezentata anterior.
Testarea metodelor de mai sus se face in aplicatia din fisierul MergeSort.java

Exemplul s-a dat pentru cazul unui tablou cu elemente de tip double, dar metodele folosite aici pot fi modificate cu usurinta pentru tablouri de alte tipuri, inclusiv pentru tablouri de obiecte.

Pentru a stabili complexitatea algoritmului de sortare prin interclasare, remarcam urmatoarele:
  - pentru un tablou cu n elemente, numarul de injumatatiri succesive pana se ajunge la zone de lungime 1 sau 2 este de aproximativ log2n;
  - la fiecare din aceste divizari succesive, se muta din tab in tab1 si invers in 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 operatii elementare pentru sortarea unui tablou cu n componente si avem in vedere ca, la fiecare pas al algoritmului, se fac doua invocari recursive ale metodei de sortare si o interclasare, iar interclasarea are complexitatea n, atunci
C(n) = 2.C(n/2)+n
Continuand acest rationament, putem scrie
C(n) = 2(2C(n/4)+n/2)+n = 4C(n/4) + n + n
Algoritmul se opreste dupa log2(n) astfel de pasi, cand se obtine
C(n) = nC(n/n) + n + n + ... + n = n.log2(n)
In consecinta, complexitatea algoritmului de sortare prin interclasare este O(n.log(n)).

Constatam deci ca, pentru tablouri cu numar mare de componente, timpul de calcul este mult mai mic in cazul sortarii prin interclasare, decat in cazul folosirii algoritmilor simpli, cum ar fi cel al selectiei, insertiei sau al bulelor, a caror complexitate este O(n2). Algoritmul de sortare prin interclasare consuma insa de doua ori mai multa memorie decat cei simpli mentionati, deoarece necesita spatiu suplimentar pentru tabloul auxiliar tab1.

Sortarea rapida (Quick Sort)

Algoritmul Quick Sort are aceeasi complexitate cu Merge Sort, dar prezinta avantajul ca ocupa memorie mai putina, deoarece nu necesita 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 considera element pivot;
  - se fac in tablou interschimbari de componente, astfel incat toate cele mai mici decat valoarea pivot sa treaca in stanga acesteia, iar elementele cu valoare mai mare decat pivot sa treaca in dreapta; prin aceasta operatie se va deplasa si valoarea pivot, astfel ca ea nu se va mai gasi pe pozitia de indice p;
  - tabloul s-a impartit astfel in doua zone: cea din stanga, cu elemente mai mici decat pivotul, si cea din dreapta, cu elemente mai mari decat pivotuul. Se continua sortarea, aplicand recursiv metoda pentru zona de tablou situata in stanga componentei pivot si pentru cea din dreapta acesteia;
  - oprirea recursiei se face cand lungimea zonei de tablou care trebuie sortata devine egala cu 1.

Complexitatea algoritmului QuickSort este O(n.log(n)).
 
In fisierul QuickSort.java se da o aplicatie in care se testeaza algoritmul QuickSort. Aplicatia contine doua metode de sortare:
   public static void quickSort(double tab[])
   private static void quickSort(double tab[], int i1, int i2) 
Prima metoda este nerecursiva dar publica, iar actiunea ei consta numai in a invoca cea de a doua metoda, protejand-o contra invocarii incorecte.

A doua metoda este recursiva si face sortarea prin algoritmul QuickSort a unei zone din tabloul tab cuprinsa intre indicii i1 si i2.

Metodele pot fi modificate cu usurinta, astfel incat sa se sorteze tablouri cu componente de alte tipuri, inclusiv tabele de obiecte.

Pentru a stabili complexitatea algoritmului Quick Sort aplicata unui tablou tab cu n componente, notam cu C(n) numarul de comparatii efectuate  si remarcam ca, la fiecare pas al algoritmului au loc n comparatii insotite de interschimbari ale elementelor si doua invocari recursive ale metodei de sortare, deci

C(n) = n + C(k)+C(n-k)
unde k este numarul de componente din zona din stanga a tabloului, iar C(k) si C(n-k) sunt complexitatile pentru cele doua subzone care urmeaza a fi sortate recursiv. Situatia este asemanatoare cu cea intalnita in cazul metodei MergeSort, cu deosebirea ca, in acest caz, tabloul nu se mai imparte in doua parti egale. 

Cazul cel mai favorabil ar fi cand, la fiecare recursie, cele doua subzone (cu elemente mai mici si respectiv mai mari decat elementul pivot) ar fi egale. In acest caz calculul complexitatii se face la fel ca la MergeSort si deci complexitatea este O(n.log(n))

Cazul cel mai defavorabil ar fi cel in care, la fiecare recursie, elementul pivot ar fi ales in mod atat de nefericit, incat una din cele doua subzone obtinute dupa interschimbari 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
si deci complexitatea algoritmului este O(n2). Acest caz "nefericit" este insa foarte putin probabil. Cel mai probabil este ca, in realitate, complexitatea sa fie situata in jurul valorii O(n.log(n)).



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati