Caracteristicile algoritmilor de sortare

Lucrare de licenta despre Caracteristicile algoritmilor de sortare
Aceasta metoda a fost pusa la punct de catre Donald L. Shell in 1959 si este o completare a algoritmului de insertie directa. El mai poarta numele si de sortare prin micsorarea incrementului. Incrementul reprezinta de fapt numarul de grupe in care va fi impartit tabloul R.
Este unul din algoritmii care deplaseaza articole numai cu cate o pozitie deodata, timpul sau mediu de rulare va fi in cel mai bun caz cu n2, deoarece fiecare inregistrare trebuie deplasata in medie aproximativ pozitii, in timpul procesului de sortare.

Pentru a imbunatati insertia directa, avem nevoie de un mecanism, prin intermediul caruia inregistrarile sa efectueze salturi lungi in loc de pasi mici. O asemenea metoda a fost propusa in anul 1959 de Donald L. Shell si se numeste sortare cu micsorarea incrementului.Consideram 16 inregistrari R1, R2, ..., R16. Aceste inregistrari le vom imparti in 8 grupe a cate doua, adica (R1, R9), (R2, R10), .... (R8, R16). Sortand fiecare grupa separat, ne va conduce la a doua linie a tabelului; aceasta numindu-se prima trecere. Acum vom imparti inregistrarile in cate 4 grupe de cate patru inregistrari fiecare, adica (R1, R5, R9, R16), ...., (R4, R8, R12, R16), si din nou fiecare grup este sortat separat.

Lucrare de licenta despre Caracteristicile algoritmilor de sortare

Lucrare de licenta despre Caracteristicile algoritmilor de sortare
Cuprins

Capitolul I. Notiuni introductive..................................3
I.1 Notiunea De Sortare..................................... 3
I.2 Aplicatii Ale Sortarii................... ........................3
I.3 Formularea Problemei....................................4
I.4 Caracteristicile Algoritmilor De Sortare.....................6

Capitolul II. Elemente teoretice necesare analizei algoritmilor................................................8
II.1 Calculul De Complexitate Si Notatii Asimptotice...................8

Capitolul III. Sortarea interna...............................15
III.1 Algoritmi De Sortare Prin Numarare............................15
III.2 Sortarea Prin Insertie ..............................20
III.3 Sortarea Prin Interschimbare................................33
III.4 Sortarea Prin Selectie.....................................43
III.5 Alti Algoritmi De Sortare......................................55

Capitolul IV. Sortarea externa................................61
IV.1 Sortarea Prin Interschimbare A Fisierelor.........................62