TEHNICI DE SORTARE A TABLOURILOR

1. Scopul lucrarii:

prezentarea celor mai cunoscute metode de sortare a tablourilor.

2. Aspecte teoretice

In cele ce urmeaza vom presupune ca tablourile de sortat sint definite dupa cum urmeaza:

  TYPE TipElement=RECORD
                    cheie:Integer;
                    {alte cimpuri}
                  END;
       TipIndex=1..N;
       TipTablou=ARRAY[TipIndex] OF TipElement;
  VAR a : TipTablou;

Se mentioneaza ca tipul cimpului "cheie" poate fi orice tip pe care e definita o relatie de ordonare (intreg, real, sir de caractere, enumerare).

Algoritmii de sortare se deosebesc intre ei prin eficienta, timp de executie necesar, exprimat prin functia O. Sint folositi pentru aprecierea eficientei si: numarul compararilor de chei efectuate pentru sortare (C), mai ales atunci cind cheile sint siruri lungi de caractere si numarul miscarilor (asignarilor) de elemente (M),atunci cind dimensiunea elementelor tabloului este mare, in aceasta situatie fiind indicat ca pentru sortare sa se foloseasca un tablou paralel de cursori la elementele celui initial.

Acesti indicatori depind de numarul elementelor tabloului (N).

2.1 Metode de sortare care nu iau in considerare structura si valorile cheilor.

2.1.1 Metode directe de sortare

Se caracterizeaza prin claritate, simplitate si eficienta pentru valori mici ale lui N (<100), timpii lor de executie fiind O(N*N).

2.1.1.a. Sortarea prin insertie

Principiu: tabloul este vazut ca fiind format din doua subtablouri a[1], a[2],..., a[i-1] si respectiv a[i], a[i+1],...,a[N] (i=2,N). Secventa a[1],...,a[i-1] este ordonata si urmeaza ca a[i] sa fie inserat in aceasta secventa la locul potrivit, astfel incit secventa a[1],...,a[i-1],a[i] sa devina ordonata, urmind ca in pasul urmator cele doua subtablouri considerate sa fie a[1],...,a[i] si a[i+1],...,a[N].

Pentru a gasi locul in care trebuie sa fie inserat a[i] se parcurge sirul a[1],...,a[i-1] de la dreapta spre stinga, pina cind fie se gaseste un element cu cheia <= a[i].cheie, fie s-a atins capatul sirului. Aici se poate utiliza metoda fanionului, extinzind tabloul spre stinga cu elementul a[0] care se asigneaza initial cu a[i] (deci TipIndex=0..N).

Implementarea algoritmului in Pascal:

  procedure Insertie;
    VAR i,j : TipIndex;
    begin
      for i:=2 to N do begin
        {insereaza a[i] la locul potrivit in sirul 
                 a[1]...a[i]}
        a[0]:=a[i]; j:=i-1;
        {cauta locul de inserare}
        while a[j].cheie > a[0].cheie do begin
          a[j+1]:=a[j]; j:=j-1
        end;
        a[j+1]:=a[0]
      end;
    end; {Insertie}

In cazul sortarii prin insertie C si M sint de ordinul N*N, avind valori minime cind tabloul e ordonat si maxime cind tabloul e ordonat descrescator. Aceasta metoda este stabila.

2.1.1.b. Sortarea prin insertie binara

Principiu: reprezinta o varianta a sortarii prin insertie, in care cautarea locului de inserare se face aplicind cautarea binara, stiind ca secventa a[1],...,a[i-1] este deja ordonata.

Implementarea algoritmului in Pascal:

  procedure InsertieBinara;
    VAR i,j,s,d,m : TipIndex; x : TipElement;
    begin
      for i:=2 to N do begin
        x:=a[i]; s:=1; d:=i-1;
        while s<=d do begin
          m:=(s+d) div 2;
          if a[m].cheie > x.cheie then d:=m-1
          else s:=m+1
        end;
        for j:=i-1 downto s do a[j+1]:=a[j];
        a[s]:=x
      end
    end; {InsertieBinara}

In cadrul acestei metode, C este de ordinul N*log N, iar M de N*N. Se obtin valori minime ale lui C pentru tablouri ordonate invers si valori maxime pentru tablouri ordonate.

2.1.1.c. Sortarea prin selectie

Principiu: se considera subtabloul a[i],...,a[N], se cauta elementul cu cheia minima din acest subtablou si apoi se interschimba acest element cu elementul a[i], repetindu-se procedeul pentru valori ale lui i de la 1 la N-1.

Implementarea algoritmului in Pascal:

  procedure Selectie;
    VAR i,j,k : TipIndex; x : TipElement;
    begin
      for i:=1 to N-1 do begin
        k:=i; x:=a[i];
        for j:=i+1 to N do if a[j].cheie < x.cheie then begin
           x:=a[j];
           k:=j
        end;
        a[k]:=a[i]; a[i]:=x
      end
    end; {Selectie}

In cazul sortarii prin selectie C este de ordinul N*N , iar M este de ordinul N*ln N. Aceasta metoda este mai putin rapida pentru tablouri ordonate sau aproape ordonate.

2.1.1.d. Sortarea prin selectie performanta

Principiu: reprezinta o varianta a sortarii prin selectie, in care determinarea elementului cu cheia minima dintr-o portiune de tablou se reduce la determinarea pozitiei acestuia. Infelul acesta se poate renunta la asignarea x:=a[j] care apare in ciclul "for" controlat de j.

Implementarea algoritmului in Pascal:

  procedure SelectiePerform;
    VAR i,j,min : TipIndex; x : TipElement;
    begin
      for i:=1 to N-1 do begin
        min:=i;
        for j:=i+1 to N do if a[j].cheie < a[min].cheie 
                                  then min:=j;
        x:=a[min]; a[min]:=a[i]; a[i]:=x
      end
    end; {SelectiePerform}

2.1.1.e. Sortarea prin interschimbare (bubblesort)

Principiu: se considera subtabloul a[i],...,a[N] care se parcurge de la dreapta spre stinga, comparind si interschimbind perechile de elemente alaturate care nu satisfac relatia de ordine, procedeul repetindu-se pentru i=2,N. Practic, la o parcurgere a subtabloului a[i],...,a[N] are loc deplasarea elementului minim al acestui subtablou pina in pozitia a[i-1].

Implementarea algoritmului in Pascal:

    procedure BubbleSort;
    VAR i,j : TipIndex; x : TipElement;
    begin
      for i:=2 to N do
        for j:=N downto i do
          if a[j-1].cheie>a[j].cheie then begin
             x:=a[j-1];
             a[j-1]:=a[j];
             a[j]:=x
          end
    end; {BubbleSort}

2.1.1.f. Sortarea prin amestecare (shakersort)

Principiu: reprezinta o varianta a metodei bubblesort, avind urmatoarele imbunatatiri:
-la fiecare parcurgere a subtabloului a[i],...,a[N] se memoreaza indicele k al ultimei interschimbari efectuate, astfel incit la urmatoarea trecere un capat al subtabloului va fi marcat de k (intre 1 si k tabloul este ordonat);
-se schimba alternativ sensul de parcurgere al subtablourilor pentru doua treceri consecutive.

Implementarea algoritmului in Pascal:

  procedure ShakerSort;
    VAR j,k,l,r : TipIndex; x : TipElement;
    begin
      l:=2; r:=N; k:=N;
      repeat
        for j:=r downto l do
          if a[j-1].cheie>a[j].cheie then begin
             x:=a[j-1];
             a[j-1]:=a[j];
             a[j]:=x;
             k:=j
          end;
        l:=k+1;
        for j:=l to r do
          if a[j-1].cheie>a[j].cheie then begin
             x:=a[j-1];
             a[j-1]:=a[j];
             a[j]:=x;
             k:=j
          end;
         r:=k-1
       until l > r
    end; {ShakerSort}

La sortarile bubblesort si shakersort, M si C sint proportionali cu N*N, metodele fiind mai putin performante decit cele anterioare.

2.1.2 Metode avansate de sortare

Sint mai complexe, mai dificil de inteles, dar mai rapide, avind timpii de executie O(N*log N).

2.1.2.a. Sortarea prin insertie cu diminuarea incrementului (Shellsort)

Principiu: reprezinta o perfectionare a metodei de sortare prin insertie. Se alege o secventa de numere naturale h1, h2,..., ht numite incrementi, care satisfac conditiile: ht=1 si h(i+1) < hi pentru i=1,t-1

Se realizeaza t treceri asupra tabloului, la fiecare trecere i luindu-se in considerare elementele a[1], a[1+hi], a[1+2*hi] etc. Aceste elemente se sorteaza aplicind metoda insertiei, cu utilizarea fanionului. S-a demonstrat ca eficienta algoritmului creste daca valorile incrementilor nu sint puteri ale lui 2. Pentru a putea folosi tehnica fanionului la aceasta metoda este necesar sa se prelungeasca tabloul a spre stinga cu inca h1 elemente.

Implementarea algoritmului in Pascal:

 
  procedure ShellSort;
    const h1=...;
    var i,j,k,s : -h1+1..N; x : TipElement;
      m : 1..t;
      h : ARRAY[1..t] OF Integer;
      a : ARRAY[-h1+1..N] OF TipElement;
    begin
      {initializarea elementelor lui h}
      for m:=1 to t do begin
        k:=h[m]; s:=-k;  {pozitia fanionului}
        for i:=k+1 to N do begin
          j:=i-k;
          if s=0 then s:=-k;
          inc(s);
          a[s]:=a[i];
          while a[s].cheie < a[j].cheie do begin
            a[j+k]:=a[j]; j:=j-k
          end;
          a[j+k]:=a[s]
        end
      end
    end; {ShellSort}

2.1.2.b. Sortarea prin metoda ansamblelor (heapsort)

Principiu: se numeste ansamblu (heap) a secventa de chei h1, h2,..., hn care satisfac conditiile: hi <= h2i si hi <= h2i+1 i=1,N/2.

Se aduce tabloul la forma unui ansamblu, adica pentru orice i,j, k din intervalul [1,N], unde j=2*i si k=2*i+1, sa avem a[i].cheie<=a[j].cheie si a[i].cheie<=a[k].cheie (*) Se observa ca in acest caz a[1] este elementul cu cheia minima in tablou. Se interschimba elementele a[1] si a[N] si se aduce subtabloul a[1],...,a[N-1] la forma de ansamblu, apoi se interschimba elementele a[1] si a[N-1] si se aduce subtabloul a[1],...,a[N-2] la forma de ansamblu s.a.m.d. In final rezulta tabloul ordonat invers. Daca se schimba sensul relatiilor in conditiile (*) atunci se obtine o ordonare directa a tabloului (a[1] va fi elementul cu cheia maxima).

Aducerea unui tablou la forma de ansamblu se bazeaza pe faptul ca subtabloul a[N/2+1],...,a[N] este deja un ansamblu (nu exista indicii j si k definiti ca mai sus). Acest subtablou se va extinde mereu spre stinga cu cite un element al tabloului, pina cind se ajunge la a[1]. Elementul adaugat va fi glisat astfel incit subtabloul extins sa devina ansamblu.

Implementarea algoritmului in Pascal:

  procedure HeapSort;
    VAR s,d : TipIndex; x : TipElement;
    procedure Deplasare(s,d : TipIndex);
      VAR i,j : TipIndex; ret : Boolean;
      begin {Deplasare}
        i:=s; j:=2*i; x:=a[i]; ret:=False;
        while (j<=d) and (not ret) do begin
          if j 1 do begin
        s:=s-1;
        Deplasare(s,N);
      end;
      {sortare}
      while d > 1 do begin
        x:=a[1]; a[1]:=a[d]; a[d]:=x;
        d:=d-1;
        Deplasare(1,d)
      end
    end; {HeapSort}

Procedura Deplasare(s,d) realizeaza glisarea elementului a[s] astfel ca subtabloul a[s],...,a[d] (s Timpul de executie al sortarii este O(N*log N).

2.1.2.c Sortarea prin partitionare (quicksort)

Principiu: se alege un element oarecare a[k] al tabloului (1<=k<=N) si vom nota cu x valoarea acestui element. Se parcurge tabloul de la stinga, pina cind se gaseste primul element a[i].cheie>x.cheie. Apoi se parcurge tabloul de la dreapta, pina cind se gaseste primul element a[j].cheie x.cheie.

Procedura descrisa se aplica in continuare pe rind celor doua partitii obtinute, apoi celor patru partitii s.a.m.d., pina cind fiecare partitie ajunge sa fie formata dintr-un singur element.

Implementarea algoritmului in Pascal: metoda Quicksort se poate implementa in doua moduri: recursiv si nerecursiv. In ambele cazuri s-a convenit ca elementul x sa fie ales la mijlocul tabloului (respectiv partitiei).

  procedure QuickSort_Recursiv;
    VAR m:TipIndex;
    procedure Sortare(s,d:TipIndex);
      VAR i,j:TipIndex;
          x,w:TipElement;
      begin
        i:=s; j:=d; x:=a[(s+d) div 2];
        repeat
          while a[i].cheiex.cheie do j:=j-1;
          if i<=j then begin
            w:=a[i]; a[i]:=a[j]; a[j]:=w;
            i:=i+1; j:=j-1
          end
       until i>j;
       if si then Sortare(i,d);
      end; {Sortare}
    begin
      m:=1;
      Sortare(m,N)
    end; {QuickSort_Recursiv}

  procedure QuickSort_Nerecursiv;
    CONST m=12; {dimensiunea stivei}
    TYPE NodStiva=RECORD
                    s,d:TipIndex
                  end;
    VAR i,j,s,d:TipIndex;
        x,w:TipElement;
        is : 0..m;
        Stiva : ARRAY[1..m] OF NodStiva;
    begin
      is:=1; Stiva[1].s:=1; Stiva[1].d:=N;
      repeat
        {extragere limite partiale din virful stivei}
        s:=Stiva[is].s; d:=Stiva[is].d; is:=is-1;
        repeat
          {partitionarea sirului a[s],...,a[d]}
          i:=s; j:=d; x:=a[(s+d) div 2];
          repeat
            while a[i].cheiex.cheie do j:=j-1;
            if i<=j then begin
              w:=a[i]; a[i]:=a[j]; a[j]:=w;
              i:=i+1; j:=j-1
            end
          until i>j;
          if i=d
      until is=0
    end; {QuickSort_Nerecursiv}

In cazul algoritmului nerecursiv este necesara o stiva care memoreaza limitele uneia dintre cele doua partitii care apar la o trecere, si anume limitele partitiei care este tratata a doua (aici, partitia dreapta). Timpul de executie este O(N* log N) si O(N*N),in cazul cel mai defavorabil.

2.2. Metode de sortare care tin cont de valorile cheilor

2.2.1. Tehnica binsort

Se poate aplica in cazul in care cheile sint valori de tip intreg cuprinse in intervalul 1..N si nu exista duplicate. Principiu: se parcurge tabloul a, verificindu-se daca elementul a[i] are cheia j egala cu i. Daca j<>i se interschimba elementele a[i] si a[j].

Implementarea algoritmului in Pascal:

  procedure BinSort;
    VAR i:TipIndex;
        temp:TipElement;
    begin
      for i:=1 to N do
        while a[i].cheie<>i do begin
          temp:=a[i];
          a[i]:=a[temp.cheie];
          a[temp.cheie]:=temp
       end
    end; {BinSort}

Timpul de executie este O(N).

2.3. Metode de sortare care folosesc baze de numeratie (RadixSort)

Aceste metode trateaza cheile de sortat ca numere reprezentate intr-o anumita baza de numeratie R (radix) si lucreaza cu cifrele individuale ale numarului. Pentru implementarea pe sisteme de calcul se preteaza metodele care utilizeaza R=2 si care lucreaza deci cu bitii ce formeaza numerele.

In sortarea radix cu R=2 operatia fundamentala necesara este extractia unui set contiguu de biti dintr-un numar. In Pascal aceasta operatie se poate simula cu ajutorul operatorilor "div" si "mod". Ca atare se va defini o functie care va returna "j biti care apar la k pozitii de la marginea dreapta a lui x", unde x este numarul considerat:

  function Biti(x,k,j:Integer):Integer;
    VAR doik,doij,i:Integer;
    begin
      doik:=1; doij:=1;
      for i:=1 to k do doik:=doik*2; {2 la puterea k}
      for i:=1 to j do doij:=doij*2; {2 la puterea j}
      Biti:=(x div doik) mod doij
    end; {Biti}

2.3.a Sortarea radix prin interschimbare

Principiu: se bazeaza pe faptul ca rezultatul comparatiei a doua chei este determinat numai de valoarea bitilor din prima pozitie la care ele difera (considerind bitii de la stinga spre dreapta). Astfel, cheile care au primul bit=0 sint trecute in fata celor care au primul bit=1; in continuare in fiecare grup se aplica aceeasi metoda, pentru bitul urmator s.a.m.d. Procesul se desfasoara ca si la metoda Quicksort: se baleiaza tabloul de la stinga spre dreapta pina se gaseste o cheie care incepe cu 1; se baleiaza apoi de la dreapta spre stinga pina se gaseste o cheie care incepe cu 0; se interschimba cele doua chei; se continua in felul acesta pina cind indicii de parcurgere se intilnesc: in acest moment tabloul are doua partitii. Se reia procedura expusa, considerind al doilea bit, pentru fiecare din partitiile rezultate etc.

Implementarea algoritmului in Pascal:

  procedure RadixSchimb(s,d:TipIndex; b:Integer);
    {s,d - limitele partitiei de sortat
     b - lungimea cheii-1 exprimata in biti=14 (chei pozitive)}
    VAR i,j:TipIndex;
        t:TipElement;
    begin
      if (d>s) and (b>=0) then begin
        i:=s;j:=d;
        repeat
          while (Biti(a[i].cheie,b,1)=0) and (i < j) do i:=i+1;
          while (Biti(a[j].cheie,b,1)=1) and (i < j) do j:=j-1;
          t:=a[i]; a[i]:=a[j]; a[j]:=t
        until j=i;
        if Biti(a[d].cheie,b,1)=0 then j:=j+1;        {*}
        RadixSchimb(s,j-1,b-1);
        RadixSchimb(j,d,b-1)
      end
    end; {RadixSchimb}

Instructiunea marcata cu "*" are ca efect refacerea lungimii partitiei daca toti bitii testati sint 0.

Pentru o distributie normala a bitilor metoda lucreaza mai repede chiar si decit Quicksort.

2.3.b. Sortarea radix directa

Principiu: Examineaza toti bitii care formeaza cheia de la dreapta la stinga, considerind cite "m" biti deodata (unde "m" este un divizor al lungimii cheii - "b"). In felul acesta sortarea se executa in b/m treceri. Aplicarea acestei metode de sortare presupune folosirea unui tablou auxiliar T care memoreaza rezultatul fiecarei treceri, precum si a unui tablou Numar care sa contina distributia cheilor in raport cu cei "m" biti considerati la un moment dat: adica pentru fiecare combinatie posibila de "m" biti trebuie sa se determine numarul cheilor care contin acea combinatie; de aici rezulta ca dimensiunea tabloului Numar este 2**m. Pentru ca algoritmul sa functioneze corect este necesar ca fiecare sortare dupa "m" biti sa fie stabila.

Se observa ca numarul de treceri se reduce daca "m" este mare, ceea ce conduce insa la cresterea dimensiunii tabloului Numar. S-a constatat ca metoda este eficienta pentru m=4 sau m=8.

Implementarea algoritmului in Pascal:

  procedure RadixDirect;
    VAR i:TipIndex;
        j,k:0..M1;   {M1 = 2**m-1}
        Trecere:Integer;
        Numar:ARRAY[0..M1] OF Integer;
        T:TipTablou;
    begin
      for Trecere:=0 to (b div m)-1 do begin
        for j:=0 to M1 do Numar[j]:=0;
        for i:=1 to N do begin
          k:=Biti(a[i].cheie,Trecere*m,m);
          Numar[k]:=Numar[k]+1;
        end;
        for j:=1 to M1 do {*}
          Numar[j]:=Numar[j-1]+Numar[j];
        for i:=N downto 1 do begin  {**}
          k:=Biti(a[i].cheie,Trecere*m,m);
          T[Numar[k]]:=a[i];
          Numar[k]:=Numar[k]-1;
        end;
        for i:=1 to N do a[i]:=T[i];
      end;
    end; {RadixDirect}

Observatii: in ciclul "for" notat cu "*" se determina practic indicii in tabloul T la care vor fi plasate elementele tabloului a la fiecare trecere; in ciclul "for" notat cu "**" tabloul a este parcurs de la sfirsit spre inceput pentru a se respecta necesitatea ca sortarea dupa "m" biti sa fie stabila.