Песни о Паскале

Деревенец Олег Виленович

О рекурсии и стеке

Такой самовызов процедур называют рекурсией. «У попа была собака…» – помните? Это рекурсия, познакомимся с нею ближе (с рекурсией, а не собакой).

Легко заметить, что повторные вызовы процедуры QuickSort выполняются с другими значениями левой и правой границ. Чем глубже вызов, тем уже эти границы. С некоторого момента условия (R > aL) и (L < aR) перестают выполняться, и происходит выход из процедуры, – здесь фермеры возвращаются к несортированным частям массива.

Таким образом, при выходе мы снова попадаем в эту же процедуру, но в другое место – следующее за вызовом. Окончательный выход из процедуры в главную программу случится только по завершении сортировки всего массива!

Напрашивается вопрос: какова судьба локальных переменных и параметров при повторных входах в процедуру? Ведь они изменятся, а это должно нарушить работу процедуры. Параметры и локальные переменные действительно изменяются, но это не путает алгоритм. Почему?

Разгадка в том, что при каждом входе в процедуру для её параметров и локальных переменных выделяется новый участок памяти. Теперь это будут уже другие параметры и локальные переменные, но с прежними названиями. Однако предыдущие их значения не теряются, а сохраняются в памяти, называемой стеком (Stack).

Что такое стек и как он работает? Случалось ли вам паковать рюкзак или глубокую сумку? Тогда вы знакомы со стеком. Все, что уложено в рюкзак, будет извлекаться из него в обратном порядке. Так же устроен и стек: при каждом вызове процедуры память для параметров и локальных переменных выделяется на его вершине. Эти новые значения временно закрывают предыдущие значения параметров, и так происходит при каждом входе в процедуру.

При выходе из неё последние значения параметров и локальных переменных удаляются с вершины стека, и тогда вновь открываются ранее скрытые. Так процедура «вспоминает» о неоконченной работе, и продолжает действия с параметрами, сохраненными в стеке ранее. В некоторый момент стек пустеет (когда все вещи из рюкзака вынуты), и тогда происходит окончательный выход из процедуры в главную программу.

Механизм стековой памяти заложен в конструкцию процессора, и он не требует участия программиста. Стек используется для любых процедур и функций, а не только рекурсивных.

Но стоп! О стеке поговорим позже, а сейчас займемся делом. Введите программу «P_43_2» и убедитесь в её правильной работе.

Алгоритмы, на старт!

Теперь в нашем распоряжении есть три процедуры сортировки, не устроить ли состязание между ними? На старт вызываются:

• BubbleSort – «пузырьковая» сортировка,

• FarmSort – «фермерская» сортировка,

• QuickSort – быстрая сортировка.

Время «спортсменов» мы будем засекать не по часам. И вы знаете, почему: мы сравниваем алгоритмы, а не компьютеры. В 42-й главе, где сравнивались алгоритмы поиска, мы оценивали время по количеству выполненных шагов. Поступим и здесь похожим образом. Вспомним, в чем состоит сортировка? – в сравнениях и перестановках. И много-много раз… Значит, трудоемкость сортировки можно оценить количеством этих двух операций – сравнений и перестановок, надо их только посчитать.

Что

ж, дело нехитрое, сейчас посчитаем, – перед вами программа для наших опытов («P_43_3»). Количество сравнений и перестановок будем накапливать в переменных C1 и C2. Обратите внимание на их тип – EXTENDED, – это переменные действительного типа. Почему не длинное целое? При сортировке больших массивов может потребоваться столь много операций, что не хватит целочисленной переменной, – она переполнится, «лопнет», и результат исказится. Потому выбран тип EXTENDED.

Далее в программе следуют знакомые вам процедуры сортировки, – это наши «спортсмены». В их тела «вживлены» дополнительные операторы для подсчета сравнений (C1) и перестановок (C2), – они выделены курсивом. Наконец, главная программа, – она вызывает по очереди каждую из процедур и печатает количество сравнений и перестановок. Здесь равные условия для соревнующихся создаются загодя сформированным случайным массивом Arr0, который копируется в массив Arr перед каждой сортировкой.

Вам осталось лишь задать размер массива константой CSize, скомпилировать и запустить программу.

{ P_43_3 – Сравнение алгоритмов сортировки }

const CSize=100; { размер массивов }

type TNumbers = array [1..CSize] of Integer;

var Arr0 : TNumbers; { несортированный массив-заготовка }

Arr : TNumbers; { сортируемый массив }

C1, C2 : extended; { счетчики сравнений и перестановок }

{ BubbleSort "пузырьковая" сортировка }

procedure BubbleSort(var arg: TNumbers);

var i, j, t: Integer;

begin

for i:= 1 to CSize-1 do

for j:= 1 to CSize-i do begin

C1:=C1+1; { подсчет сравнений }

if arg[j] > arg[j+1] then begin

C2:=C2+1; { подсчет перестановок }

t:= arg[j]; arg[j]:= arg[j+1]; arg[j+1]:= t;

end;

end;

end;

{ FarmSort – «Фермерская» сортировка }

procedure FarmSort(var arg: TNumbers);

var L, R, T: Integer;

begin

for L := 1 to CSize-1 do

for R := CSize downto L+1 do begin

C1:=C1+1; { подсчет сравнений }

if arg[L] > arg[R] then begin

C2:=C2+1; { подсчет перестановок }

T:= arg[L]; arg[L]:= arg[R]; arg[R]:= T;

end;

end;

end;

{ QuickSort – Быстрая сортировка }

procedure QuickSort(var arg: TNumbers; aL, aR: Integer);

var

L, R, Mid, T: Integer;

begin

L:= aL; R:= aR;

Mid:= (arg[L] + arg[(L + R) div 2] + arg[R]) div 3;

repeat

while arg[L] < Mid do begin L:=L+1; C1:=C1+1 end;

while arg[R] > Mid do begin R:=R-1; C1:=C1+1 end;

if L <= R then begin

if arg[L]>arg[R] then begin

C2:=C2+1; { подсчет перестановок }