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){ 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) { 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. |
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; /* Daca mai există componente în tab1, se adaugă la tab3
*/ /* Daca mai exista componente in tab2, se adauga la tab3
*/ 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. |
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, Pentru interclasarea a doua zone de tablou sortate se poate folosi urmatoarea procedură: private static void interclasare(double tab[], int i1, int
k, 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[]) { Î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. 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
|
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.
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 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 |