CLASE DE ALGORITMI de cautare sortare interna si externa, interclasare

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 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.

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:            

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.

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: 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.

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

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 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(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

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, (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

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 H₁, H₂, , H_n, cu sortarea interna a acestora;

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