ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 2
Тема: «Сортировка методом прямого включения»
Цель: научиться сортировать по
возрастанию и убыванию одномерные массивы и массивы записей методом прямого
включения.
Ход работы
Теоретические
обоснования
В этой сортировке массив делится на две части: отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и «включается» в отсортированную часть массива.
Пусть отсортировано начало массива A[1], A[2], ..., A[i–1], а остаток массива A[i], ..., A[n] содержит неотсортированную часть. На очередном шаге будем включать элемент A[i] в отсортированную часть, ставя его на соответствующее место. При этом придется сдвинуть часть элементов, больших A[i], (если таковые есть) на одну позицию правее, чтобы освободить место для элемента A[i]. Но при сдвиге будет потеряно само значение A[i], поскольку в эту позицию запишется первый (самый правый – с самым большим индексом) сдвигаемый элемент. Поэтому прежде чем производить сдвиг элементов необходимо сохранить значение A[i] в промежуточной переменной.
Так как массив из одного элемента можно считать отсортированным, начнем с i = 2.
Выглядит это в виде следующей процедуры:
procedure InsertSort(n: integer;
var A: array[1..n] of integer);
{Процедура сортировки простым включением}
var i, j, Tmp: integer;
begin
for i := 2 to n do begin
{Сохраняем текущий элемент}
Tmp := A[i];
{Сдвигаем элементы,
большие, чем текущий}
j := i;
while (A[j-1] > Tmp) and (j
> 1) do begin
A[j] := A[j-1];
j := j-1;
end;
{Вставляем текущий элемент}
A[j] := Tmp;
end;
end;
Задание 1. Выполнить
сортировку в одномерном массиве. Массив заполнить случайными числами, вывести исходный
массив, выполнить сортировку методом прямого включения, вывести отсортированный
массив.
Задание 2. Дан
массив записей, каждая запись описывается свойствами: марка автомобиля, год
выпуска, стоимость. Выполнить сортировку в массиве записей по полю год рождения
по возрастанию. Выполнить сортировку по полю стоимость по убыванию. Заполнить
массив записей, вывести исходный массив в табличном виде, выполнить две
сортировки методом прямого включения, вывести результат сортировки в табличном
виде, записать результат сортировки в файл, проверить запись в файл
(осуществить считывание записей из файла и вывод их на экран).
Выполнение задания 1 и 2.
Решение задач осуществляется аналогично примеру, рассмотренному в 1 практической работе.
Задания для самостоятельного решения
1. Выполнить сортировку в одномерном
массиве.
2. Выполнить сортировку в двумерном
массиве по столбцам.
3. Выполнить сортировку в двумерном
массиве по строкам.
4. Известны данные о сотрудниках фирмы:
фамилия и отношение к воинской службе (военнообязанный или нет), год рождения. Заполнить
массив записей. Вывести на экран исходные данные в табличном виде. Выдать на
экран меню с выбором сортировки:
1 - Сортировка по полю год рождения.
2 - Сортировка военнообязанных по полю год
рождения.
Выдать на экран отсортированные
данные в табличном виде.