Algoritmii de sortare prin numarare

Lucrare de licenta despre Algoritmii de sortare prin numarare
Sortarea prin calcul de adrese necesita spatiu aditional de memorie proportional cu N, pentru care sa nu fie necesare deplasari excesive , sau pentru a forma tabele auxiliare care vor ajuta in tinerea evidentei neregularitatilor din distributia cheilor . Putem sa utilizam cel mai bine aceste spatii de memorie , daca le alocam campurilor de legatura , ca in metoda insertiilor de liste. Aceasta cale permite evitarea necesitatii de zone diferite pentru intrare si iesire . Totul poate fi facut in aceiasi zona de memorie.

Ideea de baza consta in generalizarea insertiei de liste astfel incat sa existe mai multe liste in loc de una. Fiecare lista este utilizata pentru un anumit domeniu de chei. Se considera ipoteza in care distributia cheilor este egala fata de cazul "aglomerarilor" nere- gulate . Multimea valorilor posibile ale cheilor va fi partitionata in M parti. Vom consi-dera ca 1/M este probabilitatea ca o cheie data sa apartina uneia din partitii . Apoi , vom asigura memorie pentru M capete de lista si vom mentine fiecare lista ca la insertia simpla de liste.
Pentru a ilustra metoda , fie cele 16 chei utilizate in exemplu , impartite in M = 4 domenii 0-249 , 250-499 , 500-749 , 750-799 . Vom obtine urmatoarea configuratie pe masura ce sortarea avanseaza.

Lucrare de licenta despre Algoritmii de sortare prin numarare

Cuprins

Introducere...............................................4

Capitolul I. Sortare prin numarare..................................8
I.1 Comparare prin numarare.......................................8
I.2 Numararea distributiilor........................................12

Capitolul II. Sortarea prin insertie.................................14
II.1 Sortare prin insertie directa.................................14
II.2 Sortare prin insertie binara si insertia in dublu sens.........................................18
II.3 Sortare cu micsorarea incrementului. Metoda lui Shell...........................................26
II.4 Insertia de lista................................28
II.5 Sortare prin calculare de adrese............................30

Capitolul III. Sortarea prin interschimbare..........................32
III.1 Sortare prin metoda buleleor optimizata.........................32
III.2 Sortare prin interschimbare si interclasare metida paralela a lui Batcher..............................................39
III.3 Sortare rapida........................................42
III.4 Sortarea dupa ranguri cu interschimbare.......................48

Capitolul IV. Sortare prin selectie................................51
IV.1 Sortare prin selectie directa.................................52
IV.2 Sortare de ansamble..........................................57

Capitolul V. Sortare prin interclasare.............................59
V.1 Sortare prin interclasare cu doua cai............................59
V.2 Sortare prin interclasare naturala cu doua cai......................64
V.3 Sortare prin interclasare directa cu doua cai......................67
V.4 Sortare prin interclasare de liste..............................69

Capitolul VI. Sortare prin distributie..............................71
VI.1 Sortare dupa ranguri a listelor...........................71
VI.2 Asamblarea sirurilor.....................................73