Referat - Sortare rapida

Categorie
Referate Informatica
Data adaugarii
acum 5 ani
Afisari
311
Etichete
sortare, rapida
Descarcari
281
Nota
0 / 10 - 0 voturi

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:
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 aseme


Copyright © Toate drepturile rezervare. 2008 - 2024 - Referatele.org