Algoritmi simpli de sortare a tablourilor

Sortarea tabloului este ordonarea componentelor acestuia dupa valoarea lor. Daca tipul componentelor tabloului este numeric, relatia de ordine este cea specifica multimii de valori a tipului respectiv. Pentru diferite clase de obiecte se pot, de asemenea, defini relatii de ordine, depinzand de scopul in care se face sortarea.
 
In limbajul Java, relatia de ordine pe o multime de obiecte apartinand de o anumita clasa se poate introduce in doua moduri: fie clasa respectiva trebuie sa implementeze interfata java.lang.Comparable, fie pentru compararea obiectelor se foloseste un comparator, adica o instanta a unei clase care implementeaza interfata java.util.Comparator.

Interfata Comparable contine metoda
    public int compareTo(Object obj)
Aceasta metoda compara obiectul de care apartine cu obiectul obj, primit ca argument, si intoarce valoarea 0 (zero) daca cele doua obiecte sunt egale, valoare negativa daca obiectul propriu il precede pe obj in relatia de ordine si valoare pozitiva daca ii succede. Cu alte cuvinte, daca x si y sunt obiecte din aceeasi clasa, iar clasa respectiva implementeaza interfata Comparable, atunci expresia x.compareTo(y) intoarce valoare negativa, nula sau pozitiva, dupa cum valoarea lui x precede, este egala cu sau succede valorii lui y. De asemenea, aceasta metoda trebuie sa intoarca 0 atunci cand expresia x.equals(y) intoarce true. Un exemplu tipic de clasa care implementeaza interfata Comparable este clasa java.lang.String.

Interfata Comparator este implementata de clasa ale carei instante servesc drept comparatoare pentru instantele altei clase. Aceasta interfata contine urmatoarele metode:
    public int compare(Object o1,Object o2)
    public boolean equals(Object obj)
Prima dintre aceste metode compara intre ele doua obiecte dintr-o clasa diferita de cea a comparatorului. Daca c este un comparator, iar x si y sunt doua obiecte, expresia c.compare(x,y) intoarce valoare negativa, nula sau pozitiva daca, respectiv, valoarea lui x precede, este egala cu sau succede valorii lui y. A doua metoda compara insasi comparatorul cu un obiect oarecare obj primit ca argument, astfel ca expresia c.equals(ob) intoarce true daca comparatorul c este identic cu argumentul ob. Este posibil ca, pentru aceeasi clasa de obiecte, sa avem mai multe clase de comparatori, care difera intre ele prin criteriul dupa care se face comparatia. De exemplu, doua persoane pot fi comparate dupa nume, dupa locul de munca, dupa data nasterii etc.

Amintim ca, in limbajul Java, daca a si b sunt doua variabile-referinta, expresia a==b are valoarea true daca, si numai daca, referintele continute in aceste doua variabile sunt identice, cu alte cuvinte ele indica unul si acelasi obiect din memorie. Cand dorim sa verificam daca doua obiecte diferite (situate in memorie la adrese diferite) sunt identice, folosim metoda
    public boolean equals(Object obj)
din clasa Object, care trebuie redefinita in fiecare clasa.

In aceasta sectiune vom studia cativa algoritmi simpli de sortare a tablourilor, care pot fi utilizati pentru tablouri cu numar mic de componente. Pentru tablouri mai mari exista algoritmi mai eficienti, pe care ii vom studia ulterior.

Sortarea prin selectie

Una din cele mai intuitive metode de ordonare a datelor intr-un tablou este urmatoarea: se cauta in tablou cel mai mic element si se schimba cu cel de pe prima pozitie. Se cauta apoi cel mai mic element dintre cele situate ramase si se aduce in tablou pe pozitia a doua si asa mai departe.
 
In pseudocod, acest algoritm se poate formula astfel:

        Fie tabloul tab cu n componente;
        Fie i, j, k numere intregi;
    pentru i de la 0 lan-2 {
        /* se cauta cel mai mic element de pe pozitiile i .. n-1  */
        k=i; /* s-a notat cu k indicele celui mai mic element */
        pentru jde lai la n-1
           dacatab[j]<tab[k]
              atunci k=j;
        /* se aduce pe pozitia i cel mai mic element de pe pozitiile i .. n-1
           acesta fiind tab[k]
        */
        daca k este diferit de i
          atuncise interschimba tab[i] cu tab[k];
    }

Exemplul 1
Fie tabloul
82
37
97
42
Se cauta cel mai mic element din intregul tablou si se schimba cu cel de pe prima pozitie (de indice 0). Ordinea elementelor in tablou este acum urmatoarea:
37
82
97
42
Se cauta cel mai mic element incepand de la cel de indice 1 si se aduce pe aceasta pozitie:
37
42
97
82
Se cauta cel mai mic element incepand cu pozitia de indice 2 si se aduce pe aceasta pozitie:
37
42
82
97
Ordonarea elementelor s-a incheiat.

Complexitatea acestui algoritm de sortare poate fi evaluata astfel: pentru fiecare valoare a lui i se fac n-i-1 comparatii, iar i ia valori de la 0 la n-2, deci ordinul de marime al numarului de operatii elementare este (n-1)+(n-2)+(n-3)+...+1=[(n-1)+1]*(n-1)/2. Aceasta inseamna ca complexitatea algoritmului de sortare prin selectie este O(n2).

Sortarea prin insertie

Se considera ca, pentru o pozitie oarecare de indice i, zona de tablou de la indicele 0 la i-1 este deja ordonata. Se ia elementul de pe pozitia de indice i si se cauta la stanga lui, de la dreapta la stanga, pozitia pe care trebuie plasat, astfel incat sa se respecte ordinea impusa. Fie aceasta pozitia de indice j<i. Elementele de pe pozitiile de la j la i-1 se deplaseaza cu cate o pozitie la dreapta. Repetandu-se acest procedei pentru i de la 1 la n (unde n este numarul de elemente din tablou), se obtine un tablou ordonat.
 
In pseudocod, algoritmul de sortare prin insertie poate fi exprimat astfel:

       Fie tab un tablou cu n componente;
       Fie i, j intregi, iar p de acelasi tip cu componentele tabloului tab.
    pentru i de la 1 lan-1 {
        /* elementul de pe pozitia i se insereaza pe pozitia corespunatoare din
           zona 0 .. i;
        */
        p=tab[i]; /* se salveaza tab[i] in p, care este de acelasi tip cu tab[i] */
        j=i; /* se vor deplasa cu o pozitie la dreapta toate elementele din zona i-1 .. 0
                care sunt mai mari decat p
             */
        cat timp (j>0 sitab[j-1]>p) {
           tab[j]=tab[j-1]; j=j-1;
        }
        tab[j]=p; /* elementul salvat p se plaseaza la locul sau corect */
    }

Exemplul 2
Fie acelasi tablou ca in exemplul 1:
82
37
97
42
Se ia elementul de pe pozitia de indice 1, si se constata ca este mai mic decat cel de la indicele 0, astfel ca se pune in locul acestuia, deplasandu-l cu o pozitie la dreapta.
37
82
97
42
Acum primele doua elemente sunt deja ordonate. Pentru i=2 se constata ca elementul curent (97) este mai mare decat cel de pe pozitia i-1, deci ramane pe loc.
37
82
97
42
Acum primele trei elemente sunt ordonate. Pentru i=3 se constata ca acest element trebuie pus pe pozitia de indice 1, iar elementele 82 si 97 trebuie deplasate cu o pozitie la dreapta.
37
42
82
97
Ordonarea s-a incheiat.

Pentru a evalua complexitatea acestui algoritm, se constata ca pentru fiecare valoare a indicelui i (de la 1 la n-1) se fac cel mult i-1 deplasari. In consecinta, ordinul de marime al numarului de operatii elementare este 1+2+3+...+(n-1)=n*(n-1)/2, iar complexitatea este O(n2).

Algoritmul de sortare prin insertie prezinta avantajul ca, daca tabloul dat initial este deja ordonat, sortarea se opreste dupa prima parcurgere a tabloului si deci complexitatea operatiei devine O(n).

Sortarea prin metoda bulelor

In sortarea prin metoda bulelor se parcurge tabloul, comparandu-se intre ele numai elementele vecine si permutand aceste elemente daca nu se gasesc in ordine. Dupa o singura parcurgere, cel mai mare element ajunge pe ultima pozitie. Se repeta operatia de parcurgere si interschimbare cu cele n-1 elemente ramase, astfel ca cel mai mare dintre ele ajunge pe penultima pozitie. Se continua parcurgerile reducand mereu numarul de elemente parcurse, pana s-e ordoneaza intregul tablou.
 
In pseudocod, acest algoritm se poate exprima astfel:

        Fie tab un tablou cu n componente;
        Fie i, j numere intregi.
    pentru i de la n-1la 1 {
        /* prin interschimbari de elemente vecine, se deplaseaza spre dreapta cel mai mare element din zona de indici 0 .. i pana ajunge pe pozitia i
        */
        pentru jde la 1 la i
           dacatab[j-1]>tab[j]
               atunci se interschimba tab[j-1] cutab[j];
    }

Se poate modifica acest algoritm, astfel incat sortarea sa se opreasca in momentul in care se constata ca, la incheierea unei parcurgeri a tabloului, nu a fost necesar sa se faca nici o permutare de elemente si, deci, tabloul este deja ordonat.

Exemplul 3
Reluam cazul tabloului din cele doua exemple precedente
82
37
97
42
La prima parcurgere, se constata ca 82 trebuie interschimbat cu 37, iar 97 trebuie interschimbat cu 42, obtinanduse tabloul
37
82
42
97
Acest tablou nu este inca ordonat, dar cel mai mare element a ajuns pe ultima pozitie. Se repeta parcurgerea numai pentru primele trei pozitii. Constatam ca este necesar sa se permute elementele de pe pozitiile de indici 1 si 2, obtinandu-se tabloul
37
42
82
97
Acest tablou este deja ordonat, dar pentru control se mai compara o data elementele de pe pozitiile 0 si 1, constatandu-se ca sunt pe pozitiile corecte.

Evaluandu-se ordinul de marime al numarului de operatii elementare necesare, se constata ca si in acest caz complexitatea algoritmului este O(n2).



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati