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

Cuprins
I. SORTARE PRIN NUMARARE
I.1 COMPARARE PRIN NUMARARE
I.2 NUMARAREA DISTRIBUTIILOR
II. SORTAREA PRIN INSERTIE
II.1 SORTARE PRIN INSERTIE DIRECTA
II.2 SORTARE PRIN INSERTIE BINARA SI INSERTIA IN DUBLU SENS
II.3 SORTARE CU MICSORAREA INCREMENTULUI. METODA LUI SHELL
II.4 INSERTIA DE LISTA
II.5 SORTARE PRIN CALCULARE DE ADRESE
III. SORTAREA PRIN INTERSCHIMBARE
III.1 SORTARE PRIN METODA BULELOR SORTARE PRIN METODA BULELOR OPTIMIZATA
III.2 SORTARE PRIN INTERSCHIMBARE SI INTERCLASARE METODA PARALELA A LUI BATCHER
III.3 SORTARE RAPIDA
III.4 SORTAREA DUPA RANGURI CU INTERSCHIMBARE
IV. SORTARE PRIN SELECTIE
IV.1 SORTARE PRIN SELECTIE DIRECTA
IV.2 SORTARE DE ANSAMBLE
V. SORTARE PRIN INTERCLASARE
V.1 SORTARE PRIN INTERCLASARE CU DOUA CAI
V.2 SORTARE PRIN INTERCLASARE NATURALA CU DOUA CAI
V.3 SORTARE PRIN INTERCLASARE DIRECTA CU DOUA CAI
V.4 SORTARE PRIN INTERCLASARE DE LISTE
VI. SORTARE PRIN DISTRIBUTIE
VI.1 SORTARE DUPA RANGURI A LISTELOR
VI.2 ASAMBLAREA SIRURILOR

Alte date

?INTRODUCERE

Cu toate ca dictionarele definesc "sortarea" ca un proces de separare si aranjare a lucrarilor dupa clase si fel , este traditional pentru programatorii de calculatoare sa utilizeze cuvantul intr-un sens mult mai special , de sortare a lucrurilor intr-o ordine ascendenta sau descendenta . Procesul , probabil , ar trebui numit " ordonare" si nu sortare; dar oricine incearca sa-i spuna ordonare va ajunge foarte curand in situatii foarte confuze , din cauza intelesurilor diferite atasate acestui cuvant .

Unii au sugerat ca termen "secventare" sa fie numele dat procesului de ordonare dar acest cuvant nu reda uneori sensul corect ,in mod special in cazul prezentei unor elemente egale . Este adevarat ca "sortare" este un cuvant foarte solicitat , dar este unanim acceptat in limbajul legat de calculatoare .

Cele mai importante aplicatii ale sortarii sunt :

a) solutionarea problemei legate de punerea impreuna a tuturor articolelor care au aceeasi identitate .

b) daca doua sau mai multe fisiere au fost sortate in aceeasi ordine , devine posibila gasirea intrarilor identice printr-o singura trecere prin ele , fara intoarceri inapoi . Sortarea face posibila utilizarea adresarii secventiale in fisiere mari , ca un substitut fezabil adresarii directe .

c) Sortarea este de asemenea un mijloc ajutator pentru cautare , permitand astfel ca iesirile de la calculator sa devina mai adecvate necesitatilor umane .

Cu toate ca sortarea a fost utilizata traditional in prelucrari de date cu caracter economic, ea este un mijloc de baza pe care programatorul trebuie sa o considere , pentru cele mai variate situatii .

Tehnicile de sortare asigura o ilustrare excelenta a ideilor generale legate de analiza algoritmilor , adica a ideilor utilizate pentru a determina performantele algoritmilor astfel incat sa se poata face un discernamant inteligent intre diferitele metode .

In lucrarea de fata este folosita o anumita terminologie pe ca o prezint in randurile ce urmeaza .

Se dau N articole R1 , … , RN care urmeaza a fi sortate ; ele vor fi numite inregistrari.

Intreaga colectie de N inregistrari va fi denumita fisier . Fiecare inregistrare R j , are o cheie Kj care guverneaza procesul de sortare . Poate exista si alta informatie in inregistrare in afara cheii ; aceasta informatie "satelit" nu va avea nici un efect asupra procesului de sortare , in afara faptului ca ea va ramane cu inregistrarea respectiva .

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

1) Numai una din posibilitatile a< b , a=b , b2) Daca a< b si b< c atunci a Aceste doua proprietati caracterizeaza conceptul matematic de ordonare liniara , denumita si ordonare totala . Orice relatie "< " ce satisface si (1) si (2) poate fi sortata prin majoritatea metodelor descrise in aceasta lucrare , cu toate ca unele tehnici de sortare vor necesita chei numerice sau alfabetice cu ordonarea obisnuita .

Lucrarea de fata este structurata in sasa capitole , care prezinta principalele tehnici de sortare interna folosite in programarea calculatoarelor . Prezentarea este insotita de numeroase exemple la fiecare capitol abordat , precum si de programe realizate pentru o mai buna fixare a tehnicilor de sortare respective .

Au fost inventate o multime de algoritmi de sortare. O idee buna consta in a studia caracteristicile fiecarei metode de sortare , astfel ca sa se poata efectua o alegere inteligenta in cazul aplicatiilor particulare. Pentru acest lucru trebuie sa se cunoasca terminologia de baza si notatiile ce vor fi utilizate in studiul sortarii .

Inregistrarile R1 , R2 , …, RN

Trebuie sortate in ordine crescatoare a cheilor K1 , K2 , …, KN , in principal prin descoperirea unei permutari p(1) p(2) …p(N) astfel incat

Kp(1) ? Kp(2) ? …? Kp(N) .

Sortarea interna se refera la cazul in care numarul de inregistrari este suficient de mic pentru ca intreg procesul sa aiba loc in memoria interna a calculatorului .

Daca inregistrarile si /sau cheile necesita fiecare un numar destul de mic de cuvinte ale memoriei calculatorului atunci se recomanda construirea unui tabel cu adrese de legatura , ce indica inregistrarile , pentru a se putea manipula aceste adrese de legatura , in loc de inregistrarile voluminoase .

Aceasta metoda de sortare este denumita sortarea prin tabel de adrese .

Sortarea prin tabela de adrese

Inregistrari

R1

R2

R3

Cheie

Informatie satelita