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