Algoritmi de Căutare și Sortare

Introducere

Căutarea şi Sortarea sunt două dintre cele mai des întâlnite subprobleme în programare. Ele constituie o parte esenţială din numeroasele procese de prelucrare a datelor. Operaţiile de căutare şi sortare sunt executate frecvent de către oameni în viaţa de zi cu zi, ca de exemplu căutarea unui cuvânt în dicţionar sau căutarea unui număr în cartea de telefon.

Căutarea este mult simplificată dacă datele în care efectuăm această operaţie sunt sortate (ordonate, aranjate) într-o anumită ordine (cuvintele în ordine alfabetică, numerele în ordine crescătoare sau descrescătoare).

Sortarea datelor consta în rearanjarea colecţiei de date astfel încat un câmp al elementelor colecţiei să respecte o anumită ordine. De exemplu în cartea de telefon fiecare element (abonat) are un câmp de nume, unul de adresă şi unul pentru numărul de telefon. Colecţia aceasta respectă ordinea alfabetică după câmpul de nume.

Dacă datele pe care dorim să le ordonăm, adică să le sortăm, sunt în memoria internă, atunci procesul de rearanjare a colecţiei îl vom numi sortare internă.

Fiecare element al colecţiei de date se numeşte articol iar acesta la randul sau este compus din unul sau mai multe componente. O cheie este asociată fiecărui articol şi este de obicei unul dintre componente. Spunem că o colecţie de articole este ordonată crescator după cheia dacă pentru , iar dacă atunci şirul este ordonat descrescător.

Căutare, Sortare şi Selecţie

1. Căutare

1.1. Căutare binară

Se dau un vector şi o valoare . Se cere să se determine dacă se află printre elementele vectorului .

Dacă este un vector oarecare, atunci trebuie parcurse secvenţial elementele vectorului. Această modalitate necesită cel mult comparaţii în cazul unei căutări cu succes şi exact comparaţii în cazul căutării fără succes. Numărul mediu de comparaţii în cazul unei căutări cu succes este:

Dacă are elementele în ordine crescătoare - situaţie des întâlnită în practică – atunci există posibilitatea de a efectua o căutare mai performantă. Deci în continuare vom lucra în ipoteza .

Vom folosi metoda „Divide et impera” , începând prin a compara cu elementul „din mijloc”, adică cu unde . Dacă , atunci căutarea se încheie cu succes. În caz contrar, vom căuta în secvenţa dacă sau în secvenţa dacă . Vom presupune că dorim ca soluţia să fie exprimată sub forma:

unde . Atunci metoda descrisă este corectată în procedura , în care şi sunt primul, respectiv ultimul indice din secvenţa curentă în care se află .

Singura explicaţie necesară este legată de cazul în care căutarea se termină fără succes. Observăm că situaţia este precedată de situaţia în care valorile lui şi sunt şi cu . Dacă avem deci ; dacă atunci deci . Rezultă că valoarea tipărită este corectă.

Analiza timpui de lucru

În acest scop vom încerca să determinăm numărul de comparaţii care au loc între şi . Acest număr este cel care va dicta eficacitatea algoritmului deoarece, pe de o parte, elementele pot fi matrici, polinoame etc., iar pe de altă parte numărul de atribuiri şi numărul de comparaţii impuse de execuţia ciclului while diferă cu o unitate de numărul căutat. Un prim rezulatat este următorul:

1) Pentru , în cazul unei căutări cu succes se fac cel mult comparaţii, iar în cazul unei căutări fără succes se fac sau comparaţii.

Înainte de a face demonstraţia, vom ataşa algoritmului un arbore binar astfel:

- pentru arborele se reduce la (1), pentru arborele este vid

- pentru o valoare oarecare arborele are forma din Fig.1, unde ,

este arborele corespunzător lui , iar este arborele corespunzător lui , în care numerele vârfurilor sunt mărite cu .