| CATEGORII DOCUMENTE |
Presupunem existenta unui numar de inregistrari care contin cate un camp numit cheie dupa care se face cautarea sau sortarea. Cautarea este operatia prin care se localizeaza inregistrarea care contine cheia data. Sortarea reprezinta ordonarea unor elemente dupa o anumita informatie (cea din campul cheie). Cautarea si sortarea se pot face dupa una sau mai multe chei, in cazul in care mai multe campuri ale inregistrarii au statutul de chei. Existenta mai multor chei nu presupune ca se face cautarea (sortarea) dupa toate.
Aceste inregistrari se pastreaza:
- in memorie daca nu sunt foarte mari sau foarte multe
- pe suport extern, in fisiere, daca inregistrarile ocupa mult spatiu sau daca se doreste ca informatiile sa fie nevolatile
Pentru generalitate vom presupune ca indiferent unde sunt pastrate informatiile se lucreaza tot cu fisiere. Fisierele vor fi impartite in doua categorii:
fisiere interne: reprezentate ca structuri de date in memoria interna a calculatorului (tablouri, liste, etc)
fisiere externe, care sunt fisierele obisnuite pastrate pe suport extern (de remarcat insa ca nu toate organizarile de fisiere implica existenta unor chei)
Algoritmii pot fi diferiti daca se refera la informatia din memorie sau la informatia de pe disc. Exista metode de sortare si de cautare interna si exista metode specifice pentru cautare si sortare externa. Numai fisierele interne vor face obiect de studiu in acest curs.
Se presupune fisierul intern f care are elementele f[n] f[n-1].f[1] din care in procesul de cautare vor fi considerate cheile:
f[n].cheie f[n-1].cheie . f[1].cheie
Nu vom descrie structura elementelor sortate sau printre care se face cautarea. Importanta este numai existenta unei chei.
Daca inregistrarile din fisier nu respecta nici o relatie de ordine din punct de vedere al valorii cheilor, se face o cautare exhaustiva (trebuie parcurse toate elementele). Cautarea se opreste daca se gasesc informatiile dorite.
Algoritmul este prezentat in Figura 1.
type inregistrare = record
cheie:integer;
alte_inf:campuri;
end;
fis_int=array[0.n] of inregistrare;
procedure caut_secv (f: fis_int; var i: integer; n,k: integer);
begin
f[0].cheie:=k;
i:=n;
while f[i].cheie<>k do
i:=i-1;
end
Figura 1. Cautare secventiala
In cazul unui fisier cu cheile ordonate se pot utiliza metode de cautare mult mai eficiente. Cautarea binara este o astfel de metoda. Presupunem un fisier cu n inregistrari si o sortare a cheilor in ordine nedescrescatoare (alfabetic pentru siruri de caractere)
Dupa fiecare comparatie multimea de chei in care mai trebuie cautat se injumatateste. Dupa j cautari multimea mai contine [n/2j] elemente (n numar intreg). Cazul cel mai nefavorabil necesita O(log n) comparatii.
Algoritmul este prezentat in Figura 2.
procedure cautare_binara (f: fis_int; var i: integer; n,k: integer);
var gata: boolean;
j,u,m: integer;
begin
i:=0;
j:=1;
u:=n;
gata:=false;
while (j<=u) and (not gata) do begin
m:=(j+u)div 2;
case compara(k,f[m].cheie) of
'>': j:=m+1;
'=': begin
i:=m;
gata:=true;
end
'<': u:=m-1;
end;
end;
end;
Figura 2. Cautare binara
Algoritmul este echivalent cu un arbore de decizie. Nodurile reprezinta numarul cheii testate. In Figura 3 este prezentat arborele de decizie pentru n=1
Figura 3. Arborele de decizie echivalent
Zona de fisier in care trebuie sa se mai caute poate fi impartita nu in parti egale, ci in concordanta, de exemplu, cu sirul numerelor Fibonacci. Se pot elimina astfel de la cautarea urmatoare mai mult de jumatate dintre elemente.
Sirul Fibonacci se defineste recursiv astfel:
F
F
Fi=Fi-1 + Fi-2 i
Avantajul utilizarii numerelor din sirul Fibonacci consta si in eficienta sporita datorita faptului ca elementele se pot calcula recursiv numai prin adunari si scaderi (timp de calcul mai mic decat la inmultiri si impartiri).
Fie n=Fa-1. Se compara k intai cu f[Fa-1].cheie
daca k<f[Fa-1].cheie T se cauta in continuare printre 1 . Fa-1-1 (Marime fisier Fa-1
daca k=f[Fa-1].cheie T succes, s-a gasit elementul cautat
(3) daca k>f[Fa-1].cheie T se cauta in Fa-1+1 Fa-1 (Marime fisier Fa-1-( Fa-1+1)+1= Fa-2
Algoritmul este prezentat in Figura 4.
procedure cautare_Fibonacci(g: fis_int; var i:integer; n,k:integer);
var gata: boolean;
p,q,t,a: integer;
begin
a:=fibindex(n+1);
i:=fib(a-1);
p:=fib(a-2);
q:=fib(a-3);
m:=n+1-(i+p);
if k>g[i].cheie then
i:=i+m;
gata:=false;
while (i<>0) and (not gata) do
case compara(k,g[i].cheie) of
'<': if q=0 then i:=0;
else begin
i:=i-q;
t:=p;
p:=q;
q:=t-q;
end;
'<': if p=1 then i:=0;
else begin
i:=i+q;
p:=p-q;
q:=q-p;
end;
'=': gata:=true;
end;
end;
end
Figura 4. Cautare Fibonacci
In cadrul aplicatiilor de la cursul de Programare s-au implementat algoritmi de sortare cum ar fi: sortare prin selectie, sortare prin metoda bulelor ("bubble sort") si prin metoda bulelor cu treceri alternante, algoritmi in general ineficienti, cu complexitate cel putin O(n
Consideram fisierul intern f completat la stanga cu o inregistrare f[0], caruia i se asociaza cheia - . Inregistrarile din fisier sunt puse in corespondenta (din punctul de vedere al algoritmului) cu sirul R , R , , Rn
R R Rn
f[1] f[n]
Se presupune ca elementele fisierului intern se impart in doua zone, una deja sortata si una din care se iau elemente care se vor introduce in prima zona (algoritm Greedy). In zona cu elemente deja sortate exista o relatie de ordine: f[1].cheie f[i].cheie.
Se cere sa se introduca un nou element astfel incat sa se pastreze ordinea.
Intitial, zona deja sortata cuprinde numai R , R iar sortarea inseamna n-1 insertii.
type fis_int= array [0maxn] of inregistrare;
procedure insert (r: inregistrare; var list: fis_int; i: integer);
var j:integer;
begin
j:=i;
while r.cheie<list[j].cheie do begin
list[j+1]:=list[j];
j:=j-1;
end;
list[j+1]:=r;
end
procedure sort_insert (var list:fis_int; n:integer);
var j:integer;
begin
list[0].cheie= -maxint;
for j:=2 to n do
insert(list[j],list,j-1);
end;
Figura 5. Algoritmul de sortare prin insertie
La fiecare parcurgere multimea elementelor nesortate se micsoreaza cu un singur element. Un exemplu este prezentat in Figura 6. Multimea elementelor nesortate este prezentata intre paranteze drepte [].
5 [4 3 2 1]
4 5 [3 2 1]
3 4 5 [2 1]
2 3 4 5 [1]
1 2 3 4 5 []
Figura 6. Exemplu de sortare prin insertie
Algoritmul cu comportarea medie cea mai buna este Quicksort ("sortare rapida"). Optimizarea adusa de acest algoritm consta in aceea ca elementele dintr-un sir de elemente nesortate se impart in doua multimi:
o multime de elemente nesortate care prin sortare isi vor schimba pozitia dar care si-au gasit locul in raport cu elementul de referinta
o multime de elemente care si-au gasit pozitia in sir
La sortarea prin insertie, cheia ki se pune in pozitia corecta in raport cu cheile deja sortate ale inregistrarilor R Ri-1. La sortarea prin metoda Quicksort cheia se pune la locul ei in raport cu intregul fisier.
Daca ki este in pozitia s(i) atunci kj ks(i) pentru j<s(i) si kj ks(i) pentru j>s(i). Dupa aceasta pozitionare fisierul original este partitionat in 2 subfisiere R Rs(i)-1 si Rs(i)+1 Rn
Cele doua se pot sorta independent prin aceeasi metoda, ceea ce conduce la ideea de recursivitate. Un exemplu este prezentat in Figura 7. La fiecare pas prin paranteze drepte se indica multimi nesortate inca, dar care contin elemente deja selectate in raport cu un element de referinta. S-au notat cu m si n indicii primului si ultimului element din multimea cu care se lucreaza la un moment dat.
|
R1 |
R2 |
R3 |
R4 |
R5 |
R6 |
R7 |
R8 |
R9 |
R10 |
m |
n |
|
| |||||||||||
Figura 7. Sortare prin metoda Quicksort (exemplu)
Algoritmul care implementeaza aceasta metoda de sortare este prezentat in Figura 8.
procedure qsort(var lista: fis_int; m,n:integer)
( i si j se folosesc pentru a partitiona subsirul
lista[l].cheie <=k T l<i
lista[l].cheie >=k T l>j
se presupune ca lista[m].cheie<=lista[n+1].cheie din evolutia anterioara a sortarii}
var i,j,k: integer;
begin
if m<n then begin
i:=m;
j:=n+1;
k:=lista[m].cheie;
repeat
repeat
i:=i+1;
until lista[i].cheie>=k;
repeat
j:=j-1;
until lista[j].cheie<=k;
if i<j then
interschimba(lista[i],lista[j]);
until i>=j;
interschimba(lista[m],lista[j]);
qsort(lista,m,j-1);
qsort(lista,j+1,n);
end;
end
Figura 8. Algoritmul "quicksort"
Metodele studiate au in cazul cel mai nefavorabil complexitatea O(n2). Se demonstreaza ca daca singurele operatii permise asupra cheilor sunt comparatii si interschimburi, cel mai bun timp posibil al unui algoritm este O(n*log n). Exista deci un timp limita inferior pentru sortare.
Interclasarea este operatia care asaza elementele unui fisier sortat printre elementele altui fisier sortat pentru a obtine un al treilea fisier sortat continand elementele primelor doua fisiere.
In cele ce urmeaza vor fi prezentate doua abordari ale sortarii prin interclasare:
o abordare iterativa cunoscuta sub numele "2-way merge sort"
o abordare recursiva
Fisierul de intrare care trebuie sortat este privit ca un ansamblu de n fisiere sortate, fiecare de lungime 1. Sunt interclasate perechile de fisiere vecine si se obtin n/2 fisiere de dimensiune 2 (si eventual un fisier de lungime 1). Se interclaseaza fisierele de lungime 2, apoi cele de lungime 4 si asa mai departe pana se obtine un singur fisier sortat.
In Figura 9 este prezentat un exemplu de sortare prin interclasare in care intre paranteze drepte au fost indicate fisierele deja sortate la momentul respectiv. Daca fisierul nu are un numar de elemente putere a lui 2, ultimul fisier va fi mereu mai scurt sau nu va avea pereche cu care sa fie interclasat.
|
[26] | |||||||||
|
| |||||||||
|
| |||||||||
|
| |||||||||
|
| |||||||||
Figura 9. Sortare prin interclasare (metoda iterativa)
Deoarece in primul pas fisierele au lungimea 1, la al doilea au lungimea 2, la al i-lea pas ele vor avea lungimea 2i-1. In total se fac [log n] treceri asupra datelor.
Deoarece doua fisiere pot fi interclasate in timp liniar, fiecare pas necesita un timp O(n) si, deoarece sunt log n treceri, timpul total va fi O(n*log n)
Algoritmul de interclasare a doua fisiere vecine xp xm si xm+1 xn este prezentat in Figura 10a. In Figura 10b este prezentat algoritmul care realizeaza un pas in procesul de sortare iar in Figura 10c algoritmul de sortare prin interclasare.
procedure merge(var x,z: fis_int; p,m,n: integer);
var i,j,k,t: integer;
begin
i:=p;
k:=p;
j:=m+1;
while (i<=m) and (j<=n) do begin
if x[i].cheie<=x[j].cheie then begin
z[k]:=x[i];
i:=i+1;
end
else begin
z[k]:=x[j];
j:=j+1;
end
k:=k+1;
end;
if i>m then
for t:=j to n do
z[k+t-j]:=x[t];
else
for t:=i to m do
z[k+t-i]:=x[t];
end
Figura 10a. Algoritmul de interclasare
procedure mpass(var x,y: fis_int; n,p:integer);
var i,t: integer;
begin
i:=1;
while i<=(n-2*p+1) do begin
merge(x,y,i,i+p-1,i+2*p-1);
i:=i+2*p;
end;
if (i+p-1)<n then
merge(x,y,i,i+p-1,n);
else
for t:=1 to n do
y[t]:=x[t];
end
Figura 10b.
procedure msort(var x:fis_int; n:integer);
var p: integer;
y: fis_int;
begin
p:=1;
while p<n do begin
mpass(x,y,n,p);
p:=2*p;
mpass(y,x,n,p);
p:=2*p;
end;
end
Figura 10c. Sortare prin interclasare
Fisierul se imparte in doua parti egale si fie ele stanga si dreapta. Acestea sunt sortate utilizand algoritmul recursiv adica sunt si ele la randul lor impartite in doua liste egale. Interclasarea propriu-zisa se face cand listele au atins lungimea 1 si se iese din recursivitate. In Figura 11 este prezentat un exemplu.
|
[26] | |||||||||
|
| |||||||||
|
|
|||||||||
|
| |||||||||
|
| |||||||||
Figura 11. Sortare prin interclasare - abordare recursiva (exemplu)
Se remarca faptul ca fisierele in care se divizeaza fisierul initial in vederea sortarii sunt diferite de cele de la metoda iterativa prezentata anterior.
Daca fisierul curent are limitele li si ls atunci fisierele in care el se subdivide sunt li (li+ ls)/2 si (li+ ls)/2+1 ls. In procesul de interclasare este necesara copierea de subfisiere dintr-un tablou in altul. Aceasta se poate evita utilizand liste cu alocare statica. Elementele raman pe loc, se modifica numai legaturile lor spre elementul succesor/predecesor care se schimba in procesul de sortare.
Pe langa cheie si alte informatii utile, fiecare element al fisierului are si un camp .urm (care initial are valoarea nil pentru toate elementele, deci lista este impartita in n liste cu cate un element fiecare. In Figura 12 este prezentat algoritmul de sortare prin interclasare in varianta recursiva.
Variabilele q si r joaca rolul de pointeri la doua lanturi de inregistrari care sunt interclasate utilizand rmerge(q,r,s). Se obtine ca rezultat un pointer s spre lantul rezultat din interclasare. Elementele tuturor sirurilor, atat cele care se interclaseaza cat si cele care rezulta, raman pe loc in fisierul intern. Se modifica numai legaturile dintre ele. Se considera existenta unui prim element x[0] folosit pentru a pastra in campul sau .urm pointerul spre inceputul sirului rezultat din sortare.
Pentru a sorta sirul x , x , , xn dupa cheile asociate elmentelor se apeleaza rmsort(x,p,n,s) care intoarce in s inceputul sirului rezultat din sortare.
type inregistrare = record
cheie: integer;
alt: alt_tip;
urm: integer;
end;
fis_int = array [0n] of inregistrare;
procedure rmerge(x:fis_int; u,y: integer; var z:integer);
var i,j:integer;
begin
i:=u;
j:=y;
z:=0;
while (i<>0) and (j<>0) do
if x[i].cheie<= x[j].cheie then begin
x[z].urm:=i;
z:=i;
i:=x[i].urm;
end
else begin
x[z].urm:=j;
z:=j;
j:=x[j].urm;
end;
if i=0 then
x[z].urm:=j;
else
x[z].urm:=i;
z:=x[0].urm;
end
procedure rmsort (var x:fis_int; li,ls: integer; var p:integer);
var m,q,r: integer;
begin
if li>=ls then p:=li
else begin
m:= (li+ls) div 2;
rmsort(x,li,m,q);
rmsort(x,m+1,ls,r);
rmerge(x,q,r,p);
end;
end
Figura 12. Sortare prin interclasare (abordare recursiva)
In algoritmul de sortare prin selectie se alege cel mai mic dintre n elemente (efectuand n-1 comparatii), apoi cel mai mic dintre n-1 elemente (efectuand n-2 comparatii) s.a.m.d. In final se alege minimul dintre doua elemente (cu o comparatie).
Performantele algoritmului s-ar putea imbunatati daca la fiecare trecere s-ar retine mai multe informatii decat pozitia minimului. Astfel:
la prima trecere, utilizand n/2 comparatii se determina cel mai mic din fiecare pereche
la a doua trecere, din n/4 comparatii se determina cel mai mic din fiecare doua perechi etc
Cu numai n-1 comparatii se poate construi un arbore in care radacina este cel mai mic dintre toate elementele sirului (asa cum rezulta din Figura 13).
Figura 13. Informatia culeasa in compararea elementelor
Se extrage radacina (elementul cu cheia minima) care va fi primul element din sirul sortat (a se vedea Figura 14a). Se coboara pe calea pe care nodurile au drept cheie cheia din radacina si se indeparteaza aceasta cheie din arbore. In pasul urmator se reface radacina arborelui alegand elementul mai mic dintre cheile descendentilor in nodurile in care informatia a fost stearsa.
Figura 14a.
In desenul prezentat in Figura 14b cheia 12 a fost aleasa ca cea mai mica dintre cheile ramase si urmeaza sa fie eliminata.
Figura 14b.
Dupa n pasi arborele este gol si sortarea incheiata. Fiecare pas cere numai log n comparatii. In total, intregul parcurs de sortare cere n*log n comparatii, plus cele n necesare construirii arborelui (rezultat mult mai bun decat n ). Fiecare pas este insa mult mai elaborat.
S-a cautat o organizare a arborelui care sa creasca eficienta:
sa nu se mai pastreze goluri care complica inutil comparatiile
arborele sa fie memorat in numai n celule in loc de 2n-1
O metoda de sortare "tree" care satisface aceste cerinte este metoda heapsort.
O movila sau heap este o secventa de chei hq, hq+1, , hr astfel incat hi h2i si hi h2i+1 pentru oricare i=l, , r/2.
Daca un tablou h h are intre elemente relatii care permit desenarea arborelui din Figura 15 el este heap si, in particular, h =min(h , , hn
Figura 15. Movila (heap)
Se da un heap cu elementele hq+1, , hr cu valori precizate pentru q si r si se cere sa se adauge un nou element pentru a forma heap-ul extins hq hr
Aceasta operatie se
numeste extindere la stanga.
De exemplu se considera movila din Figura 16a si se cere sa
fie "extinsa la stanga" cu hq=44. Se
insereaza valoarea 44 sus in arbore si apoi ea aluneca in
jos pe calea cu elemente mai mici care se ridica pentru a-i lua locul.
Algoritmul acesta se numeste sifting. Prin aplicarea lui se
obtine situatia prezentata in Figura 16b.
Figura 16a.
Se da un tablou h hn si se cere modificarea ordinii elementelor astfel incat in final sa formeze un heap. Elementele h(n+1)/2 hn formeaza deja un heap pentru ca nu exista doi indici i si j astfel incat j=2i sau j=2i+1 (i, j sunt indicii care marcheaza elementele ce trebuie schimbate intre ele la fiecare pas). Ele formeaza randul de jos al arborelui binar asociat (marcat cu *)); intre ele nu se impune vreo relatie de ordine. Heap-ul este extins spre stanga, la fiecare pas incluzand un nou element prin utilizarea procedurii sift. Algoritmul lui Floyd este prezentat in Figura 17.
procedure sift(q,r: indice);
label 13;
var i,j:indice; x:element;
begin
i:=q;
j:=2*i;
x:=a[i];
while j<=r do begin
if j<r then
if a[j].cheie>a[j+1].cheie then j:=j+1;
if x.cheie <=a[j].cheie then goto 13;
a[i]:=a[j];
i:=j;
j:=2*i;
end;
a[i]:=x;
end
Figura 17. Algoritmul lui Floyd
Pentru a se realiza sortarea unui sir se incepe prin a construi un heap prin extinderi succesive la stanga. In Figura 18 este considerat un exemplu in care sirul dat are 8 elemente h , h , , h
|
h1 |
h2 |
h3 |
h4 |
h5 |
h6 |
h7 |
h8 |
|
| |||||||
|
| |||||||
|
|
|
Figura 18. Construirea unei movile (heap)
Pentru a obtine elemente sortate se fac n pasi de sift. Pe masura ce se obtin elementele deja sortate, ele trebuie pastrate undeva. Acestea sunt mereu elementele din varful arborelui. Solutia adoptata in metoda heapsort este urmatoarea: la fiecare pas se ia ultimul element, fie el x, se scoate din heap, se pune elementul din varful heapului in locul lui x si se sifteaza x in pozitia corecta. In acest fel se reface heapul 'stricat prin scoaterea elementului minim.
Algoritmul pentru un pas in sortare este prezentat in Figura 19.
r:=n;
while r>1 do begin
x:=a[1];
a[1]:=a[r];
a[r]:=x;
r:=r-1;
sift(1,r);
end
Figura 19. Un pas in sortare
In Figura 20 este prezentat un exemplu complet de sortare a unui sir prin metoda heapsort. Dupa construirea heap-ului, elementele minime se duc pe rand pe ultima pozitie a heap-ului. Zona de culoare gri contine elementele deja sortate.
|
h1 |
h2 |
h3 |
h4 |
h5 |
h6 |
h7 |
h8 | |
|
|
Heap |
|||||||
|
Sir sortat |
Figura 20. Exemplu complet heapsort
Sirul este sortat descrescator. Ar rezulta crescator daca s-ar schimba ordinea in sift. Algoritmul heapsort complet este prezentat in Figura 21.
procedure heapsort;
var q,r: indice; x:element;
procedure sift;
var i,j: indice;
gata: boolean;
begin
i:=q;
j:=2*i;
x:=a[i];
gata:=false;
while (j<=r) and (not gata) do begin
if j<r then
if a[j].cheie>a[j+1].cheie then
j:=j+1;
if x.cheie<=a[j].cheie then gata:=true
else begin
a[i]:=a[j];
i:=j;
j:=2*i;
end;
end;
a[i]:=x;
end;
begin
q:=(n div 2)+1;
r:=n;
while q>1 do begin
q:=q-1;
sift;
end
while r>1 do begin
x:=a[1];
a[1]:=a[r];
a[r]:=x;
r:=r-1;
sift;
end;
end;
Figura 21. Heapsort
Curs editat de Monica Popa (Grupa 313CA)
|
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 2116
Importanta: 
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved
