Sortare rapida(quicksort)

Un tablou V se completeaza cu n elemente numere reale .Sa se ordoneze crescator folosind metoda de sortare rapida .

Solutia problemei se bazeaza pe urmatoarele etape implementate in programul principal:

4se apeleaza procedura “quick” cu limita inferioara li=1 si limita superioara ls=n;

4functia”poz” realizeaza mutarea elementului v[i] exact pe pozitia ce o va ocupa acesta in vectorul final ordonat ; functia”poz” intoarce (in k ) pozitia ocupata de acest element;

4in acest fel ,vectorul V se imparte in doua parti : li …k-1 si k+1…ls;

4pentru fiecare din aceste parti se reapeleaza procedura“quick”,cu limitele modificate corespunzator ;

4in acest fel ,primul element din fiecare parte va fi pozitionat exact pe pozitia finala ce o va ocupa in vectorul final ordonat (functia“poz”);

4fiecare din cele doua parti va fi ,astfel ,inpartita in alte doua parti ;procesul continua pana cand limitele partilor ajung sa se suprapuna ,ceea ce indica ca toate elementele vectorului au fost mutate exact pe pozitiile ce le vor ocupa in vectorul final ;deci vectorul este ordonat ;

4in acest moment se produc intoarcerile din apelurile recursive si programul isi termina executia .

program quicksort;

type vector= array [1..50] of real ;

var v:vector;

i,n,k:integer;

function poz(li,ls:integer):integer;

var i,j,modi,modj,m:integer;

man:real;

begin

i:=li; j:=ls;

modi:=0; modj:=-1;

while i<j do

begin

if v[i]>v[j] then

begin

man:=v[i];

v[i]:=v[j];

v[j]:=man;

m:=modi ;

modi:=-modj;

modj:=-m;

end;

i:=i+modi;

j:=j+modj;

end;

poz:=i;

end;

procedure quick(li,ls:integer);

begin

if li<ls then begin

k::=poz(li,ls); 53528cnz87yej8u

quick(li,k-1);

quick(k+1,ls);

end;

end;

begin

write(‘cate elemente are vectorul ?=’);readln(n);

for i:=1 to n do

begin

write(‘tastati elementul ‘,i,’=’);

readln(v[i]);

end;

quick(1,n);

writeln(‘vectorul ordonat este :’);

for i:=1 to n do writeln(v[i]);

readln;

end.

OBSERVATIE

4daca elementul se afla in stanga ,atunci se compara cu elementele din dreapta lui si se sar (j:=j-1)elementele mai mari decat el ;

4daca elementul se afla in dreapta ,atunci se compara cu elemente din stanga lui si se sar (i:=i+1)elementele mai mici decat el.