Решение. Пусть задан массив чисел (снова, для простоты рассуждений, возьмем массив целых чисел):

Пусть задан массив чисел (снова, для простоты рассуждений, возьмем массив целых чисел):

12 -3 25 -10 6 8 34 -65 44 17

Этот, заданный массив обозначим именем a. В нашем примере он имеет 10 элементов.

Заведем еще один массив, также из 10 тех же элементов, но уже упорядоченных по возрастанию.

Наша задача будет состоять в построении этого массива. В качестве первого элемента упорядоченного массива b возьмем первый элемент массива a:

Итак, массив b:

Теперь берем второй элемент массива a - это -3 и с помощью процедуры быстрого поиска вставляем его в упорядоченный массив b. Поскольку -3 меньше 12, то он вставится перед 12 и упорядоченный массив b уже будет состоять из 2-х элементов:

-3 12

Берется третий элемент массива a - 25 и вставляется в массив b, получаем:

-3 12 25

И такой процесс будем продолжать до тех пор, пока все n элементов массив a не будут просмотрены. В результате образуется новый упорядоченный массив b.

Способ

Program Problem7; {Сортировка простыми вставками}

uses WinCrt;

const

n = 20;

type

t = array [1..n] of integer;

var

a, b: t;

i, p: integer;

{----------------------------------------------------------------------------------------}

Procedure create(n: integer; var a: t);

var

i: integer;

begin

randomize;

writeln('Заданный массив целых чисел');

for i: = 1 to n do

begin

a[i]: = random(201) - 100;

write(a[i], ' ')

end;

writeln

end;

{----------------------------------------------------------------------------------------}

Procedure quick_search(m, c: integer; b: t; var p: integer);

var

q, s: integer;

begin

p: = 1; q: = m;

while p < q do

begin

s: = (p + q) div 2;

if c > b[s] then p: = s + 1 else q: = s

end

end;

{---------------------------------------------------------------------------------------}

Procedure movement_end(i, k: integer; var b: t);

var

j: integer;

begin

for j: = i downto k + 1 do b[j]: = b[j - 1]

end;

{---------------------------------------------------------------------------------------}

begin

create(n, a);

b[1]: = a[1];

for i: = 2 to n do

begin

quick_search(i, a[i], b, p);

movement_end(i, p, b);

b[p]: = a[i]

end;

writeln;

writeln('Массив упорядоченный по возрастанию.');

for i: = 1 to n do write(b[i], ' ');

writeln

end.

Способ

Program Problem7a; {Сортировка простыми вставками}

uses WinCrt;

const

n = 20;

type

t = array [1..n] of integer;

var

a: t;

i: integer;

{----------------------------------------------------------------------------------------}

Procedure create(n: integer; var a: t);

var

i: integer;

begin

writeln('Заданный массив чисел');

randomize;

for i: = 1 to n do

begin

a[i]: = random(201) - 100;

write(a[i], ' ')

end;

writeln;

end;

{---------------------------------------------------------------------------------------}

Procedure insert(var a: t; n: integer);

var

p, q, s, k, c: integer;

begin

for i: = 2 to n do

begin

p: =1;

q: = i;

c: = a[i];

while p < q do

begin

s: = (p + q) div 2;

if c > a[s] then p: = s + 1

else q: = s

end;

for k: = i downto p + 1 do a[k]: = a[k - 1];

a[p]: = c

end

end;

{----------------------------------------------------------------------------------------}

begin

create(n, a);

insert(a, n);

writeln;

writeln('Массив упорядоченный по возрастанию.');

for i: = 1 to n do write(a[i], ' '); writeln

end.