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