Размещение путем поиска места и вставки

 

В процедуре, реализующей сортировку вставкой с таким вариантом размещения, целесообразно использовать две вспомогательные процедуры:

1) Find_Place – определяющую подходящее место элемента массива с индексом i в предшествующей ему упорядоченной части массива;

2) Insert – которая обеспечивает перемещение в массиве элемента с индексом i на j-ю позицию и смещение всех элементов с индексами от j до i-1 на одну позицию вправо.

 

На школьном алгоритмическом языке эти процедуры имеют вид:

алг Find_Place(аргрезцелтаб a[0:n], цел i, резцел j)

нач

а[0]:=a[i] |Создаем «барьер» (см. выше)

|Определяем значение индекса j,

j:=i |идя от элемента a[i] к началу массива

нцпока a[j-1]>a[i]

j:=j-1

кц

кон

 

алг Insert(аргрезцелтаб a[1:n], аргцел i,j)

начцел tmp, k

tmp:=a[i] |Запоминаем значение элемента a[i]

нцдля k от i до j+1 шаг -1 |Элементы с индексами от i до j+1

a[k]:=a[k-1] |Смещаем вправо на 1 позицию

кц

a[j]:=tmp;

кон

 

С использованием этих процедур алгоритм сортировки вставками оформляется следующим образом:

 

алг Insert_Sort(аргрезцелтаб a[1:n])

начцел i,j

нцдля i от 2 до n

если a[i]<a[i-1]

то

|Находим место j для элемента a[i]

Find_Place(a,i,j)

|«Вставляем» i-й элемент на j-е место

Insert(a,I,j)

все

кц

 

 

Порядок действий при работе с массивами:

1. В разделе описаний объявить массив;

2. Организовать ввод данных в массив;

3. Выполнить действия, необходимые для получения результата в задаче обработки массива.

4. Вывести результат работы программы.

 

Основная часть

Разработка программы сортировки методом вставки.

При разработке программы следует выполнить следующие шаги:

 

А) Выбрать из Приложения одну из программ сортировки вставкой, составить по ней схему, отладить и исполнить вручную.

 

 

Инструктивно-методические указания по проведению самостоятельного занятия № 1

обсуждены и одобрены на заседании кафедры КС

 

Протокол № ____ от “___” ____________ 200 г.

 

Приложение 1

 

СОРТИРОВКА ВСТАВКАМИ

1. Размещение путем сравнения и обмена.

 

program Project2;

{$APPTYPE CONSOLE}

Uses

SysUtils;

const n=1000;

var a: array [1..n] of integer; i,j,k,m,z:integer;

Begin

write('vvedite razmer masiva k = ');

readln(k);

writeln('vvedite elementi masiva');

for i:=1 to k do readln(a[i]); writeln; //ввод массива

for i:=1 to k do write(a[i],' ');writeln; //вывод массива начального

for i:=2 to k do

if a[i]<a[i-1]

Then

Begin

j:=i;

Repeat

m:=a[j]; a[j]:=a[j-1]; a[j-1]:=m;

j:=j-1

until (j=1)or (a[j]>=a[j-1])

end;

writeln;

writeln('novij masiv');

for i:=1 to k do write(a[i],' '); //вывод отсортированного массива

readln

end.

 

2. Сравнение и обмен с барьером

 

program Project2;

{$APPTYPE CONSOLE}

Uses

SysUtils;

const n=1000;

var a:array[0..n] of integer; i,j,k,m,z:integer;

Begin

write('vvedite razmer masiva k = ');

readln(k);

writeln('vvedite elementi masiva');

for i:=1 to k do readln(a[i]); writeln;

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

for i:=2 to k do

if a[i]<a[i-1]

Then

Begin

a[0]:=a[i];

j:=i;

Repeat

a[j]:=a[j-1];

j:=j-1

until a[0]>=a[j-1];

a[j]:=a[0]

end;

writeln;

writeln('novij masiv');

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

readln

end.

 

3. Размещение путем поиска места и вставки

 

program Project2;

{$APPTYPE CONSOLE}

Uses

SysUtils;

const n=1000;

var a:array[0..n] of integer; i,j,k,m,z:integer;

Begin

write('vvedite razmer masiva k = ');

readln(k);

writeln('vvedite elementi masiva');

for i:=1 to k do readln(a[i]); writeln;

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

for i:=2 to k do

if a[i]<a[i-1]

Then

Begin

a[0]:=a[i];

j:=i;

while a[j-1]>a[i] do j:=j-1;

m:=a[i];

for z:=i downto j+1 do

a[z]:=a[z-1];

a[j]:=m;

end;

writeln;

writeln('novij masiv');

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

readln

 

end.