CLASE DE ALGORITMI

Cautarea si Sortarea sunt doua dintre cele mai des intalnite subprobleme in programare. Ele constituie o parte esentiala din numeroasele procese de prelucrare a datelor. Operatiile de cautare si sortare sunt executate frecvent de catre oameni in viata de zi cu zi, ca de exemplu cautarea unui cuvant in dictionar sau cautarea unui numar in cartea de telefon.

Cautarea este mult simplificata daca datele in care efectuam aceasta operatie sunt sortate (ordonate, aranjate) intr-o anumita ordine (cuvintele in ordine alfabetica, numerele in ordine crescatoare sau descrescatoare).

Sortarea datelor consta in rearanjarea colectiei de date astfel incat un camp al elementelor colectiei sa respecte o anumita ordine. De exemplu in cartea de telefon fiecare element (abonat) are un camp de nume, unul de adresa si unul pentru numarul de telefon. Colectia aceasta respecta ordinea alfabetica dupa campul de nume.

Daca datele pe care dorim sa le ordonam, adica sa le sortam, sunt in memoria interna, atunci procesul de rearanjare a colectiei il vom numi sortare interna, iar daca datele se afla intr-un fisier (colectie de date de acelasi fel aflate pe suport extern), atunci procesul il vom numi sortare externa.

Fiecare element al colectiei de date se numeste articol iar acesta la randul sau este compus din unul sau mai multe componente. O cheie C este asociata fiecarui articol si este de obicei una dintre componente. Spunem ca o colectie de n articole este ordonata crescator dupa cheia C daca C(i) C(j) pentru 1 i<j n, iar daca C(i) C(j) atunci sirul este ordonat descrescator.

1 Algoritmi de cautare

In acest subcapitol vom studia cateva tehnici elementare de cautare si vom presupune ca datele se afla in memoria interna, intr-un sir de articole. Vom cauta un articol dupa un camp al acestuia pe care il vom considera cheie de cautare. In urma procesului de cautare va rezulta pozitia elementului cautat (daca acesta exista).

Notand cu k₁, k₂, ., k_n cheile corespunzatoare articolelor si cu a cheia pe care o cautam, problema revine la a gasi (daca exista) pozitia p cu proprietatea a = k_p.

De obicei articolele sunt pastrate in ordinea crescatoare a cheilor, deci vom presupune ca

k₁ < k₂ < . < k_n .

Uneori este util sa aflam nu numai daca exista un articol cu cheia dorita ci si sa gasim in caz contrar locul in care ar trebui inserat un nou articol avand cheia specificata, astfel incat sa se pastreze ordinea existenta.

Deci problema cautarii are urmatoarea specificare:

Date a,n,(k_i, i=1,n);

Preconditia: nIN, n 1 si k₁ < k₂ < . < k_n ;

Rezultate p;

Postconditia: (p=1 si a k₁) sau (p=n+1 si a > k_n) sau (1<p n) si (k_p-1 < a k_p).

Pentru rezolvarea acestei probleme vom descrie mai multi subalgoritmi.

O prima metoda este cautarea secventiala, in care sunt examinate succesiv toate cheile. Sunt deosebite trei cazuri: a k₁, a>k_n, respectiv k₁ < a k_n, cautarea avand loc in al treilea caz.

Subalgoritmul CautSecv(a,n,K,p) este: 

Daca a k₁ atunci p:=1 altfel

Daca a>k_n atunci p:=n+1 altfel

Pentru i:=2; n executa

Daca (p=0) si (a k_i) atunci p:=i sfdaca

sfpentru

sfdaca

sfdaca

sf-CautSecv

Se observa ca prin aceasta metoda se vor executa in cel mai nefavorabil caz n-1 comparari, intrucat contorul i va lua toate valorile de la 2 la n. Cele n chei impart axa reala in n+1 intervale. Tot atatea comparari se vor efectua in n-1 din cele n+1 intervale in care se poate afla cheia cautata, deci complexitatea medie are acelasi ordin de marime ca si complexitatea in cel mai rau caz.

Evident ca in multe situatii acest algoritm face calcule inutile. Atunci cand a fost deja gasita cheia dorita este inutil a parcurge ciclul pentru celelalte valori ale lui i. Cu alte cuvinte este posibil sa inlocuim ciclul PENTRU cu un ciclu CATTIMP. Ajungem la un al doilea algoritm, dat in continuare.

Subalgoritmul CautSucc(a,n,K,p) este: 

{(p=n+1 si a>k_n) sau (1<p n) si (k_p-1 < a k_p).

Fie p:=1;

Daca a>k₁ atunci

Cattimp p n si a>k_p executa p:=p+1 sfcat

sfdaca

sf-CautSecv

In cel mai rau caz si acest algoritm face acelasi numar de operatii ca si subalgoritmul Cautsecv. In medie numarul operatiilor este jumatate din numarul mediu de operatii efecuat de subalgoritmul Cautsecv deci complexitatea este aceeasi.

O alta metoda, numita cautare binara, care este mult mai eficienta, utilizeaza tehnica 'divide et impera' privitor la date. Se determina in ce relatie se afla cheia articolului aflat in mijlocul colectiei cu cheia de cautare. In urma acestei verificari cautarea se continua doar intr-o jumatate a colectiei. In acest mod, prin injumatatiri succesive se micsoreaza volumul colectiei ramase pentru cautare. Cautarea binara se poate realiza practic prin apelul functiei BinarySearch(a,n,K,1,n), descrisa mai jos, folosita in subalgoritmul dat in continuare.

Subalgoritmul CautBin(a,n,K,p) este: 

Daca a k₁ atunci p:=1 altfel

Daca a>k_n atunci p:=n+1 altfel

p:=BinarySearch(a,n,K,1,n)

sfdaca

sfdaca

sf-CautBin

Functia BinarySearch (a,n,K,St,Dr) este:

Daca St Dr-1

atunci BinarySearch:=Dr

altfel m:=(St+Dr) Div 2;

Daca a K[m]

atunci BinarySearch:=BinarySearch(a,n,K,St,m)

altfel BinarySearch:=BinarySearch(a,n,K,m,Dr)

sfdaca

sfdaca

sf-BinarySearch

In functia BinarySearch descrisa mai sus, variabilele St si Dr reprezinta capetele intervalului de cautare, iar m reprezinta mijlocul acestui interval. Prin aceasta metoda, intr-o colectie avand n elemente, rezultatul cautarii se poate furniza dupa cel mult log₂n comparari. Deci complexitatea in cel mai rau caz este direct proportionala cu log₂n. Fara a insista asupra demonstratiei, mentionam ca ordinul de marime al complexitatii medii este acelasi.

Se observa ca functia BinarySearch se apeleaza recursiv. Se poate inlatura usor recursivitatea, asa cum se poate vedea in urmatoarea functie:

Functia BinSeaNerec (a,n,K,St,Dr) este:

Cattimp Dr-St>1 executa

m:=(St+Dr) Div 2;

Daca a K[m] atunci Dr:=m altfel St:=m sfdaca

sfcat

BinSeaNerec:=Dr

sf-BinSeaNerec

Complexitatea acestor algoritmi de cautare este data in tabelul care urmeaza.

2 Sortare interna

Prin sortare interna vom intelege o rearanjare a unei colectii aflate in memoria interna astfel incat cheile articolelor sa fie ordonate crescator (eventual descrescator).

Din punct de vedere al complexitatii algoritmilor problema revine la ordonarea cheilor. Deci specificarea problemei de sortare interna este urmatoarea:

Date n,K;

Preconditia: k_iIR, i=1,n

Rezultate K';

Postconditia: K' este o permutare a lui K, dar ordonata crescator. Deci k₁ k₂ k_n.

O prima tehnica numita 'Selectie' se bazeaza pe urmatoarea idee: se determina pozitia elementului cu cheie de valoare minima (respectiv maxima), dupa care acesta se va interschimba cu primul element. Acest procedeu se repeta pentru subcolectia ramasa, pana cand mai ramane doar elementul maxim.

Subalgoritmul Selectie(n,K) este: 

Pentru i:=1; n-1 executa

Fie ind:=i;

Pentru j:=i+1; n executa

Daca k_j < k_ind atunci ind:=j sfdaca

sfpentru

Daca i<ind atunci t:=k_i; k_i:=k_ind; k_ind:=t sfdaca

sfpentru

sf-Selectie

Se observa ca numarul de comparari este:

(n-1)+(n-2)++2+1=n(n-1)/2

indiferent de natura datelor. Deci complexitatea medie, dar si in cel mai rau caz este O(n²).

O alta posibilitate consta in parcurgerea cheilor cu ordonare partiala: intotdeauna portiunea parcursa ramane ordonata. Deci cheia la care am ajuns va fi inserata in secventa parcursa astfel ca aceasta sa-si pastreze proprietatea de ordonare. Obtinem un al doilea algoritm de sortare, numit Insertie.

Subalgoritmul Insertie(n,K) este:

Pentru i:=2; n executa

Fie ind:=i-1; a:=k_i;

Cattimp ind>0 si a<k_ind executa

k_ind+1 := k_ind ;

ind:=ind-1

sfcat

k_ind+1:=a

sfpentru

sf-Insertie

Algoritmul prezentat mai sus va executa in cel mai nefavorabil caz n(n-1)/2 comparari si mutari, iar in cazul cel mai favorabil, cand sirul este ordonat va executa 2(n-1) mutari si n-1 comparari, ceea ce inseamna ca acest algoritm are complexitatea O(n²).

A treia metoda care va fi prezentata, numita 'BubbleSort', compara doua cate doua elemente consecutive iar in cazul in care acestea nu se afla in relatia dorita, ele vor fi interschimbate. Procesul de comparare se va incheia in momentul in care toate perechile de elemente consecutive sunt in relatia de ordine dorita.

Subalgoritmul BubbleSort (n,K) este:

Repeta

Fie kod:=0;

Pentru i:=2; n executa

Daca k_i-1 > k_i atunci

t := k_i-1;

k_i-1 := k_i;

k_i:=t;

kod:=1

sfdaca

sfpentru

panacand kod=0 sfrep 

sf-BubbleSort

Acest algoritm executa in cel mai nefavorabil caz (n-1)+(n-2)+ +2+1 = n(n-1)/2 comparari, deci complexitatea lui este O(n²).

O metoda mai performanta de ordonare, care va fi prezentata in continuare, se numeste 'QuickSort' si se bazeaza pe tehnica 'divide et impera' dupa cum se poate observa in continuare. Metoda este prezentata sub forma unei proceduri care realizeaza ordonarea unui subsir precizat prin limita inferioara si limita superioara a indicilor acestuia. Apelul procedurii pentru ordonarea intregului sir este : QuickSort(n,K,1,n), unde n reprezinta numarul de articole ale colectiei date. Deci

Subalgoritmul SortareRapida (n,K) este:

Cheama QuickSort(n,K,1,n)

sf-SortareRapida

Procedura QuickSort (n,K,St,Dr) va realiza ordonarea subsirului k_St,k_St+1,, k_Dr. Acest subsir va fi rearanjat astfel incat k_St sa ocupe pozitia lui finala (cand sirul este ordonat). Daca i este aceasta pozitie, sirul va fi rearanjat astfel incat urmatoarea conditie sa fie indeplinita:

k_j k_i k_l , pentru st j < i < l dr (*)

Odata realizat acest lucru, in continuare va trebui doar sa ordonam subsirul k_St , k_St+1 , ,k_i-1 prin apelul recursiv al procedurii QuickSort(n,K,St,i-1) si apoi subsirul k_i+1,, k_Dr prin apelul QuickSort(n,K,i+1,Dr). Desigur ordonarea acestor doua subsiruri (prin apelul recursiv al procedurii) mai este necesara doar daca acestea contin cel putin doua elemente.

Procedura QuickSort este prezentata in continuare :

Subalgoritmul QuickSort (n,K,St,Dr) este:

Fie i:=St; j:=Dr; a:=k_i;

Repeta

Cattimp k_j >= a si (i<j) executa j:=j‑1 sfcat

k_i:= k_j;

Cattimp k_i a si (i<j) executa i:=i+1 sfcat

k_j:= k_i ;

panacand i=j sfrep

Fie k_i := a;

Daca St < i‑1 atunci Cheama QuickSort(n,K,St,i‑1) sfdaca

Daca i+1 < Dr atunci Cheama QuickSort(n,K,i+1,Dr) sfdaca

sf-QuickSort

Complexitatea algoritmului prezentat este O(n²) in cel mai nefavorabil caz, dar complexitatea medie este de ordinul O(nLog₂n).

Un alt algoritm performant pentru sortare interna este 'Tree Sort' (sortare arborescenta) care se bazeaza pe construirea unui arbore binar. Arborele binar construit are proprietatea ca in orice subarbore, subarborele stang al acestuia contine articole cu chei mai mici decat cheia continuta in radacina, iar subarborele drept contine chei mai mari decat radacina. Prin parcurgerea in inordine a arborelui astfel construit elementele vor fi in ordine crescatoare. Construirea unui astfel de arbore se va realiza prin adaugari succesive ale elementelor de sortat in subarborele stang sau drept dupa cum cheia articolului ce se adauga este mai mica sau mai mare decat cheia aflata in radacina subarborelui in care se efectueaza adaugarea. Acest algoritm va fi prezentat in capitolul referitor la arbori binari din volumul doi.

Complexitatea acestor algoritmi de sortare este data in tabelul care urmeaza.

Un ultim algoritm care va fi prezentat se numeste 'Merge Sort' (sortare prin interclasare) si se bazeaza pe tehnica 'divide et impera'. Sirul ce urmeaza a fi ordonat se imparte in doua subsiruri care se ordoneaza, dupa care acestea se vor interclasa obtinandu-se intregul sir ordonat. Fiecare subsir se va ordona tot prin despartirea lui in doua subsiruri urmata de interclasare si asa mai departe pana cand ordonarea unui subsir se poate rezolva elementar fara a mai fi necesara despartirea lui in alte doua subsiruri (lungimea subsirului este cel mult 2).

Algoritmul corespunzator este prezentat in sectiunea urmatoare sub forma unei proceduri recursive care ordoneaza un subsir precizand limitele acestuia.

3 Interclasare

Fiind date doua colectii de date, ordonate crescator (sau descrescator) dupa o cheie, se cere sa se obtina o colectie care sa fie de asemenea ordonata crescator (respectiv descrescator) dupa aceeasi cheie si care sa fie formata din articolele colectiilor date. Acest lucru se poate obtine direct (fara o sortare a colectiei finale) prin parcurgerea secventiala a celor doua colectii, simultan cu generarea colectiei cerute. Prin compararea a doua elemente din listele de intrare se va decide care element va fi adaugat in lista de iesire.

Deci ne intereseaza un algoritm de rezolvare a problemei ce are urmatoarea specificare:

Date m, (x_i, i=1,m), n, (y_i, i=1,n);

Preconditia: si

Rezultate k, (z_i, i=1,k);

Postconditia: si si (z₁,z₂,, z_k) este o permutare a

valorilor (x₁, , x_m,y₁,, y_n)

O solutie posibila ar fi depunerea componentelor vectorului X si a componentelor vectorului Y in vectorul Z, realizand astfel a doua parte din postconditie. Ordonand apoi componentele vectorului Z obtinem solutia dorita. Acest algoritm, desi corect, este ineficient si, in plus, nu este util in sortarile externe (vezi sectiunea 5.4). Este important ca la o singura trecere prin vectorii X si Y sa se obtina vectorul Z. Acest lucru este realizat de urmatorul algoritm de interclasare:

Subalgoritmul Interclasare(m,X,n,Y,k,Z) este: 

Fie i:=1; j:=1; k:=0;

Cattimp (i<=m) si (j<=n) executa

Daca x_i y_j

atunci Cheama PUNE(i,x_i,k,Z)

altfel Cheama PUNE(j,y_j,k,Z)

sfdaca

sfcat

Cattimp (i<=m) executa 

Cheama PUNE(i,x_i,k,Z)

sfcat

Cattimp (j<=n) executa 

Cheama PUNE(j,y_j,k,Z)

sfcat

sf-Interclasare

Aici s-a folosit subalgoritmul PUNE(ind,val,k,Z) care pune in vectorul Z valoarea val si mareste indicele ind cu 1, subalgortim dat in continuare.

Subalgoritmul PUNE(ind,val,k,Z) este:

k:=k+1;

z_k:=val;

ind:=ind+1

sf-PUNE

Algoritmul MergeSort de sortare bazat pe interclasare se poate vedea in continuare.

Algoritmul MergeSort este:

Citeste n;

Pentru i:=1 ; n executa Citeste K_i sfpentru

Cheama SortInter (n,K);

Pentru i:=1; n executa Tipareste K_i sfpentru

sf-MergeSort

Subalgoritmul SortInter(n, C) este:

Cheama Ordon (1,n,C);

sf-SortInter

Subalgoritmul Ordon (St,Dr,A) este: 

Daca St < Dr atunci

Fie m:=(St+Dr) Div 2;

Cheama Ordon (St,m,A);

Cheama Ordon (m+1,Dr,A);

Cheama Inter (St,m, m+1,Dr);

sfdaca

sf-Ordon

Subalgoritmul Inter (s1,d1, s2,d2) este: 

Fie A:=C; k:=s1‑1;

Cattimp (s1<=d1) si (s2<=d2) executa

Daca (C[s1]<C[s2])

atunci Cheama PUNE(s1,c_s1 ,k,A)

altfel Cheama PUNE(s2,c_s2 ,k,A)

sfdaca

sfcat

Cattimp (s1<=d1) executa Cheama PUNE(s1,c_s1 ,k,A) sfcat

Cattimp (s2<=d2) executa Cheama PUNE(s2,c_s2 ,k,A) sfcat

C:=A

sf-Inter

4 Sortare externa

O problema cu care ne confruntam adesea este sortarea unei colectii de date aflate pe un suport extern, de volum relativ mare fata de memoria interna disponibila. In aceasta sectiune o astfel de colectie de date o vom numi fisier. In acest caz nu este posibil transferul intregii colectii in memoria interna pentru a fi ordonata si apoi din nou transferul pe suport extern. Daca datele ce urmeaza a fi sortate ocupa un volum de n ori mai mare decat spatiul de memorie interna de care dispunem, atunci colectia se va imparti in n subcolectii ce vor fi transferate succesiv in memoria interna, se vor sorta pe rand si vor fi stocate din nou pe suportul extern sortate. Din acest moment prin operatii de interclasare doua cate doua se pot obtine colectii de dimensiuni superioare pana se obtine toata colectia ordonata.

La aceste interclasari, pentru a efectua un numar cat mai mic de operatii de transfer se recomanda interclasarea colectiilor de dimensiuni minime, apoi din datele obtinute din nou vor fi alese doua colectii de dimensiuni minime si asa mai departe pana se obtine o singura colectie care va fi colectia ceruta, adica sortata.

Dupa metodele de sortare externa folosite, in [Tambulea92] se descriu trei procedee de sortare externa:

- sortarea echilibrata;

- sortarea polifazica;

- sortarea in cascada.

In aceasta sectiune nu vom intra in detalii referitoare la diferitele metode de sortare posibile. Ne multumim cu prezentarea unei singure metode de sortare, fara a avea pretentia de a alege pe cea mai buna.

Evident ca sortarea depinde si de configuratia calculatorului folosit, dar si de suportul pe care se afla fisierul de sortat si fisierele intermediare create.

Principial sortarea externa presupune parcurgerea a doua etape importante:

a) Divizarea fisierului de sortat F, in n fisiere H₁, H₂, , H_n, cu sortarea interna a acestora;

b) Interclasarea acestor fisiere sortate pentru a ajunge la fisierul dorit G.

In incheierea acestui capitol vom prezenta doi algoritmi DivizareFisier, respectiv InterclasFisier, care realizeaza aceste activitati. Inainte insa vom da specificarea celor doua probleme corespunzatoare.

Specificarea programului DivizareFisier este:

Date F;

Preconditia: F este un fisier arbitrar (ce trebuie sortat).

Rezultate H₁, H₂, ,H_n;

Postconditia: F '=' H₁ H₂ H_n; (aceleasi inregistrari) si fiecare H_i este fisier sortat.

Specificarea programului Intercl2Fisier este:

Date H₁, H₂;

Preconditia: H₁, H₂ sunt doua fisiere sortate.

Rezultate G3;

Postconditia: G3 '=' H₁ H₂ (au aceleasi inregistrari) si G3 este fisier

sortat, obtinut din H₁ si H₂ prin interclasare

Se observa ca etapa a doua este rezolvata de programul Intercl2Fisier in cazul particular n=2.

Daca consideram algoritmul corespunzator ca o procedura, atunci cazul general (InterclasFisier) este rezolvat prin apelurile:

Cheama Intercl2Fisier(H₁ ,H₂ ,G₂);

Cheama Intercl2Fisier(H₃ ,G₂ ,G₃);

. . .

Cheama Intercl2Fisier(H_n ,G_n-1 ,G_n)

fisierul G_n = G fiind chiar fisierul dorit.

Dam mai intai algoritmul DivizareFisier.

Algoritmul DivizareFisier este:

Fie j:=0;

Cattimp mai exista articole necitite in F executa

j:=j+1;

i:=0;

Cattimp (i<m) si (Fisierul F mai are articole necitite) executa

alt:=urmatorul articol din F;

i:=i+1;

Art[i]:=alt; K_i:=Cheie(alt)

sfcat

nri:=m;

Daca i<m atunci nri:=i sfdaca

Cheama Ordon(m,K,O);

Pentru i:=1 ; nri executa

@Scrie articolul Art_o[i] in fisierul H_j

sfpentru

sfcat

sf-DivizareFisier

Subalgoritmul Ordon (m,K,O) este: 

Pentru i:=1;m executa O_i:=i sfpentru

Repeta kod:=0;

Pentru i:=1;m‑1 executa

Daca K[O_i] > K[O_i+1] atunci

kod:=O_i;

O_i:=O_i+1; O_i+1:=kod

sfdaca

sfpentru

panacand kod=0 sfrep

sf-Ordon

Dam in continuare o prima varianta a algoritmului Intercl2Fis. Mentionam insa ca el contine o greseala si sugeram cititorului sa o gaseasca inainte de a citi varianta a doua, care este corecta.

Subalgoritmul Intercl2Fis(H1,H2, G3) este:

r1:=Urmatorul articol din H1;

r2:=Urmatorul articol din H2;

Repeta

Daca Cheia(r1) > Cheie(r2)

atunci Cheama Depune(H2,G3,r2)

altfel Cheama Depune(H1,G3,r1)

sfdaca

panacand (H1 nu mai are articole) sau

(H2 nu mai are articole) sfrep

Cattimp (nu s-a epuizat fisierul H1) executa

Cheama Depune(H1,G3,r1)

sfcat

Cattimp (nu s-a epuizat fisierul H2) executa

Cheama Depune(H2,G3,r2)

sfcat

sf-Intercl2Fis

Subalgoritmul Depune(H,G, r) este:

@Pune articolul r in fisierul G.

r:=Urmatorul articol din H

sf-Depune

Intrucat greseala se afla in procedura Intercl2Fis dam in continuare doar textul corectat al acestei proceduri.

Subalgoritmul Intercl2Fis(H1,H2,G3) este:

Daca H1 e vid

atunci ind1:=0

altfel ind1:=1;

r1:=Primul articol din H1;

sfdaca

Daca H2 e vid atunci ind2:=0 altfel

r2:=Primul articol din H2;

ind2:=1;

sfdaca

Cattimp (ind1>0) si (ind2>0) executa

Daca Cheie(r1) > Cheie(r2)

atunci Cheama Pune(H2,G3,r2,ind2)

altfel Cheama Pune(H1,G3,r1,ind1)

sfdaca

Cattimp ind1>0 executa Cheama Pune(H1,G3,r1,ind1) sfcat

Cattimp ind2>0 executa Cheama Pune(H2,G3,r2,ind2) sfcat

sfcat

sf-Intercl2Fis

Subalgoritmul Pune(H,G,r,ind) 

este:

@Scrie pe r in G.

ind:=ind‑1;

Daca mai exista articole necitite in H atunci

@Citeste in r urmatorul articol din H.

ind:=ind+1

sfdaca

Sf-Pune

Sa observam ca ultima varianta foloseste doua variabile suplimentare, ind1 si ind2. Semnificatia lor este precizata prin comentarii si explica greseala facuta in prima varianta: aceea ca ultima inregistrare citita din fisierul de intrare ramanea nedepusa in fisierul rezultat G3. Deci ind1, respectiv ind2, reprezinta numarul inregistrarilor citite din fisierul H1, respectiv H2 si inca nedepuse in G3.