Программа
Вернёмся к программе сортировки массива. Итак задача стояла следующим образом (краткое содержание предыдущих 5000 серий :) - программу, которая сортирует массив пузырьковой сортировкой. Этим делом мы сегодня и займёмся. Естественно, что мы используем полученные знания про процедуры и функции.
При этом мы будем считать число сравнений и перестановок. Поэтому напишем такую простую функцию для сравнения двух чисел. При этом переменная CmpCount (число сравнений) предпологается глобальной:
function cmp (a, b : integer) : integer;
begin
CmpCount := CmpCount + 1;
cmp := ord (a > b)
end;
Я надеюсь вы помните, что ord преобразовывает логическое выражение к целому числу. У нас логическое выражени a > b истинно, когда а больше b, поэтому функция вернёт нам 1 в этом случае и 0 в случае, если а меньше b.
Так же напишем процедуру для перестановки значений a и b. В этом случае воспользуемся адрессами переменных. Переменная SwapCount - число перестановок - глобальная:
procedure swap (var a, b : integer);
var
c : integer;
begin
c := a;
a := b;
b := c;
SwapCount := SwapCount + 1
end;
Здесь я думаю всё прозрачно. Теперь подойдём к реализации алгоритма сортировки. Основная мысль алгоритма: сравниваются два соседних элемента, если порядок нарушен, то они меняются местами.
Первая мысль, которая приходит ко мне в голову: нужно продолжать поиск по всем элементам до тех пор пока будет совершена хоть одна перестановка. Давайте введём переменную flag - когда она равна 1, то совершенна перестановка, если 0 - то перестановки не было. Поэтому напишем такое начало:
const
Size = 10;
var
flag : integer;
i : integer;
CmpCount : integer;
SawpCount : integer;
a : array [1 .. size] of integer;
procedure PrintArray;
var
i : integer;
begin
for i := 1 to Size do
write (A[i] : 4);
writeLn
end;
begin
randomize;
flag := 1;
SwapCount := 0;
CmpCount := 0;
for i := 1 to Size do
A[i] := random (100);
PrintArray;
{Начало сортировки}
while flag = 1 do
begin
flag := 0;
end;
PrintArray;
writeLn ('Число сравнений - ', CmpCount);
writeLn ('Число перестановок - ', SwapCount);
ReadLn
end.
Итак А - это массив, который нам нужно отсортировать. Вначале мы его заполняем с помощью случайных чисел. Потом выводим с помощью процедуры PrintArray - её текст настолько очевиден, что я решил не выносить его куда-то на отдельное рассмотрение.
Итак нам нужно пробежать весь массив и сравнить два соседних элемента. Теперь алгоритм превращается в такой:
while flag = 1 do
begin
flag := 0;
for i := 1 to Size - 1 do
if cmp (A[i], A[i +1]) = 1 then
begin
swap (A[i], A[i + 1]) ;
flag := 1
end
end;
обратите внимание, что в цикле мы идём до Size - 1 так как сравниваем i-тый элемент с i+1 элементом. Поэтому i+1 не должно выходить за границу массива, которая у нас и равна Size (т.е. i + 1 <= Size следовательно i <= Size - 1). Мы устанавливаем flag в 1, только если произошла перестановка!
Таким образом число сравнений и обменов у нас получается: (Size - 1) * Size
За один проход максимальный элемент становится на свою позицию, по этому последний элемент проверять не надо. За второй проход не надо проверять предпоследний и так далее.
Поэтому мы можем запомнить максимальный номер соседа, с которым происходило сравнение. И пробегать в цикле соответственно до этого номера
n := Size;
while n > 0 do
begin
last := 0;
for i := 1 to n - 1 do
if cmp (B[i], B[i + 1]) = 1 then
begin
swap (B[i], B[i + 1]);
last := i + 1
end;
n := last
end;
таким образом при проходе мы запоминаем номер соседа в last, если сравнения не произошло, то мы получаем в last 0 и в n тоже 0.
Конечно и этот алгоритм не идеален и его можно улучшить, но на сегодня хватит.
А сейчас мы выдадим ещё одно домашнее задание, так как опыт прошёл успешно. Оно немного не по теме (оно относится к теме Строки), но всё же: сегодня мы предлогаем вам написать программу, которая проверяет является ли строка полиномом. Т.е. одинаково читается справа на лево и с лева на право. Например: ШАБАШ, ШАЛАШ... больше не помню :(
|
