Sortare rapida QuickSort metoda referat





Sortare rapida (QuickSort) <andys>

 

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. 42425ozl39nme6r



Exemplu:

Numerele:
503
087
512
061
908
170
897
275
653
426
154
509
612
677
765
703
Descreste j
Interschimb 1:
154
087
512
061
908
170
897
275
653
426
503
509
612
677
765
703
Mareste i
Interschimb 2:
154
087
503
061
908
170
897
275
653
426
512
509
612
677
765
703
Descreste j
Interschimb 3:
154
087
426
061
908
170
897
275
653
503
512
509
612
677
765
703
Mareste i
Interschimb 4:
154
087
426
061
503
170
897
275
653
908
512
509
612
677
765
703
Descreste j
Interschimb 5:
154
087
426
061
275
170
897
503
653
908
512
509
612
677
765
703
Mareste i
Interschimb 6:
154
087
426
061
275
170
503
897
653
908
512
509
612
677
765
703
Descreste j

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