2. Сортировка

нель h на выходную ленту /[/] можно просто описать cjj дующим образом:

writeif [j], Н[1]У, readifO,h[l]y, siftiUn)

(2.51)

Sift ( просеивание ) - это процесс, описанный g разд. 2.2.5. Новая вставляемая компонента h[l] просеивается на соответствующее место. Отметим, что h[l] - наименьший элемент в пирамиде. Пример дан на рис. 2.17.

Состояние до передачи элемента:

f[i]

31 27

Состояние после передачи очередного элемента:

Рис. 2.17. Просеивание ключа через пирамиду.

В конечном счете программа значительно усложняется, поскольку:

1. Пирамида h вначале пуста и прежде всего должна быть заполнена.

2. К концу работы пирамида заполнена лищь частично, а в самом конце становится пустой.

3. Нужно сохранять информацию о начале новых серий, дЛ того чтобы вовремя сменить индекс выходной ленты /.

,лр всего опишем формально переменные, явно участвую-

й . var fO: tope;

f:array[tojoerto]oftape; 252)

h: array [1. .tn] of item;

t,r: integer

размер пирамиды h. Для обозначения т/2 мы исполь- veM константу mh; I и г - индексы в h. Процесс пропуска элементов через пирамиду можно теперь разбить на пять отдельных этапов:

1 Прочесть mil первых элементов с /О и записать их в верх-нюю половину пирамиды, где не требуется никакого упо-)ядочения ключей.

2. Прочесть mh остальных элементов и записать их в нижнюю половину пирамиды, просеивая каждый элемент на соответствующее место (построить пирамиду).

3. Установить / в m и выполнить для оставшихся на /О элементах следующий шаг: отправить h[l] на текущую выходную ленту. Если его ключ меньше или равен ключу следующего элемента входной ленты, то этот следующий элемент принадлежит той же серии и его можно просеять на подходящее место. В противном случае надо уменьшить размер пирамиды и поместить новый элемент во вторую, верхнюю пирамиду, которая строится для следующей серии. Границу между двумя пирамидами обозначим индексом /. .Итак, нижняя , или текущая, пирамида состоит из элементов ii[l] ... h[l], а верхняя , или следующая, пирамида - из /г[/+1] ... h[m]. Если / = О, то нужно сменить выходную ленту и вновь установить / в т.

4. Теперь входные ленты исчерпаны. Вначале установить г в т, затем сбросить на выходную ленту нижнюю часть пирамиды, заканчивающую текущую серию, одновременно построить верхнюю часть и постепенно переместить ее в позиции h[l+l] ... h[r].

- Последняя серия формируется из оставшихся элементов пирамиды.

Теперь мы можем подробно описать эти пять этапов Виде законченной программы, вызывающей процедуру lecttape как только найден конец серии и нужно совершить которое действие, изменяющее индекс выходной ленты. Программе 2.17 вместо этого используется фиктивная про-Дура: она просто подсчитывает число сформированных серий. Все элементы записываются на ленту /1.

Анализ и выводы. Какой эффективности можно ожидать от многофазной сортировки с начальным распределение ! серий с помощью пирамидальной сортировки? Вначале ni обсудим, каких улучшений следует ожидать от использования пирамиды.

В последовательности со случайно распределенными клР чами средняя длина серий равна 2. Какова эта длина посЛ того, как последовательность пропущена через пирамиД) размером т? Казалось бы, нужно ответить т, но, к счастЫ результат вероятностного анализа на самом деле намнос лучще, а именно равен 2т (см. [2.7], т. 3, с. 304). Поэтой ожидаемый коэффициент улучшения равен т.

Если теперь мы попытаемся объединить эту nporpaMj : например, с программой многофазной сортировки, то стол, немея с серьезной трудностью. Она возникает по следующ^ причинам: программа сортировки содержит вначале довольн сложную процедуру для переключения лент и предполагае^ наличие процедуры copyrun, которая записывает .на выбра^ ную ленту ровно одну серию. С другой стороны, програцщ, пирамидальной сортировки представляет собой сложную про. цедуру, предполагающую наличие закрытой процедуры-sg.i lecttape, которая просто выбирает новую ленту. Проблемы не возникало бы, если бы в одной (или обеих) про. грамме нужная процедура вызывалась лищь в одном месте однако она вызывается в нескольких местах в обеих про. граммах. \

-В такой ситуации лучще всего использовать так называе!

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

Сопрограмму можно рассматривать как процедуру, или подпрограмму, которая содержит одну или несколько точен прерывания. Если встречается такая точка прерывания, те управление возвращается в программу, вызвавшую эту сопрограмму. При повторном вызове сопрограммы ее выполнение возобновляется с этой точки прерывания. В нашем-примере мы можем рассматривать многофазную сортировку) как основную программу, вызывающую copyrun, которая по-; строена в виде сопрограммы. Она состоит из основного тела программы 2.17, где каждый вызов selecttape теперь прея ставляет собой точку прерывания. Проверку на конец файла^ нужно всюду заменить проверкой, достигла ли сопрограмма своего конца. Логично заменить еоД/0) на еос{соругип).