Acasa | Trimite referat | Cere referat | Contact

Referat Sortare rapida

Sortare rapida

Categorie: Referate Informatica

Referat downloadat de: 236 ori.

Cauta referat dupa: sortare rapida

Descriere referat:

Sortare rapida (QuickSort) Secventa de comparatie din metoda lui Batcher este predeterminata; de fiecare data se compara aceleasi perechi de chei, indiferent de rezultatele comparatiilor anterioare. Sortarea rapida, in schimb, foloseste rezultatele fiecarei comparatii pentru a stabilii care sunt cheile care urmeaza a fi comparate. Deci, se foloseste urmatoare schema: se utilizeaza doi indicatori i si j, cu i=1 si j=N. Se compara Ki cu Kj si daca nu este necesar interschimbul, se micsoreaza j cu 1, repetandu-se procesul. Daca apare un interschimb, se mareste i cu 1si se continua compararea marind i pana la aparitia unui interschimb. Apoi, se micsoreaza din nou j, continuandu-se in acelasi mod, pana cand i=j. Exemplu: |Numerele: | |Interschimb 1: | |Interschimb 2: | |Interschimb 3: | |Interschimb 4: | |Interschimb 5: | |Interschimb 6: | Fiecare comparatie din exemplu, a implicat cheia 503; in general, fiecare comparatie va implica valoarea originala a cheii K1, deoarece ea va fi modificata odata cu fiecare schimbare de directie.In momentul cand i=j, inregistrarea originala R1, va fi plasata in pozitia finala, deoarece se poate vedea ca nu vor exista chei mai mari la stanga sa si nici mai mici la dreapta sa. Inregistrarile vor fi impartite intr-o asemenea maniera, incat problema initiala este redusa la doua probleme mai simple: sortarea Ri - Ri- 1 si sortarea Ri+1 - RN. Se poate aplica aceasi tehnica fiecarei dintre aceste doua multimi de inregistrari. Pentru a tine minte multimile de elemente care sunt impartite, se foloseste o stiva. Alt exemplu, care arata modul in care sunt sortate inregistrarile prin acesta metoda, este dat in tabelul de mai jos. Parantezele, indica inregistrarile care mai trebui sortate; inregistrarile impartite in grupe sunt reprezentate prin doua variabile l si r, care reprezinta limitele inregistrarilor care sunt curent examinate. | |Stiva (l,r) | [503 |087 |512 |061 |908 |170 |897 |275 |653 |426 |154 |509 |612 |677 |765 |703] |(1,16) - | |[154 |087 |426 |061 |275 |170] |503 |[897 |653 |908 |512 |509 |612 |677 |765 |703] |(1,6) (8,16) | |[061 |087] |154 |[426 |275 |170] |503 |[897 |653 |908 |512 |509 |612 |677 |765 |703] |(1,2) (4,6) (8,16) | |061 |087 |154 |426 |275 |170 |503 |[897 |653 |908 |512 |509 |612 |677 |765 |703] |(4,6) (8,16) | |061 |087 |154 |170 |275 |426 |503 |[897 |653 |908 |512 |509 |612 |677 |765 |703] |(4,5) (8,16) | |061 |087 |154 |170 |275 |426 |503 |[897 |653 |908 |512 |509 |612 |677 |765 |703] |(8,

Alte referate din materia: Informatica

Nr.	Nume referat	Hits
1	mtSZPKbW	20
2	TkkvMlabSupl	50
3	qzpymq@dxuzju.com	148
4	email@gmail.com	269
5	pfuqxd@exjswl.com	288
6	ncqcez@hdtnnq.com	244
7	Hard	722
8	ISTORIA INTERNET-ULUI	782
9	Impera	469
10	Info Doc	524
11	Info-TIRON	467
12	Informatica - Grafica pentru web	938
13	Informatica - Introducere in HTML	711
14	Initiere in pc	701
15	Instalarea sistemului de operare Windows	593
16	Internetul ca sursa de comunicare	580
17	Istoria Internetului	617
18	Istoria calculatorului	539
19	Istoria metodelor de proiectare	359
20	Java visavis de C++	401
21	Java vizavi de C	333
22	LIMBAJUL DE PROGRAMARE PASCAL - Programul defineste tipul salariat, o inregistrare cu variante, valorile citite fiind salvate in fisierul salariat.dat	0
23	Limbajul C	413
24	Lista vinuri prg	322
25	Lotus software	293

Acasa Trimite referat Cere referat Adauga la favorite Seteaza ca homepage Contact libertateailuziei Trailere Filme Filme Noi Jocuri Online Jocuri Barbie Jocuri pentru Copii GameBox.ro Make Money Bucuresti regim hotelier