Идея линейной сортировки по не возрастанию заключается в том, чтобы, последовательно просматривая весь массив, отыскать наибольшее число и поместить его на первую позицию, обменяв его с элементом, который ранее занимал первую позицию. Затем просматриваются все остальные элементы массива и выполняется аналогичная операция по отбору из рассматриваемой части массива максимального элемента и обмену местами этого элемента и первого в рассматриваемой части и т.д.
Введем в разделе описание следующие целые переменные:
I-для указания позиции первого элемента в рассматриваемой части массива;
J-для указания позиции очередного сравниваемого с ним элемента;
N-для временного хранения значения первого элемента для обмена значениями с максимальным из рассматриваемой части массива;
L-параметр цикла при выводе текущего значения элементов массива в процессе сортировки для наблюдения происходящих в массиве наблюдений;
A-переменная, значение которой будет равно числу перестановок элементов.
Вначале запишем вывод исходного массива на экран:
Writeln (′Исходный массив:′);
for I:=1 to Count do Write (‘’,M[I]);
Writeln;
Переход началом сортировки установим значение счетчика итераций А, равно 0. для сортировки организуем два цикла for. Внешний цикл с параметром I, указывающим позицию первого элемента в не отсортированной части массива, и внутренний цикл с параметром J, указывающим позицию очередного, сравниваемого с первым, элемента не отсортированной части массива. Сравнение элементов запишем оператором:
if M[I]<M[J] then
begin
N:= M[I];
M[I]:= M[J];
M[J]:=N;
end;
Если условие M[I]<M[J] выполняется, т.е. в не отсортированной части массива найден элемент, больший, чем первый, то обменять местами эти элементы. Обмен осуществляется следующим образом: сначала значение M[i] запоминается в переменой N, затем значение элемента массива из J-й позиции записывается в 1-го позицию, а после этого в J-ю позицию массива записывается значение переменной N. Для наблюдения изменений состояния массива после каждой перестановки зададим цикл вывода значений всех элементов массива и напечатаем текущее значение числа перестановок элементов А следующим образом:
for L:=1 to Count do Write (‘’,M[L]); Writeln(′Число итераций=′,А);
Полный текст программы линейной сортировки массива М по невозрастанию может быть записан так:
Program Sort Lin; {Линейная сортировка по невозрастанию}
const
Count=20;
M: array [1.. Count] of byte=(9, 11, 12, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 20, 20, 19, 2, 5);
var
I, J, N, L: Byte;
A:integer;
begin
Writeln(′Исходный массив:′);
for I:=1 to Count do
Write (‘’, M [L]); Writeln
A:=0;
for I:=1 to Count-1do{Изменять размер неотсортированной части массива}
for J:=I+1 to Count do {Сравниваем поочередной 1-й элемент неотсортированной части массива со всеми отI+1-го до конца}
begin
A:=A+1;
if M[I]<M[J] than {Если в неотсортированной части массива нашли элемент/больший, чем 1-й, то обменять их местами}
begin
N: = M [I]; {Запомнить на время значение M [I]}
M [I]: = M [J];
M [J]: = N;
end;
for L:=1 to Count do
Write (‘’, M [L]); Writeln (′Число итераций=′,А);
end;
end.