SORTAREA FISIERELOR SECVENTIALE

1. Scopul lucrarii:

prezentarea unor metode de sortare specifice structurilor de tip fisier, structuri caracterizate prin faptul ca la un moment dat este accesibila o singura compo- nenta a lor. In lucrare se vor prezenta patru metode de sortare bazate pe interclasare.

2. Aspecte teoretic

Interclasarea presupune combinarea a doua sau mai multe secvente ordonate intr-o singura secventa, prin selectia repetata a componentelor curent accesibile.

Procesul de sortare implica executia repetata a unui grup de operatii, fiecare operatie tratind intregul set de date. O aseme- nea operatie se numeste faza, iar grupul de operatii care se repeta se numeste trecere.

In cele ce urmeaza vor fi utilizate urmatoarele notatii:

          TYPE TipElement=RECORD
                    cheie:Integer;
                    {alte cimpuri}
               end;
               Banda=FILE OF TipElement;

2.a. Interclasarea cu trei benzi

Principiu: fie "a" secventa care trebuie sortata.
(1) Se imparte a in 2 jumatati: b si c.
(2) Se interclaseaza b cu c, combinind cite un element din fiecare, rezultind perechi ordonate care vor forma o noua secventa a.
(3) Pentru noua secventa a se repeta pasii (1) si (2), combinind insa perechile ordonate in quadruple ordonate.
(4) Se repeta pasii (1) si (2), interclasind quadru- plele in 8-uple s.a.m.d., dublind de fiecare data lungimea sub- secventelor de interclasare, pina la sortarea intregii secvente.

Pentru implementarea acestei metode sint necesare trei benzi magnetice (respectiv trei fisiere pe disc) corespunzatoare sec- ventelor a, b si c. In cadrul acestei metode o trecere se compune din doua faze: injumatatirea (1) si interclasarea (2). Injuma- tatirea se va efectua in asa fel incit un n-uplu ordonat al secventei a sa fie distribuit in intregime pe una din secventele b sau c (sa nu fie divizat intre cele 2 secvente destinatie). In acest scop este bine ca n-uplele ordonate sa fie depuse alterna- tiv in secventele b si c.

Implementarea algoritmului in Pascal:

          procedure Interclasare_3_benzi;
            VAR a,b,c:Banda;
                p,k:Integer;
            procedure Injumatatire(n:Integer);
              VAR x:TipElement;
              procedure ScrieN_uplu(var d:Banda);
                VAR i:Integer;
                begin {ScrieN_uplu}
                  i:=0;
                  while (i < n) and (not Eof(a)) do begin
                    Read(a,x);
                    Write(d,x); i:=i+1
                  end;
                end; {ScrieN_uplu}
              begin {Injumatatire}
                Reset(a); Rewrite(b); Rewrite(c);
                while not Eof(a) do begin
                  ScrieN_uplu(b);
                  ScrieN_uplu(c);
                end;
                Close(a); Close(b); Close(c);
              end; {Injumatatire}
            procedure Interclasare(n:Integer; var s:Integer);
              VAR i,j:Integer;
                  x,y:TipElement;
                  termb,termc:Boolean;
              begin
                Reset(b); Reset(c); Rewrite(a);
                termb:=Eof(b);
                termc:=Eof(c);
                if not termb then Read(b,x);
                if not termc then Read(c,y);
                repeat
                  i:=0; j:=0;
                  {interclasarea unui n-uplu}
                  while (i < n) and (j < n) and not termb and not           
                         termc do begin
                    if x.cheie < y.cheie then begin
                      Write(a,x); i:=i+1;
                      if Eof(b) then termb:=true else Read(b,x)
                    end
                    else begin
                      Write(a,y); j:=j+1;
                      if Eof(c) then termc:=true else Read(c,y)
                    end;
                  end;
                  {copierea restului n-uplului de pe "b"}
                  while (i < n) and not termb do begin
                    Write(a,x); i:=i+1;
                    if Eof(b) then termb:=true else Read(b,x)
                  end;
                  {copierea restului n-uplului de pe "c"}
                  while (j < n) and not termc do begin
                    Write(a,y); j:=j+1;
                    if Eof(c) then termc:=true else Read(c,y)
                  end;
                  if not termb or not termc then s:=s+1;
                until termb and termc;
                Close(a); Close(b); Close(c);
              end; {Interclasare}
            begin {Interclasare_3_benzi}
              p:=1;
              repeat
                Injumatatire(p);                  {pasul (1)}
                k:=0;
                Interclasare(p,k);                {pasul (2)}
                p:=p*2;
              until k=0;
            end; {Interclasare_3_benzi}
Observatie: prin variabila k se returneaza de fapt numarul n-uplelor complete depuse pe "a" inainte de epuizarea lui "b" sau a lui "c".

2.b. Interclasarea echilibrata (cu o singura faza)

Principiu: deriva din interclasarea cu trei benzi prin combinarea fazei de injumatatire cu cea de interclasare, si anume: la interclasarea n-uplelor nu se constituie o singura secventa a (ca la punctul (2) de mai sus) ci, 2n-uplele rezultate sint distribuite imediat pe alte doua benzi.

In felul acesta se economiseste foarte mult timp, deoarece faza de injumatatire, care de fapt nu contribuie direct la sor- tare, consuma jumatate din operatiile de copiere.

Implementarea metodei in Pascal: pentru implementarea meto- dei se foloseste o structura de tablou de fisiere B, cu 4 ele- mente. Se considera ca structura de sortat se afla initial pe B[1]. Ea se distribuie in doua jumatati pe B[2] si B[3], distri- buindu-se pe B[1] si B[4], inversind apoi alternativ rolurile (B[1] si B[4] - secventele sursa, iar B[2] si B[3] - secventele destinatie). In acest scop se utilizeaza variabilele s1, s2 care reprezinta indicii fisierelor sursa, respectiv d1, d2 - indicii fisierelor destinatie la un moment dat. In final fisierul sortat va fi B[d1].

          procedure InterclasareEchilibrata;
            VAR B:ARRAY[1..4] OF Banda;
                s1,s2,d1,d2:1..4;
                i,j,k,p,h:Integer;
                x,y:TipElement;
            procedure Interclasare(n:Integer; var s:Integer);
              VAR d:Integer;
                  term1,term2:boolean;
              begin 
                Reset(B[s1]); Reset(B[s2]);
                Rewrite(B[d1]); Rewrite(B[d2]);
                term1:=Eof(B[s1]);
                term2:=Eof(B[s2]);
                if not term1 then Read(B[s1],x);
                if not term2 then Read(B[s2],y); 
                d:=d1;
                repeat
                  i:=0; j:=0;
                  while (i < n) and (j < n) and not term1
                         and not term2 do begin
                    if x.cheie < y.cheie then begin
                      Write(B[d],x); i:=i+1;
                      if Eof(B[s1]) then term1:=true else 
                              Read(B[s1],x)
                    end
                    else begin
                      Write(B[d],y); j:=j+1;
                      if Eof(B[s2]) then term2:=true else 
                      Read(B[s2],y)
                    end;
                  end;
                  while (i < n) and not term1 do begin
                    Write(B[d],x); i:=i+1;
                    if Eof(B[s1]) then term1:=true else 
                         Read(B[s1],x)
                  end;
                  while (j < n) and not term2 do begin
                    Write(B[d],y); j:=j+1;
                    if Eof(B[s2]) then term2:=true else 
                    Read(B[s2],y)
                  end;
                  if not (term1 and term2) then s:=s+1;
                  if d=d1 then d:=d2 else d:=d1
                until term1 and term2;
                for i:=1 to 4 do Close(B[i]);
              end; {Interclasare}
            begin {InterclasareEchilibrata}
              {impartirea secventei de sortat B[1] in 2 jumatati}
              Reset(B[1]); Rewrite(B[2]); Rewrite(B[3]);
              i:=2;
              while not Eof(B[1]) do begin
                Read(B[1],x);
                Write(B[i],x);
                if i=2 then i:=3 else i:=2;
              end;
              for i:=1 to 3 do Close(B[i]);
              h:=1; p:=1;
              repeat
                if h=1 then begin
                  s1:=2; s2:=3; d1:=1; d2:=4 end
                else begin
                  s1:=1; s2:=4; d1:=2; d2:=3 end;
                k:=0;
                Interclasare(p,k);
                p:=p*2;
                h:=-h;
              until k=0;
              {fisierul sortat se afla pe B[d1]}
            end; {InterclasareEchilibrata}

2.c. Interclasarea naturala

Principiu: spre deosebire de metodele prezentate mai sus, in care subsecventele care se interclaseaza la un moment dat au lungime fixata (2,4,8...), tehnica de interclasare naturala porneste de la faptul ca datele initiale pot fi partial sortate si cauta sa delimiteze subsecventele deja ordonate, pe care apoi le interclaseaza. Notiunea de baza folosita aici este aceea de monotonie, prin care se intelege o secventa partiala ai,...,aj ce satisface urmatoarele conditii:
          i) 1 <= i <= j <= n   (n=lungimea totala a fisierului)
         ii) ak <= ak+1         i <= k <= j-1
        iii) ai-1 > ai    sau i=1
         iv) aj > aj+1    sau j=n
Definitia include si monotoniile cu un singur element, cind i=j.

Sortarea naturala se realizeaza prin interclasarea monotoniilor, avind la baza proprietatea ca daca se interclaseaza doua secvente a cite m monotonii, se obtine o secventa cu exact m monotonii. Algoritmul utilizeaza trei fisiere: a,b - auxiliare si c - fisierul de sortat.

Fiecare trecere este constituita din doua faze alternative:
-defalcarea: delimitarea monotoniilor din cadrul fisierului c si distribuirea acestora pe fisierele a si b;
-interclasarea: monotoniile de pe a si b se combina, formind o noua secventa c.

In faza de defalcare monotoniile gasite sint depuse alternativ in fisierele a si b, astfel incit fie cele doua fisiere vor contine cite un numar egal de monotonii, fie pe a va fi o monotonie in plus fata de b. Dupa interclasarea monotoniilor perechi, monotonia nepereche va fi recopiata in c.

Implementarea algoritmului in Pascal:

          procedure InterclasareNaturala;
            VAR l:Integer;
                a,b,c:Banda;
                terma,termb,termc,sm:Boolean;
                arta,artb,artc:TipElement;
            procedure Copiaza(var x,y:Banda;var artx:TipElement;
                              var termx:boolean);
              var aux:TipElement;
              begin
                write(y,artx);
                if Eof(x) then begin sm:=True;termx:=true end
                          else begin aux:=artx;read(x,artx);
                              sm:=aux.cheie > artx.cheie
              end; {Copiaza}
            procedure CopiazaMonotonia(var x,y:Banda
                         ;var artx:TipElement;var termx:boolean);
              {x - fisierul in care se delimiteaza monotonia
               y - fisierul in care se copiaza monotonia}
              begin
                repeat
                  Copiaza(x,y,artx,termx)
                until sm
              end; {CopiazaMonotonia}
            procedure Defalcare;
              begin
                Rewrite(a);Rewrite(b);Reset(c);
                termc:=Eof(c);
                Read(c,artc);
                repeat
                  CopiazaMonotonia(c,a,artc,termc);
                  if not termc then                         
                         CopiazaMonotonia(c,b,artc,termc)
                until termc;
                Close(a);Close(b);Close(c)
              end; {Defalcare}
            procedure InterclasareMonotonie;
              begin
                repeat
                  if arta.cheie < artb.cheie then begin
                    Copiaza(a,c,arta,terma);
                    if sm then CopiazaMonotonia(b,c,artb,termb)
                  end
                  else begin
                    Copiaza(b,c,artb,termb);
                    if sm then CopiazaMonotonia(a,c,arta,terma)
                  end
                until sm
              end; {InterclasareMonotonie}
            procedure Interclasare;
              begin
                Reset(a); Reset(b); Rewrite(c);
                terma:=Eof(a);
                termb:=Eof(b);
                if not terma then Read(a,arta);
                if not termb then Read(b,artb);
                while not termb do begin
                  InterclasareMonotonie;
                  l:=l+1
                end;
                if not terma then begin
                  CopiazaMonotonia(a,c,arta,terma);
                  l:=l+1
                end;
                Close(a);Close(b);Close(c)
              end; {Interclasare}
            begin {InterclasareNaturala}
              repeat
                Defalcare;
                l:=0;
                Interclasare;
              until l=1;
            end; {InterclasareNaturala}

2.d. Interclasarea multipla echilibrata

Principiu: constituie o imbunatatire a interclasarii natu- rale in sensul reducerii numarului de treceri prin distribuirea monotoniilor pe mai mult decit doua fisiere. Astfel, daca se interclaseaza r monotonii si se distribuie pe N benzi, pe fiecare banda se vor obtine r/N monotonii, la urmatoarea interclasare- distribuire vor rezulta r/N**2 monotonii, apoi r/N**3s.a.m.d. Deci numarul de treceri in acest caz va fi log N (n) (n=lungimea fisierului de sortat).

Interclasarea multipla se poate realiza intr-o singura faza, fapt care presupune ca la fiecare trecere se utilizeaza un numar egal de fisiere de intrare si de iesire, monotoniile de pe primele fiind interclasate si imediat redistribuite pe celelalte.

In continuare presupunem ca in total se folosesc N fisiere, N - par, iar interclasarea se va realiza pe N/2 cai. In program va fi necesara o structura de date de tip tablou de fisiere. Fata de interclasarea naturala (care poate fi privita ca o interclasare multipla cu doua cai) aici apar citeva actiuni suplimentare care trebuie executate:
-gestionarea unei liste de fisiere active, din care se elimina pe rind fisierele ce ramin vide;
-comutarea grupelor de fisiere de intrare si iesire dupa fiecare trecere.

Structurile de date folosite se definesc astfel:

          TYPE NrBanda=1..N; {nr. total de fisiere; N-par}
          VAR f:ARRAY[NrBanda] OF Banda; {cele N fisiere}
              f0:Banda; {fisierul initial care trebuie sortat}
              t:ARRAY[NrBanda] OF NrBanda; {tabela cu indicii 
                                             benzilor}
Tabela t este necesara in vederea comutarii fisierelor de intrare si iesire; astfel: daca notam Nh=N/2, elementele t[1],...,t[Nh] contin indicii benzilor de intrare, iar t[Nh+1],...,t[N] - indicii benzilor de iesire. Initial t[i]=i, i=1,N si dupa fiecare trecere se va realiza interschimbarea t[j] - t[Nh+j] , j=1,Nh

Se mentioneaza ca fisierele nu vor fi accesate direct, ci prin intermediul tabelei t, adica in loc de f[i] se va utiliza f[t[i]].

Pe masura ce avanseaza procesul de sortare, se reduce numarul monotoniilor si ca atare si numarul fisierelor active. Se considera ca sortarea s-a incheiat cind mai ramine un singur fisier activ. In program se va folosi o variabila k1 care va indica numarul actual de fisiere de intrare active.

Descrierea formala a algoritmului:

          procedure InterclasareMultipla;
            VAR i,j,tx:NrBanda;
                l:Integer; {nr. monotonii distribuite}
            begin
              {distribuire monotonii initiale pe t[1]...t[Nh]}
              j:=Nh; l:=0;
              repeat
                if j < Nh then j:=j+1
                        else j:=1;
                {copiaza monotonie de pe f0 pe f[j]}
                l:=l+1
              until Eof(f0);
              for i:=1 to N do t[i]:=i;
              {interclasare de pe t[1]...t[Nh] pe t[Nh+1]...t[N]}
              repeat
                {initializare benzi intrare}
                for i:=1 to Nh do Reset(f[t[i]]);
                l:=0;
                j:=Nh+1; {indicele benzii de iesire}
                repeat
                  l:=l+1;
                  {interclaseaza monotonie de la intrari pe t[j]}
                  if j < N then j:=j+1
                         else j:=Nh+1;
                until {toate fisierele de intrare s-au epuizat}
                {comuta benzile}
                for i:=1 to Nh do begin
                  tx:=t[i]; t[i]:=t[i+Nh];
                  t[i+Nh]:=tx
                end;
              until l=1;
              {banda sortata este f[t[1]]}
            end; {InterclasareMultipla}