...umita 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 Ci Cj pentru 1ijn, iar daca Ci Cj atunci sirul este ordonat descrescator.5.1 Algoritmi de cautareIn 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 cak1 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 specificareDate a,n,ki, i1,n Preconditia nN, n1 si k1 k2 .... kn Rezultate p Postconditia p1 si a k1 sau pn1 si a kn sau 1pn 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 CautSecva,n,K,p esteInN, n1 siSIk1 k2 .... knSISe cauta p astfel caSIp1 si a k1 sau pn1 si aknSIsau 1pn si kp-1 a kp. Fie p0ICazul inca negasitS Daca ak1 atunci p1 altfel Daca akn atunci pn1 altfel Pentru i2 n executa Daca p0 si aki atunci pi sfdaca sfpentru sfdaca sfdacasf-CautSecvSe 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 n1 intervale. Tot atatea comparari se vor efectua in n-1 din cele n1 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 CTTIMP. Ajungem la un al doilea algoritm, dat in continuare.Subalgoritmul CautSucca,n,K,p esteInN, n1 siSIk1 k2 .... knSISe cauta p astfel caSIp1 si a k1 sau pn1 si aknSIsau 1pn si kp-1 a kp. Fie p1 Daca ak1 atunci Cattimp pn si akp executs pp1 sfcat sfdacasf-CautSecvO 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. Cau...
Download