E-learn.ro
Panou utilizatori
Utilizator Parola
Creeaza cont nou    Recupereaza parola
Login
Newsletter
Introdu adresa ta de email
Inscrie-te
Inchide panoul de utilizatori
Add to Google

Tutoriale Java

Descarca toolbar

Toolbar E-learn.ro Facebook Twitter

DEVELOPMENT  /  Java  /  Introducere in Java (8)

Sortare, cautare si recursivitate (Partea a IV-a)

17.07.2009
Sortare, cautare si recursivitate (Partea a IV-a)

In cazul acestui tutorial Java pentru incepatori, vom utiliza array-uri pentru a ilustra cativa algoritmi de baza pentru sortare, cautare si recursivitate.

Total vizualizari: 14848 14848 afisari   |   Comentarii  0   |   Rating   |   (0 voturi)   |   Timp necesar: 30 min 30 min   |   Nivel de cunostiinte necesar: Incepator  Incepator

Sursa:  learnola.com  
Autor:  learnola.com
Adauga la tutoriale favorit Adauga la tutoriale favorite
Pagina:
1 2 »
comenteaza printeaza

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:

// metoda recursiva
public static int doSomething(int someNumber)
{
    // verifica valoarea parametrului
    if(someNumber<=0)
        return someNumber;
    else
    {
        // decrementeaza valoarea si apeleaza din nou functia
        someNumber--;
        System.out.println(someNumber);
        return(doSomething(someNumber));
    }
}

Acum apeleaza noua functie din metoda main.

int result = doSomething(10);
System.out.println("rezultat: " + result);

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:

//array cu date nesortate
int [] myData = {3, 1, 9, 5, 7};

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:

 
//parcurge array-ul intr-o bucla for
for(int pos=0; pos < myData.length-1; pos++)
{
        /* gaseste si retine pozitia 
         * celui mai mic element
         * incepe de la pos si cauta in restul array-ului
         * (pos indica inceputul sectiunii nesortate)
         */
    int minIndex = pos;
 
        // parcurge sectiunea nesortata
    for(int next=pos+1; next< myData.length; next++)
    {
        if(myData[minIndex]>myData[next])
            minIndex=next;
    }
 
        //inverseaza pozitia elementelor daca este necesar
    if(minIndex!=pos)
    {
            //retine elementul curent indicat de pos
        int temp = myData[pos];
            //copiaza cel mai mic element la pozitia pos
        myData[pos] = myData[minIndex];
            //copiaza elementul inlocuit la pozitia minIndex
        myData[minIndex] = temp;
    }
 
        //afiseaza array-ul sortat
    for(int p : myData)
    {    System.out.print(p);    }
    System.out.println();
}

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

Pagina:
1 2 »
comenteaza printeaza
Alte tutoriale Java:
Noteaza acest tutorial
Rating tutorial
 
(0 voturi)
Pentru a nota acest tutorial, trebuie sa fii logat!
Posteaza un comentariu
Pentru a posta un comentariu, trebuie sa fii logat!
0 TOP UTILIZATORI* 0 0
Tutoriale scrise de claibornelara
claibornelara Rang utilizator claibornelara - Incepator
4165
Tutoriale scrise de kheops
kheops Rang utilizator kheops - Mediu
4084
Tutoriale scrise de ellarichards
ellarichards Rang utilizator ellarichards - Incepator
4075
Tutoriale scrise de mcuemica
mcuemica Rang utilizator mcuemica - Incepator
4050
Tutoriale scrise de emonclercheap
emonclercheap Rang utilizator emonclercheap - Incepator
3865
* Acest top reprezinta punctajele acumulate in ultimele 30 de zile.
StyleSheet Excel Gimp Lightroom Bridge COREL DRAW Sony Vegas Action Script Verilog Swift 3D PHP PSD CSS Flash Illustrator HTML Fireworks Powerpoint XML AJAX JSON Vista SEO Javascript Word Java MySQL SWF XHTML Photoshop Ruby on Rails Python Dreamweaver Outlook Fotografie RoR
Promovare:
Daca faci parte din comunitatea E-learn.ro si doresti promovarea acesteia, poti accesa pagina de promovare.
Arhiva newsletter:
Daca ai ratat un numar mai vechi, sau vrei sa revezi care au fost noutatile E-learn.ro la un moment dat, poti accesa arhiva de newslettere.
  Copyright © 2008-2013 E-LEARN.ro. Toate drepturile rezervate. Termeni si conditii.
Conceput si realizat de Neokinetics Software