// Binarne Sortowanie Przez Wstawianie
//-------------------------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//-------------------------------------------------

program Insertion_Sort;

const N = 20; // Liczebność zbioru.

var
d : array[1..N] of integer;

// Program główny
//---------------

var
i,j,x,ip,ik : integer;
begin
writeln(' Binarne sortowanie przez wstawianie ');
writeln('-------------------------------------');
writeln(' (C)2005 Jerzy Walaszek ');
writeln;

// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi
// a następnie wyświetlamy jej zawartość

randomize;
for i := 1 to N do d[i] := random(100);
writeln('Przed sortowaniem:'); writeln;
for i := 1 to N do write(d[i] : 4);
writeln;

// Sortujemy

for j := N - 1 downto 1 do
begin
x := d[j];
ip := j;
ik := N + 1;
while ik - ip > 1 do
begin
i := (ip + ik) div 2;
if x <= d[i] then ik := i else ip := i;
end;
for i := j to ip - 1 do d[i] := d[i + 1];
d[ip] := x;
end;

// Wyświetlamy wynik sortowania

writeln('Po sortowaniu:'); writeln;
for i := 1 to N do write(d[i] : 4);
writeln;
writeln('Nacisnij Enter...');
readln;
end.