Sortare prin insertie binara rezolvarea problemei



Sortare prin insertie binara


Sa se ordoneze crescator un tablou unidimensional V de n numere reale ,folosind sortarea prin insertie binara .

Pentru fiecare element v[i] se procedeaza in patru pasi:



se considera ordonate elementele v[1],v[2],..,v[i-1];

se cauta pozitia k pe care urmeaza s-o ocupe v[i] intre elementele v[1],v[2],.,v[i-1](procedura "poz" prin cautare binara);

se deplaseaza spre dreapta elementele din pozitiile k,k+1,.,n(procedura "deplasare");

insereaza elementul v[i] in pozitia k (procedura"deplasare");

se obtine o succesiune de k+1 elemente ordonate crescator.


program sortare _binara;

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

var n,k,i:integer;

v:vector;

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

var m:integer;

begin

if li=ls then

if v[i]<v[j] then poz:=li

else poz:=i

else if ls-li=1 then if v[i]<v[ls] then if v[i]>=v[li]

then poz:=ls

else poz:=li

else poz:=i

else begin

m:=(li+ls)div 2;





if v[i]<v[m] then poz:=poz(li,m,i)

else poz :=poz(m,ls,i);

end;

end;

procedure deplasare(k,i:integer);

var man:real;

j:integer;

begin


if k<i then begin

man:=v[i];

for j:=I downto k+1 do v[j]:=v[j-1];

v[k]:=man;

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;

for i:=2 to n do begin

k:=poz(1,i-1,i);

deplasare(k,i);

end;

writeln('vectorul ordonat este :');

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

readln;

end.