Algoritmi și Programe de Prelucrare a Fișierelor

Operaţia de sortare a unui fişier binar presupune aranjarea articolelor în ordinea crescătoare

(descrescătoare) a valorilor unei zone, numită cheie de sortare. În cazul în care cheia de sortare este

formată dintr-un singur câmp din cadrul articolului, operaţia se numeşte sortare simplă. Sortarea

multiplă presupune aranjarea articolelor după valorile a două sau mai multe câmpuri, alcătuind, prin

juxtapunere, cheia de sortare. Juxtapunerea câmpurilor (nu neapărat adiacente în cadrul articolului) se

realizează pe lungimea efectivă a lor, alcătuind forma canonică a cheii de sortare. De exemplu, dacă

nume şi prenume sunt două câmpuri distincte, declarate de tip STRING, forma canonică a cheii de

sortare după nume şi prenume este dată de lungimea efectivă a fiecărei date de tip şir.

Dacă pentru sortarea simplă cheia poate fi însuşi câmpul din articol, pentru cea multiplă este

necesară o zonă auxiliară de memorie, în care se construieşte cheia de sortare, în forma canonică.

Sortarea unui fişier se poate realiza cu aducerea lui integrală în memorie (sortare în memorie)

sau cu aducerea în memorie a câte unui articol (sortare "direct pe disc"). Indiferent de modul utilizat,

sortarea poate fi realizată printr-unul din algoritmii cunoscuţi pentru masivele de date: sortare prin

interschimbare, prin selecţie, prin inserţie etc.

- Sortarea în memorie este o metodă rapidă şi presupune: citirea întregului fişier în memoria

principală; sortarea efectivă după cheia de sortare; recrearea fişierului pe disc. Metoda se poate aplica

numai fişierelor reduse ca dimensiuni sau cu lungime mică de articol, dată fiind capacitatea limitată a

memoriei interne asociată unui program. Ea poate avea mai multe variante:

- Sortarea cu vehicularea întregului articol presupune memorarea întregului fişier într-un

vector de articole. Compararea pentru sortare se va realiza pe câmpul cheie de sortare, însă

interschimbarea se realizează la nivelul întregului articol.

Exemplu:

Program sortare_1;

type

art=record

grupa:byte;

nume_student:string[30];

medie:real;

end;

var

f:file of art; x:array[1..250] of art;

i,j,n:byte; aux:art;

begin

assign(f,'student.dat'); reset(f):

n:=filesize(f):

for i:=1 to n do read (f,x[i]); {citirea fisierului

initial in memorie}

for i:=1 to n-1 do

for j:=i+1 to n do

if x[i].medie < x[j].medie then

begin

aux:=x[i];

x[i]:=x[j];

x[y]:=aux

end;

close(f); rewrite(f);

for i:=1 to n do write(f,x[i]);

close (f)

Algoritmi şi programe de prelucrare a fişierelor

end.

- Sortarea cu vehicularea cheii şi indexului, presupune memorarea într-un vector numai a

valorii cheii de sortare, împreună cu numărul relativ al articolului din fişierul iniţial (indexul).

Interschimbarea se va realiza la nivelul cheii de sortare, rezultând în final ordinea în care articolele vor

fi scrise în fişier. Deoarece articolele, în întregime, sunt rezidente pe disc, fişierul sortat va fi creat cu

un alt nume fizic, în acces secvenţial, preluând articolele din fişierul iniţial, în acces direct. Cheile de

sortare şi indexurile pot fi memorate în vectori distincţi sau într-unul singur, cu elemente de tip articol.

Exemplu:

program sortare_2;

type

art=record

grupa:byte;

nume_student:string[30];

medie:real;

end;

art_cheie=record

medie:real;

index:byte

end;

var

f,g:file of art; y:art; aux:art_cheie;

x:array[1..250] of art_cheie;

i,j,n:byte;

begin

assign(f,'student.dat'); reset(f);

assign(g,'students.dat'); rewrite(g);

n:=filesize(f):

(* ---------------------------------- *)

for i:=1 to n do

begin

read(f,y);

x[i].medie:=y.medie;

x[i].index:=i-1;

end;

(*-------------------------------------*)

for i:=1 to n-1 do

for j:=i+1 to n do

if x[i].medie <x[j].medie then

begin

aux:=x[i];

x[i]:=x[j];

x[j]:=aux

end;

(*--------------------------------------*)

for i:=1 to n do

begin

seek(f,x[i].index);

read(f,y);

write(g,y)

end;

Algoritmi şi programe de prelucrare a fişierelor

close(f); close(g)

end.