Размещение путем поиска места и вставки
В процедуре, реализующей сортировку вставкой с таким вариантом размещения, целесообразно использовать две вспомогательные процедуры: 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.
|