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;
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".
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}
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}
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}