Lucrarea nr. 3

		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. In
felul 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<d then
            if a[j].cheie<a[j+1].cheie then j:=j+1;
          if x.cheie<a[j].cheie then begin
            a[i]:=a[j]; i:=j; j:=2*i
          end
          else ret:=True
        end;
        a[i]:=x
      end; {Deplasare}
    begin {HeapSort}
      {constructie ansamblu}
      s:=(N div 2) +1; d:=N;
      while s > 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<d) sa devina ansamblu.
Aceasta procedura este folosita mai intii pentru aducerea 
intregului tablou la structura de ansamblu si apoi pentru 
ordonarea tabloului conform metodei enuntate mai sus.
     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. Se interschimba 
a[i] cu a[j] si se continua parcurgerea tabloului din punctele 
in care s-a ramas, pina cind se gasesc alte doua elemente a[i], 
respectiv a[j] care satisfac proprietatile de mai sus si care 
trebuie interschimbate s.a.m.d. Procesul se termina cind cele 
doua parcurgeri se intilnesc, moment in care tabloul este compus 
din doua partitii: una stinga, cu chei < x.cheie si una dreapta, 
cu chei > 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].cheie<x.cheie do i:=i+1;
          while a[j].cheie>x.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 s<j then Sortare(s,j);
       if d>i 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].cheie<x.cheie do i:=i+1;
            while a[j].cheie>x.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 then begin
            {depune in stiva limitele partitiei drepte}
            is:=is+1; Stiva[is].s:=i; Stiva[is].d:=d
          end;
          d:=j; {trateaza partitia stinga a[s],...,a[j]}
        until s>=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 
          (Radix Sort)
     Aceste metode trateaza cheile de sortat ca numere reprezen-
tate 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.

	 3. Aplicatii
	 Sa se realizeze un program interactiv care apeleaza
metodele de sortare expuse in lucrare. Programul va trebui sa
execute urmatoarele comenzi:
		  R - evaluarea performantelor - se afiseaza timpii de executie,
			  numarul de comparatii de chei (C) si de asignari de elemente (M)
			  corespunzator tuturor metodelor de sortare;
			  tabloul de sortat va avea dimensiunea introdusa de la tastatura,
			  iar elementele sale vor fi o permutare aleatoare a indicilor
			  ( restrictie impusa de binsort )
	  C - analog cu R, dar tabloul va fi creat ordonat crescator
	  D - analog cu R, dar tabloul va fi creat ordonat descrescator
	  X - parasirea programului.
     Se va observa imbunatatirea timpului de executie prin rescrierea functiei 
Biti de la metodele Radix, astfel incit extragerea bitilor sa se faca folosind 
o masca corespunzatoare si operatorii pe biti.