Sortare, cautare si recursivitate (Part. IV)

O data ce ai inceput sa utilizezi structuri de date in Java, in mod inevitabil vei intalni situatii in care vei fi nevoit sa le sortezi sau sa cauti ceva anume. In cazul acestui tutorial Java pentru incepatori, vom utiliza array-uri pentru a ilustra cativa algoritmi de baza pentru sortare, cautare si recursivitate.

Un algoritm este o procedura, o serie de pasi pe care ii definesti pentru a rezolva o anumita problema.

Recursivitate

Anumite tehnici pe care le vom utiliza se bazeaza pe procesele recursive, asadar sa le studiem mai intai pe acestea. O metoda recursiva este de fapt o functie care se apeleaza pe ea insasi. Utilizarea metodelor recursive in mod eficient necesita ceva practica, deoarece programul poate fi prins cu usurinta intr-o bucla infinita.

Pentru a observa cum actioneaza o functie recursiva, sa cream un exemplu banal. Creeaza un nou proiect Java si scrie urmatorul cod in clasa principala, dupa metoda main:

Acum apeleaza noua functie din metoda main.

Programul va numara de la valoarea int introdusa catre zero. Experimenteaza schimband valoarea parametrului int introdus in metoda si observa ce efecte are asupra rezultatului afisat pe consola. Metoda reuseste sa evite blocarea intr-o bucla (cauzata de solicitarea repetata a acesteia) utilizand o instructiune conditionala �if’.

Aceasta metoda simpla are un efect similar unei bucle, dar dupa cum vei observa, recursivitatea poate fi utila mai ales daca ai o problema complexa care este rezolvata cel mai bine in etape, fiecare etapa aducandu-te cu un pas mai aproape de solutie prin simplificare. Un ingredient necesar al metodelor recursive il reprezinta deci precizarea explicita a modului in care metodele ar trebui sa se comporte pentru cel mai banal input, si apoi cu fiecare iteratie, te indrepti catre acest caz foarte simplu. In exemplul de mai sus, cazul cel mai simplu este atunci cand parametrul int este mai mic sau egal cu zero.

Incearca sa nu te ingrijorezi daca aceasta pare a fi la inceput o practica ciudata, de indata ce incepi sa utilizezi metode de sortare, abordarea recursiva va deveni mai clara.

Sortarea

Motivul principal pentru pastrarea unei colectii de date intr-o ordine sortata il reprezinta usurinta cu care se gasesc articolele in cadrul acesteia. Cu toate acestea, pastrarea datelor intr-o ordine sortata implica o anumita munca de procesare, mai ales la adaugarea sau indepartarea articolelor.

Cand spunem, de exemplu, ca un array este sortat, intelegem ca elementele acestuia sunt aranjate intr-o anumita ordine. Uneori, regula de ordonare este intuitiva: de exemplu daca array-ul contine numere, ele vor fi ordonate crescator (sau descrescator) dupa valoarea lor. In mod similar, daca array-ul contine siruri de caractere, ele pot fi sortate alfabetic.

Oricum, exista situatii in care regula de sortare este mai putin clara – imagineaza-ti ca ti-ai creat o clasa proprie, si ca doresti sa stochezi obiecte de tipul respectiv intr-un array. Va trebui sa decizi apoi care este regula de sortare pentru aceste obiecte. Pentru aceasta trebuie sa te gandesti la modul de comparare a doua obiecte din aceeasi clasa. Cand compari doua obiecte ale clasei, exista situatia in care, fie unul este „mai mare” decat celalalt, fie sunt „egale”. Pentru a putea ordona obiectele astfel, clasa ta trebuie sa implementeze interfata Comparable, incluzand o definitie pentru metoda compareTo. In cadrul acestei metode va trebui sa definesti regula de sortare pentru obiectele din clasa, de exemplu, ai putea utiliza valoarea unor proprietati ale clasei pentru a decide care obiect este „mai mare”.

Nota: Ai grija atunci cand utilizezi metoda equals deoarece in mod implicit ea este mostenita din clasa Object si lucreaza cu referintele obiectelor – de ex., testeaza daca numele a doua variabile indica acelasi obiect. Daca intentionezi sa utilizezi medoda equals, cel mai bine ar fi sa lucrezi cu propria implementare a acesteia, rescriind metoda implicita.

In cadrul acestui tutorial Java, vom ramane la tipuri de date simple pentru a ilustra cativa algoritmi de selectie.

Sortarea prin selectie

Sortarea prin selectie actioneaza prin descoperirea in permanenta a celui mai mic articol din colectie si prin plasarea acestuia la inceput. Creeaza un nou program si introdu urmatorul cod in metoda main pentru a crea un array continand cateva date ales in mod arbitrar:

In continuare, vom utiliza sortarea prin selectie pentru a aranja elementele din array in ordine crescatoare. Algoritmul functioneaza astfel:

• In cadrul colectiei de date care urmeaza a fi sortate (initial, intreaga structura), gaseste cel mai mic articol;
• Plaseaza acest articol in prima pozitie (a structurii nesortate), inlocuind orice element care se afla deja acolo si muta elementul inlocuit la pozitia celui mai mic articol;
• Sectiunea nesortata contine acum un element mai putin (articolul tocmai considerat a fi cel mai mic si prin urmare, mutat);
• Continua plasarea celui mai mic element nesortat in prima pozitie pana cand toate datele au fost sortate.

Introdu urmatorul cod dupa declararea array-ului si compileaza programul, observand rezultatul:

Cand privesti rezultatul programului, incearca sa observi articolele care se inlocuiesc in fiecare etapa – experimenteaza schimband valorile (sau ordinea lor) din array.

Sortarea prin interclasare

O metoda mai eficienta de sortare a continutului unui array este sortarea prin interclasare, care utilizeaza un algoritm recursiv. Aceasta se bazeaza pe ideea ca unificarea a doua array-uri deja sortate este o problema mai simpla decat ordonarea tuturor datelor dintr-un array nesortat. Deci, algoritmul sorteaza un array prin divizarea sa continua in doua parti si sortarea fiecareia, unificand rezultatele intr-un array sortat.

Adauga urmatoarea metoda in clasa ta (dupa functia main):

De fiecare data cand metoda ajunge la punctul de unificare a celor jumatati, fiecare jumatate a fost deja sortata, deoarece functia a fost aplicata mai intai asupra acestora. Asadar, metoda rezolva problema prin impartirea si simplificarea sa repetata. Acum, apeleaza noua metoda din main:

Din nou, experimenteaza schimband valorile din array si observa rezultatul programului.

Pentru inceput, algoritmul recursiv poate fi dificil de inteles si in mod sigur necesita ceva practica, dar atunci cand vei reusi, vei descoperi ca poti identifica solutii destul de rapide pentru anumite probleme. Este indicat ca la scrierea unei metode recursive sa incepi de la cazul cel mai simplu, apoi sa te ocupi de pasii care conduc catre acesta de fiecare data cand metoda este executata.

Cautarea

Deseori va trebui sa gasesti un anumit element intr-o structura de date dintr-un motiv sau altul. Daca datele din array nu sunt sortate, singurul mod pentru a efectua aceasta este sa verifici fiecare element pe rand. In schimb, daca dispui de un array sortat, poti folosi o metoda de cautare binara, cum este cea de mai jos:

Acum apeleaza aceasta functie din metoda main:

Experimenteaza cautand diverse elemente din array. In plus, poti verifica cate iteratii ale buclei sunt necesare de fiecare data, incluzand o instructiune System.out.print in bucla din metoda binarySearch. In general este o practica buna sa incluzi astfel de instructiuni in codul tau, pentru a verifica in mod exact ce se intampla in fiecare stadiu al programului; poate fi de ajutor mai ales la corectarea programelor mai mari.

Desi multe tipuri de date din Java includ metode de sortare si de cautare, poate fi de ajutor pentru optimizarea programelor proprii sa te gandesti la algoritmii implicati. Totodata, cand trebuie sa iti definesti propriile tipuri de date, s-ar putea sa fie nevoie sa implementezi astfel de metode. Exista numeroase abordari in vederea sortarii si a cautarii in Java, exemplele de mai sus fiind doar introductive.