|
Один из самых популярных методов сортировки – «пузырьковый» метод – основан на том, что в процессе исполнения алгоритма более «легкие» элементы массива постепенно «всплывают». Особенностью данного метода является сравнение не каждого элемента со всеми, а сравнение в парах соседних элементов. Алгоритм пузырьковой сортировки по убыванию состоит в последовательном просмотре снизу вверх (от начала к концу) массива М. Если для соседних элементов выполняется условие, согласно которому элемент, находящийся справа, больше элемента, находящегося слева, то выполняется обмен значениями этих элементов. Текст программы сортировки массива по невозрастанию можно записать следующим образом: program Sort_Puz;
{Сортировка массива «пузырьковым» методом по невозрастанию} 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, K, L : Byte;
A : integer;
begin
Writeln(‘Исходный массив: ‘);
for I := 1 to Count do Write(M[I],’ ‘);
Writeln;
A:=0;
for I := 2 to Count do
{Сортировка «пузырьковым» методом по невозрастанию}
begin
for J:=Count downto I do
begin
A:=A+1;
if M[J-1]<m[j] p=»» <=»» then=»»></m[j]>
{Если элемент справа больше элемента слева, то «вытеснить» его влево — пузырек «всплывает»}
begin
K:=M[J-1]; {Обмен значениями этих элементов}
M[J-1]:=M[J];
M[J]:=K; {Печатать текущее состояние массива после каждой перестановки}
for L := 1 to Count do Write(M[L]);
Writeln(‘Число итераций =’,А);
end;
end;
end; {Завершение сортировки}
end.
Запустите интегрированную среду программирования. Введите текст программы Sort_Puz и запишите файл на диск под соответствующим именем, а затем откомпилируйте его. После успешного завершения компиляции запустите программу, отслеживая в пошаговом режиме текущие значения переменных I, J, К, M[J], M[J–1], всего массива М, а по окончании цикла J просматривая изменения массива в результате одного прохода. Как можно заметить, при помощи оператора for с параметром J выполняется циклический просмотр элементов массива от последнего до второго, и при этом элементы, большие, чем «соседи» слева, смещаются при обмене к началу массива, а меньшие смещаются вправо – «всплывают» в конце массива. Каждый проход фиксируется счетчиком – увеличением на единицу значения переменной А. После каждого просмотра-сравнения элементов массива просматриваемый участок массива уменьшается на один элемент, так как из рассмотрения исключается самый левый (самый большой) элемент. Такое уменьшение просматриваемого участка реализуется при помощи внешнего цикла for с параметром I. По последнему значению А можно определить, что для данного массива сортировка по невозрастанию пузырьковым методом выполняется за 170 итераций. |