Algoritmi simpli de sortare a tablourilor

Sortarea tabloului este ordonarea componentelor acestuia după valoarea lor. Dacă tipul componentelor tabloului este numeric, relația de ordine este cea specifică mulțimii de valori a tipului respectiv. Pentru diferite clase de obiecte se pot, de asemenea, defini relații de ordine, depinzând de scopul în care se face sortarea.
 
În limbajul Java, relația de ordine pe o mulțime de obiecte aparținând de o anumită clasă se poate introduce în două moduri: fie clasa respectivă trebuie să implementeze interfața java.lang.Comparable, fie pentru compararea obiectelor se foloseste un comparator, adica o instanță a unei clase care implementează interfața java.util.Comparator.

Interfața Comparable conține metoda
    public int compareTo(Object obj)
Această metodă compară obiectul de care aparține cu obiectul obj, primit ca argument, și întoarce valoarea 0 (zero) dacă cele două obiecte sunt egale, valoare negativă dacă obiectul propriu îl precede pe obj în relația de ordine și valoare pozitivă dacă îi succede. Cu alte cuvinte, dacă x și y sunt obiecte din aceeași clasă, iar clasa respectivă implementează interfața Comparable, atunci expresia x.compareTo(y) întoarce valoare negativă, nulă sau pozitivă, după cum valoarea lui x precede, este egală cu sau succede valorii lui y. De asemenea, această metodă trebuie să întoarca 0 atunci când expresia x.equals(y) întoarce true. Un exemplu tipic de clasă care implementează interfața Comparable este clasa java.lang.String.

Interfața Comparator este implementată de clasa ale cărei instanțe servesc drept comparatoare pentru instanțele altei clase. Această interfață conține următoarele metode:
    public int compare(Object o1,Object o2)
    public boolean equals(Object obj)
Prima dintre aceste metode compară între ele două obiecte dintr-o clasă diferită de cea a comparatorului. Dacă c este un comparator, iar x si y sunt două obiecte, expresia c.compare(x,y) întoarce valoare negativă, nulă sau pozitivă dacă, respectiv, valoarea lui x precede, este egală cu sau succede valorii lui y. A doua metoda compară însăsi comparatorul cu un obiect oarecare obj primit ca argument, astfel ca expresia c.equals(obj) întoarce true dacă comparatorul c este identic cu argumentul obj. Este posibil ca, pentru aceeași clasă de obiecte, să avem mai multe clase de comparatori, care diferă intre ele prin criteriul după care se face comparația. De exemplu, două persoane pot fi comparate după nume, după locul de muncă, după data nașterii etc.

Amintim că, în limbajul Java, dacă a și b sunt două variabile-referință, expresia a==b are valoarea true dacă, și numai dacă, referințele conținute în aceste două variabile sunt identice, cu alte cuvinte ele indică unul și același obiect din memorie. Când dorim sa verificăm dacă două obiecte distincte (situate în memorie la adrese diferite) sunt identice, folosim metoda
    public boolean equals(Object obj)
din clasa Object, care trebuie redefinită în fiecare clasă.

În această secțiune vom studia câțiva algoritmi simpli de sortare a tablourilor, care pot fi utilizați pentru tablouri cu număr mic de componente. Pentru tablouri mari există algoritmi mai eficienți, pe care îi vom studia ulterior.

Sortarea prin selecție

Una din cele mai intuitive metode de ordonare a datelor într-un tablou este următoarea: se caută în tablou cel mai mic element și se schimbă cu cel de pe prima poziție. Se caută apoi cel mai mic element dintre cele rămase și se aduce în tablou pe poziția a doua și așa mai departe.
 
În pseudocod, acest algoritm se poate formula astfel:

        Fie tabloul tab cu n componente;
        Fie i, j, k numere întregi;
    pentru i de la 0 lan-2{
        /* se caută cel mai mic element de pe pozițiile i .. n-1  */
        k=i; /* s-a notat cu k indicele celui mai mic element */
        pentru j de la i la n-1
           dacă tab[j]<tab[k]
           atunci k=j;
        /* se aduce pe poziția i cel mai mic element de pe pozițiile i .. n-1
           acesta fiind tab[k]
        */
        dacă k este diferit de i
          atunci se interschimbă tab[i] cu tab[k];
    }

Exemplul 1
Fie tabloul
82
37
97
42
Se caută cel mai mic element din întregul tablou și se schimbă cu cel de pe prima poziție (de indice 0). Ordinea elementelor în tablou este acum urmatoarea:
37
82
97
42
Se caută cel mai mic element începând de la cel de indice 1 și se aduce pe această poziție:
37
42
97
82
Se caută cel mai mic element începând cu poziția de indice 2 și se aduce pe această poziție:
37
42
82
97
Ordonarea elementelor s-a încheiat.

Complexitatea acestui algoritm de sortare poate fi evaluată astfel: pentru fiecare valoare a lui i se fac n-i-1 comparații, iar i ia valori de la 0 la n-2, deci ordinul de mărime al numărului de operații elementare este (n-1)+(n-2)+(n-3)+...+1=[(n-1)+1]*(n-1)/2. Aceasta înseamnă că complexitatea algoritmului de sortare prin selecție este O(n2).

Sortarea prin inserție

Se consideră că, pentru o poziție oarecare de indice i, zona de tablou de la indicele 0 la i-1 este deja ordonată. Se ia elementul de pe poziția de indice i și se caută la stânga lui, de la dreapta la stânga, poziția pe care trebuie plasat, astfel încât să se respecte ordinea impusă. Fie aceasta poziția de indice j<i. Elementele de pe pozițiile de la j la i-1 se deplasează cu câte o poziție la dreapta. Repetându-se acest procedeu pentru i de la 1 la n (unde n este numărul de elemente din tablou), se obține un tablou ordonat.
 
In pseudocod, algoritmul de sortare prin inserție 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 poziția i se înserează pe poziția 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 plasează la locul sau corect */
    }

Exemplul 2
Fie acelasi tablou ca în exemplul 1:
82
37
97
42
Se ia elementul de pe poziția de indice 1, și se constată că este mai mic decât cel de la indicele 0, astfel că se pune în locul acestuia, deplasându-l cu o poziție la dreapta.
37
82
97
42
Acum primele două elemente sunt deja ordonate. Pentru i=2 se constată că elementul curent (97) este mai mare decât cel de pe poziția i-1, deci ramâne pe loc.
37
82
97
42
Acum primele trei elemente sunt ordonate. Pentru i=3 se constată că acest element trebuie pus pe poziția de indice 1, iar elementele 82 si 97 trebuie deplasate cu o poziție la dreapta.
37
42
82
97
Ordonarea s-a încheiat.

Pentru a evalua complexitatea acestui algoritm, se constată că pentru fiecare valoare a indicelui i (de la 1 la n-1) se fac cel mult i-1 deplasări. În consecință, ordinul de mărime al numărului de operații elementare este 1+2+3+...+(n-1)=n*(n-1)/2, iar complexitatea este O(n2).

Algoritmul de sortare prin inserție prezintă avantajul că, dacă tabloul dat initial este deja ordonat, sortarea se oprește după prima parcurgere a tabloului și deci complexitatea operatiei devine O(n).

Sortarea prin metoda bulelor

În sortarea prin metoda bulelor se parcurge tabloul, comparându-se între ele numai elementele vecine și permutând aceste elemente dacă nu se găsesc în ordine. După o singură parcurgere, cel mai mare element ajunge pe ultima poziție. Se repetă operația de parcurgere și interschimbare cu cele n-1 elemente rămase, astfel că cel mai mare dintre ele ajunge pe penultima poziție. Se continuă parcurgerile reducând mereu numărul de elemente parcurse, până se ordonează întregul tablou.
 
În pseudocod, acest algoritm se poate exprimă astfel:

        Fie tab un tablou cu n componente;
        Fie i, j numere întregi.
    pentru i de la n-1 la 1 {
        /* prin interschimbări de elemente vecine, se deplasează spre dreapta cel mai mare element din zona de indici 0 .. ipână ajunge pe poziția i
        */
        pentru j de la 1 la i
           dacă tab[j-1]>tab[j]
            atunci se interschimbă tab[j-1]cutab[j];
    }

Se poate modifica acest algoritm, astfel încât sortarea să se oprească în momentul în care se constată că, la încheierea unei parcurgeri a tabloului, nu a fost necesar să se facă nici o permutare de elemente și, deci, tabloul este deja ordonat.

Exemplul 3
Reluăm cazul tabloului din cele două exemple precedente
82
37
97
42
La prima parcurgere, se constată că 82 trebuie interschimbat cu 37, iar 97 trebuie interschimbat cu 42, obtinânduse tabloul
37
82
42
97
Acest tablou nu este încă ordonat, dar cel mai mare element a ajuns pe ultima poziție. Se repetă parcurgerea numai pentru primele trei poziții. Constatăm că este necesar să se permute elementele de pe pozițiile de indici 1 si 2, obtinându-se tabloul
37
42
82
97
Acest tablou este deja ordonat, dar pentru control se mai compara o dată elementele de pe pozițiile 0 si 1, constatându-se că sunt pe pozițiile 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 "Dunărea de Jos" din Galați