Inainte 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.
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. 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.
Sortarea este un mijloc ajutator pentru cautare, permitand astfel ca iesirile de la calculator sa poata fi adaptate cerintelor umane.
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. In 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.
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.
Inregistrarile 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 a ...
Pentru a descărca acest document,
trebuie să te autentifici in contul tău.
