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: 15948 15948 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

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):

/* Functia mergeSort sorteaza datele dintr-un array
* -parametrii transmisi sunt array-ul cu datele ce trebuiesc sortate,
*  un array temporar (temp) utilizat la calcule
*  si doua valori intregi care indica inceputul si sfarsitul
*  sectiunii din array ce trebuie ordonata
*/
public static void mergeSort(int[] dataArray, int[] tempArray, int start, int end)
{
    // daca start = end, array-ul a fost sortat
    if(start==end)
        return;
    // altfel imparte array-ul in 2 sectiuni
    else
    {
        //calculeaza centrul array-ului
        int center = (start+end)/2;
 
        //apeleaza mergeSort pentru prima jumatate
        mergeSort(dataArray, tempArray, start, center);
 
        //apeleaza mergeSort pentru cea de-a doua jumatate
        mergeSort(dataArray, tempArray, center+1, end);
 
        //uneste jumatatile intr-un singur array
        int firstIndex = start;
        int secondIndex = center+1;
        int thirdIndex = start;
 
        //parcurge ambele parti
        while(thirdIndex<=end)
        {
                /* parcurge partile
                 * inserand cel mai mic element
                 * in array-ul temp
                 */
            if(secondIndex>end ||
            (firstIndex<=center &&
            dataArray[firstIndex]<=dataArray[secondIndex]))
            {
                tempArray[thirdIndex]=dataArray[firstIndex];
                thirdIndex++;
                firstIndex++;
            }
            else
            {
                tempArray[thirdIndex]=dataArray[secondIndex];
                thirdIndex++;
                secondIndex++;
            }
        }
 
        //copiaza continutul array-ului temp in array-ul principal
        for(int i=start; i<=end; i++)
            dataArray[i]=tempArray[i];
    }

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:

//array-ul ce trebuie ordonat
int[] someData = {4, 3, 7, 6, 2, 8, 5, 9, 1};
//array suplimentar (ca ajutor)
int[] extraArray = new int[someData.length];
//apeleaza functia mergesort
mergeSort(someData, extraArray, 0, someData.length-1);
 
//afiseaza rezultatul
for(int pr : someData)
{ System.out.print(pr); }

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:

//metoda de cautare 
//primul parametru reprezinta array-ul in care cautam
//cel de-al doilea este elementul cautat
public static int binarySearch(String[] theData, String wanted)
{
    //-1 inseamna ca elementul nu a fost gasit
    int foundIndex=-1;
 
    //retine capetele intervalului de cautare
    int top = theData.length-1;
    int bottom = 0;
 
    //parcurge array-ul, divizand intervalul de cautare
    while(bottom<=top)
    {
        //calculeaza mijlocul sectiunii analizate
        int middle = (top+bottom)/2;
 
        //compara elementul din mijloc cu elementul cautat 
        int comp = theData[middle].compareTo(wanted);
 
        //daca elementul din mijloc este egal cu elementul cautat, returneaza indexul sau
        if(comp==0)
            return middle;
 
        /* daca elementul din mijloc este mai mare, 
         * atunci elementul cautat se afla in prima jumatate
         * altfel se afla in cea de-a doua jumatate
         */
 
        else if(comp>0) //mijlocul este mai mare
            top=middle-1;
        else //mijlocul este mai mic
            bottom=middle+1;
 
    }
 
    //am terminat cautarea
    return foundIndex;
}

Acum apeleaza aceasta functie din metoda main:

//array ordonat
String[] sortedStrings = {"aubergine", "carrot", "courgette",
        "leek", "onion", "potato", "turnip"};
 
//apeleaza metoda de cautare - returneaza -1 daca elementul nu este gasit
int searchResult = binarySearch(sortedStrings, "potato");
 
System.out.println("gasit la indexul: "+searchResult);

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.

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
4670
Tutoriale scrise de mcuemica
mcuemica Rang utilizator mcuemica - Incepator
4590
Tutoriale scrise de ellarichards
ellarichards Rang utilizator ellarichards - Incepator
4510
Tutoriale scrise de emonclercheap
emonclercheap Rang utilizator emonclercheap - Incepator
4415
Tutoriale scrise de beacherrosa
beacherrosa Rang utilizator beacherrosa - Incepator
4290
* Acest top reprezinta punctajele acumulate in ultimele 30 de zile.
Javascript AJAX Vista Action Script Gimp HTML COREL DRAW Verilog StyleSheet CSS Excel MySQL XHTML Fotografie Dreamweaver PSD SEO Java JSON XML Fireworks Ruby on Rails Photoshop Bridge Sony Vegas PHP RoR Word Outlook SWF Powerpoint Lightroom Swift 3D Illustrator Flash Python
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