Varianta recursiva a algoritmului de cautare binaraAm 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){
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) {
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. |
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;
/* Daca mai exista componente in tab1, se adauga la tab3
*/
/* Daca mai exista componente in tab2, se adauga la tab3
*/
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. |
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,
Pentru interclasarea a doua zone de tablou sortate se poate folosi urmatoarea procedura: 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 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[]) {
In aceasta metoda se creeaza tabloul auxiliar tab1, avand aceeasi lungime
cu tabloul tab care trebuie sortat, apoi se invoca metoda privata prezentata
anterior.
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
|
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.
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 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 |