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 unul dintre componente. Spunem ca o colectie de n articole este ordonat 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.
5.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 k1, k2, ., kn cheile corespunzatoare articolelor si cu a cheia pe care o cautam, problema revine la a gasi (daca exista) pozitia p cu proprietatea a = kp.
De obicei articolele sunt pastrate in ordinea crescatoare a cheilor, deci vom presupune ca
k1 < k2 < . < kn .
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,(ki, i=1,n);
Preconditia: nIN, n 1 si k1 < k2 < . < kn ;
Rezultate p;
Postconditia: (p=1 si a k1) sau (p=n+1 si a > kn)
sau (1<p n) si (kp-1 < a kp).
Pentru rezolvarea acestei probleme vom descrie mai multi subalgoritmi.
O prima metoda este cautarea secventiala, in care sunt examinate succesiv toate cheile.
Subalgoritmul CautSecv(a,n,K,p) este:
Daca a k1 atunci p:=1 altfel
Daca a>kn atunci p:=n+1 altfel
Pentru i:=2; n executa
Daca (p=0) si (a ki) 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:
Daca a k1 atunci p:=1 altfel
Daca a>kn 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.
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
5.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: kiIR, i=1,n
Rezultate K';
Postconditia: K' este o permutare a lui K, dar ordonata crescator. Deci k1 k2 kn.
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 kj < kind atunci ind:=j sfdaca
sfpentru
Daca i<ind atunci t:=ki; ki:=kind; kind:=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.
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 ki-1 > ki atunci
t := ki-1;
ki-1 := ki;
ki:=t;
kod:=1
sfdaca
sfpentru
panacand kod=0 sfrep
sf-BubbleSort
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.
Subalgoritmul SortareRapida (n,K) este:
Cheama QuickSort(n,K,1,n)
sf-SortareRapida
Procedura QuickSort (n,K,St,Dr) va realiza ordonarea subsirului kSt,kSt+1,, kDr. Acest subsir va fi rearanjat astfel incat kSt 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:
kj ki kl , pentru st j < i < l dr (*)
Odata realizat acest lucru, in continuare va trebui doar sa ordonam subsirul kSt , kSt+1 , ,ki-1 prin apelul recursiv al procedurii QuickSort(n,K,St,i-1) si apoi subsirul ki+1,, kDr prin apelul QuickSort(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:=ki;
Repeta
Cattimp kj >= a si (i<j) executa j:=j‑1 sfcat
ki:= kj;
Cattimp ki a si (i<j) executa i:=i+1 sfcat
kj:= ki ;
panacand i=j sfrep
Fie ki := 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
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.
5.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, (xi, i=1,m), n, (yi, i=1,n);
Preconditia: si
Rezultate k, (zi, i=1,k);
Postconditia: si si (z1,z2,, zk) este o permutare a
valorilor (x1, , xm,y1,, yn)
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 xi yj
atunci Cheama PUNE(i,xi,k,Z)
altfel Cheama PUNE(j,yj,k,Z)
sfdaca
sfcat
Cattimp (i<=m) executa
Cheama PUNE(i,xi,k,Z)
sfcat
Cattimp (j<=n) executa
Cheama PUNE(j,yj,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;
zk:=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 Ki sfpentru
Cheama SortInter (n,K);
Pentru i:=1; n executa Tipareste Ki 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,cs1 ,k,A)
altfel Cheama PUNE(s2,cs2 ,k,A)
sfdaca
sfcat
Cattimp (s1<=d1) executa Cheama PUNE(s1,cs1 ,k,A) sfcat
Cattimp (s2<=d2) executa Cheama PUNE(s2,cs2 ,k,A) sfcat
C:=A
sf-Inter
5.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, se descriu trei procedee de sortare externa:
- sortarea echilibrata; sortarea polifazica; sortarea in cascada.
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 H1, H2, , Hn, cu sortarea interna a acestora;
b) Interclasarea acestor fisiere sortate pentru a ajunge la fisierul dorit G.
