Algoritmi de Cautare si Sortare

Cuprins licenta Cum descarc?

Cautare, Sortare si Selectie 4
1. Cautare 4
1.1. Cautare binara 4
1.2. Arbori binari de cautare 9
2. Sortare 13
2.1. Strategii generale de sortare 13
2.2. Sortarea prin insertie binara 19
2.3. Sortarea rapida (Quicksort) 20
2.4. Sortare cu numar minim de comparatii 24
2.5. Sortarea prin distribuire 31
2.6. Sortarea topologica 35
3. Interclasare 38
4. Selectie 41
Bibliografie 47


Extras din licenta Cum descarc?

Introducere
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.
Fiecare element al colectiei de date se numeste articol iar acesta la randul sau este compus din unul sau mai multe componente. O cheie este asociata fiecarui articol si este de obicei unul dintre componente. Spunem ca o colectie de articole este ordonata crescator dupa cheia daca pentru , iar daca atunci sirul este ordonat descrescator.
Cautare, Sortare si Selectie
1. Cautare
1.1. Cautare binara
Se dau un vector si o valoare . Se cere sa se determine daca se afla printre elementele vectorului .
Daca este un vector oarecare, atunci trebuie parcurse secvential elementele vectorului. Aceasta modalitate necesita cel mult comparatii in cazul unei cautari cu succes si exact comparatii in cazul cautarii fara succes. Numarul mediu de comparatii in cazul unei cautari cu succes este: 
Daca are elementele in ordine crescatoare - situatie des intalnita in practica - atunci exista posibilitatea de a efectua o cautare mai performanta. Deci in continuare vom lucra in ipoteza .
Vom folosi metoda ,,Divide et impera" , incepand prin a compara cu elementul ,,din mijloc", adica cu unde . Daca , atunci cautarea se incheie cu succes. In caz contrar, vom cauta in secventa daca sau in secventa daca . Vom presupune ca dorim ca solutia sa fie exprimata sub forma:
unde . Atunci metoda descrisa este corectata in procedura , in care si sunt primul, respectiv ultimul indice din secventa curenta in care se afla .
Singura explicatie necesara este legata de cazul in care cautarea se termina fara succes. Observam ca situatia este precedata de situatia in care valorile lui si sunt si cu . Daca avem deci ; daca atunci deci . Rezulta ca valoarea tiparita este corecta.
Analiza timpui de lucru
In acest scop vom incerca sa determinam numarul de comparatii care au loc intre si . Acest numar este cel care va dicta eficacitatea algoritmului deoarece, pe de o parte, elementele pot fi matrici, polinoame etc., iar pe de alta parte numarul de atribuiri si numarul de comparatii impuse de executia ciclului while difera cu o unitate de numarul cautat. Un prim rezulatat este urmatorul:
1) Pentru , in cazul unei cautari cu succes se fac cel mult comparatii, iar in cazul unei cautari fara succes se fac sau comparatii.
Inainte de a face demonstratia, vom atasa 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 corespunzator lui , iar este arborele corespunzator lui , in care numerele varfurilor sunt marite cu .


Fisiere in arhiva (1):

  • Algoritmi de Cautare si Sortare.doc

Imagini din aceasta licenta Cum descarc?

Banii inapoi garantat!

Plateste in siguranta cu cardul bancar si beneficiezi de garantia 200% din partea Diploma.ro.


Descarca aceasta licenta cu doar 8 €

Simplu si rapid in doar 2 pasi: completezi adresa de email si platesti.

1. Numele, Prenumele si adresa de email:

Pe adresa de email specificata vei primi link-ul de descarcare, nr. comenzii si factura (la plata cu cardul). Daca nu gasesti email-ul, verifica si directoarele spam, junk sau toate mesajele.

2. Alege modalitatea de plata preferata:



* La pretul afisat se adauga 19% TVA.


Hopa sus!