Линейная сортировка (сортировка отбором)

Идея линейной сортировки по не возрастанию заключается в том, чтобы, последовательно просматривая весь массив, отыскать наибольшее число и поместить его на первую позицию, обменяв его с элементом, который ранее занимал первую позицию. Затем просматриваются все остальные элементы массива и выполняется аналогичная операция по отбору из рассматриваемой части массива максимального элемента и обмену местами этого элемента и первого в рассматриваемой части и т.д.

Введем в разделе описание следующие целые переменные:

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.