|
Идея линейной сортировки по невозрастанию заключается в том, чтобы последовательно просматривая весь массив, отыскать наибольшее число и поместить его на первую позицию, обменяв его с элементом, который ранее занимал первую позицию. Затем просматриваются все остальные элементы массива и выполняется аналогичная операция по отбору из рассматриваемой части массива максимального элемента и обмену местами этого элемента и первого в рассматриваемой части, и т. д. Введем в разделе описания следующие целые переменные: I – для указания позиции первого элемента в рассматриваемой части массива; J – для указания позиции очередного сравниваемого с ним элемента; N – для временного хранения значения первого элемента для обмена значениями с максимальным из рассматриваемой части массива; L – параметр цикла при выводе текущего значения элементов массива в процессе сортировки для отслеживания происходящих в массиве изменений; А – переменная, значение которой будет равно числу перестановок элементов. Вывод исходного массива на экран запишем следующим образом: 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] выполняется, т. е. в неотсортированной части массива найден элемент, больший первого, то следует поменять местами эти элементы. Перестановка осуществляется следующим образом: сначала значение М[1] запоминается в переменной N, затем значение элемента массива из J-й позиции записывается в 1-ю позицию, а после этого в J-ю позицию массива записывается значение переменной N. Для отслеживания изменений состояния массива после каждой перестановки зададим цикл вывода значений всех элементов массива и напечатаем текущее значение числа перестановок элементов А: for L := 1 to Count do
Write(‘, M[L]);
Writeln( ‘Число итераций=’, А);
Полный текст программы линейной сортировки массива М по невозрастанию может быть записан следующим образом: program Sort_Lin; {Линейная сортировка по невозрастанию} const
Count = 20;
М:аггау [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[I]);
Writeln;
A:=0;
for I := 1 to Count — 1 do {Изменять размер неотсортированной части массива}
for J:=I+1 to Count do {Сравниваем поочередно 1-й элемент неотсортированной части массива со всеми от I+1-го до конца}
begin
А:=А+1;
if M[I] < M[J] then {Если в неотсортированной части массива нашли элемент. больший, чем 1-й, то обменять их местами}
begin
N := М[1]; {Запомнить на время значение М[1]}
M[I] := M[J];
M[J] := N;
end;
for L := 1 to Count do
Write(M[L]);
Writeln(‘Число итераций -‘,А);
end;
end.
Запустите интегрированную среду программирования. Введите текст программы Sort_Lin и запишите файл на диск под соответствующим именем, а затем откомпилируйте его. После успешного завершения компиляции запустите программу, отслеживая в пошаговом режиме текущие значения переменных: I, J, N, M[I], M[J], а также просматривая на экране пользователя результат изменения массива за один проход внутреннего цикла. По последнему значению А можно определить, что для данного массива линейная сортировка по невозрастанию выполняется за 190 итераций. |