Cuprins

Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.

Extras din document

Alte date

?Capitolul 1

NOTIUNI INTRODUCTIVE

1.1. NOTIUNEA DE SORTARE

Înainte de a incepe prezentarea anumitor algoritmi de sortare se impune a specifica ce inseamna sortare sau, cu alte cuvinte, ce-si propun sa rezolve algoritmii de sortare. Se doreste ca pornind de la o secventa de inregistrari continand fiecare o cheie, secventa sa fie reordonata astfel incat cheile sa fie intr-o anumita relatie de ordine. Pentru chei numerice poate fi crescatoare sau descrescatoare, iar pentru chei alfanumerice poate fi ordinea alfabetica. Restul informatiei din inregistrare, mai putin cheia se numeste informatie satelit.

1.2. APLICATII ALE SORT?RII

Unele din cele mai importante aplicatii ale sortarii sunt:

1. Solutionarea problemei legate de punerea impreuna a tuturor articolelor care au aceeasi identitate, adica dandu-se n (suficient de mare) articole intr-o ordine aleatoare, din care multe au aceeasi valoare, ne propunem sa rearanjam acest fisier astfel incat toate articolele cu valori egale sa apara in pozitii consecutive; elementele pot fi asezate crescator sau descrescator.

2. Daca doua sau mai multe fisiere au fost sortate in aceeasi ordine, devine posibila gasirea intrarilor identice printr-o singura trecere prin ele, fara intoarcere. Este mult mai economic sa accesam o lista de informatii de la inceput la sfarsit, decat sa accesam lista sarind aleator in lista, cu exceptia cazului cand lista este suficient de mica, pentru a fi memorata intr-o memorie rapida cu acces aleator. Sortarea face posibila utilizarea adresarii secventiale in fisiere mari, ca un substitut fezabil adresarii directe.

3. Sortarea este un mijloc ajutator pentru cautare, permitand astfel ca iesirile de la calculator sa poata fi adaptate cerintelor umane.

4. O alta aplicatie, mai clara, a sortarii apare in cazul rutinelor de editare a fisierelor unde fiecare linie este identificata de un numar de cheie. În timp ce un utilizator tipareste adaugari si modificari nu este necesar sa se pastreze intreg fisierul in memorie. Liniile pot fi modificate, apoi sortate (oricum ele sunt ordonate) si dupa aceea comasate cu fisierul original. Aceasta permite o utilizare rezonabila a eficientei memoriei intr-o situatie ce presupune multiprogramarea.

Fabricantii de calculatoare estimeaza ca peste 25% din timpul de rulare al calculatoarelor este ocupat de sortare, in conditiile in care toti clientii sunt luati in considerare.Exista multe instalatii in care sortarea reclama peste jumatate din timpul de calcul. Din aceste statistici putem conchide ca:

? exista o multitudine de aplicatii ale sortarii;

? multe persoane utilizeaza sortarea fara sa fie nevoie;

? se utilizeaza pe scara larga algoritmi de sortare ineficienti.

1.3. FORMULAREA PROBLEMEI

Se dau n articole R1, R2 ..., Rn care urmeaza a fi sortate. Aceste articole Ie vom numi inregistrari, iar colectia de n inregistrari o vom numi fisier. Fiecare inregistrare Rj are o cheie Kj care guverneaza procesul de sortare. Înregistrarile pot contine si alta informatie in afara cheii, numita informatie satelit, care nu va avea nici un efect asupra procesului de sortare.

0 relatie de ordine "<" este specificata asupra cheilor astfel ca pentru orice valoare a celor trei chei a, b, c, urmatoarele conditii sa fie satisfacute:

i) numai una din posibilitatile aii) daca aAceste doua posibilitati caracterizeaza conceptul matematic de ordonare liniara, denumita si ordonare totala. Orice relatie "<" ce satisface i) si ii) poate fi sortata prin majoritatea metodelor descrise in acest capitol, cu toate ca unele tehnici de sortare vor necesita chei numerice sau alfanumerice cu ordonarea obisnuita.

Scopul ordonarii este de a determina o permutare a inregistrarilor, care va pune cheile intr-o ordine nedescrescatoare:

Kp(1) ? Kp(2) ?....? Kp(n). (1)

De exemplu, primind secventa de intrare (219, 129, 243, 98, 491, 151, 452, 162, 376, 193, 134, 231, 332, 429, 449, 440) un algoritm de sortare intoarce ca rezultat secventa ordonata, (98, 129, 134, 151, 162, 193, 219, 231, 243, 332, 376, 429, 440, 449, 452, 491), conform relatiei de ordine "<".

În cazul algoritmilor de sortare, exista o dependenta profunda intre reprezentarea datelor care trebuie prelucrate si alegerea algoritmului de prelucrare. Acest lucru conduce la clasificarea algoritmilor de sortare in algoritmi interni (secventa de sortat este pastrata in memoria interna) si algoritmi externi (secventa de sortat este pastrata pe un suport extern).

Distinctia dintre cele doua reprezentari este sugestiv ilustrata de ordonarea cartilor de joc. Daca secventa care trebuie sortata este in memoria interna, suntem in situatia in care toate cartile de joc se afla pe masa, fiecare fiind vizibila si putand fi luata. În cazul pastrarii datelor de intrare pe suportul extern cu acces secvential, suntem in situatia in care cartile sunt puse intr-un teanc, din care numai cartea din varf este vizibila.

În general, pentru a caracteriza dimensiunea problemei se foloseste numarul de inregistrari din secventa, n. Acesta nu este intotdeauna suficient pentru a evalua timpul de executie al unui algoritm, el depinzand si de modul de aranjare initiala a elementelor in secventa (de exemplu, secventa aproape sortata sau cu multe chei egale). Dorim sa obtinem dependenta de lungime a secventei de sortat, a doi parametri: timpul de executie si memoria suplimentara utilizata. Algoritmii de sortare care nu folosesc memorie suplimentara se numesc in situ.

1.4. CARACTERISTICILE ALGORITMILOR DE SORTARE

1.4.1.STABILITATEA

0 caracteristica importanta a unui algoritm de sortare este stabilitatea. 0 metoda de sortare va fi stabilita daca pastreaza ordinea relativa a inregistrarilor cu chei egale, adica

p(i) < p(j) pentru Kp(i) = Kp(j) si i < j. (2)

Este util ca o metoda de sortare sa fie stabila in cazul unei duble sau multi sortari. De exemplu, daca avem o secventa de inregistrari continand un camp nume si un camp nota, secventa fiind sortata dupa nume, si daca sortam secventa si dupa nota, atunci in secventa finala pentru o sortare stabila inregistrarile cu aceeasi valoare a campului nota vor fi inca in ordine alfabetica.

În unele cazuri vom dori ca inregistrarile sa fie rearanjate fizic in memorie astfel incat cheile sa fie in ordine, in timp ce, in alte cazuri, va fi suficient sa avem un tabel auxiliar in care sa se specifice intr-un mod oarecare permutarile, astfel ca accesul la inregistrari sa se faca in ordinea cheilor. Unele metode de sortare presupun existenta uneia sau a ambelor valori "+?" sau "??", care se definesc ca fiind mai mari sau mai mici decat toate cheile, adica

? ? < Kj < +?, pentru 1 ? j ? n . (3)