подмассивов длиной т(1 < m < к); затем для завершения задачи пользуется сортировка методом пузырька. Отметим, что последняя т* i перь может проходить по всему массиву, минимизируя тем cainJl затраты на управление. Найдите значение т, минимизирующее 0614 время сортировки.

Примечание. Ясно, что оптимальное значение т будет достаточд мало. Тогда, может быть, стоит позволить, чтобы сортировка методе,!! пузырька проходила по всему массиву ровно т - 1 раз, вместо тог чтобы определять последний проход, на котором не производилось щ каких обменов.

2.7. Проведите тот же эксперимент, что и в упр. 6 с сортировкой простьц, выбором вместо сортировки методом пузырька. Конечно, сортировка простым выбором не может проходить по всему массиву, поэтому ожи. даемый объем работы с индексами несколько больше.

2.8. Напишите рекурсивный алгоритм быстрой сортировки согласно указа, нию, что сортировку меньшего подмассива следует выполнять раныие

гпртирпнки бп.прр дппннпгп ппгтичррнпп В1.тпп.днитр первую задачу при

помощи итеративного оператора, а последнюю - при помощи рекур. , сивного вызова. (Следовательно, ваша процедура сортировки будет содержать один рекурсивный вызов в отличие от программы 2.10, содержащей 2 вызова, и программы 2.11, ие содержащей ни одного.)

2.9. Найдите перестановку ключей 1, 2, п, для которой быстрая сортировка ведет себя наихудшим (наилучшим) образом (я = 5, 6, 8).

2.10. Напишите программу естественного слияния, которая, подобно программе простого слияния 2.13, работает на массиве двойной длины с двух концов в середину. Сравните ее характеристики с характеристиками программы 2.13.

2.11. Заметьте, что при двухпутевом естественном слиянии мы не прост слепо выбираем наименьшее значение из имеющихся ключей. Вместо; этого, когда встречается конец серии, остаток другой серии просто пе-. реписывается в выходную последовательность. Например, слияние

2, 4, 5, 1, 2,... 3.6,8,9,7....

дает последовательность

2, 3, 4, 5, 6, 8, 9, 1. 2, ...

вместо последовательности

2, 3, 4, 5, 1, 2, 6, 8, 9, ...

которая кажется лучше упорядоченной. Почему принята такая стратегия?

2.12. Зачем нужна переменная la в программе 2.15? При каких условиях выполняется оператор

bi-ginrewrlte{f[ta[mx]\); ...

а при каких - оператор

begin tx := ta[mx]; ...7

2.13. Почему в программе многофазной сортировки 2.16 требуется пере- менная last, а в программе 2.15 она не нужна?

в.14. Существует метод сортировки, похожий на многофазную сортировку так называемое каскадное слияние [2.1, 2.9]. Он использует друго

ойВЦИ'П слияния. Если, например, даны шесть лент Г1,...,7 6, кас-пное слияние, начиная также с идеального распределения серий

я 7 1> вьшолияет пятипутевое слияние с Т\, ..., ТЪ на Г6,

пока не станет пустой, затем (не затрагивая 7 6) четырехпутевое слияние иа 7 5, затем трехпутевое слияние на ТА, двухпутевое слияние на и, наконец, перепись с Т\ иа Т2. Следующий проход работает-таким же образом, - иная с пятипутевого слияния на Т\ и т. д. Хотя эта схема каяо^ Чуже многофазного слияния, поскольку временами оставляет ri\ (%1ые ленты без работы, а также выполняег дерадин-простого Kdi-l-ания, она, к удивлению, оказывается луч-Bie многофазной для оЧ- больших файлов и для шести и более леят. Напишите хорошо струк^-ированную программу каскадного слияния..

яитература

0 1 BETZ В. К., CARTER. -ЛСМ National Conf., 14, 1959, Paper 14.

ni FLOYD R. W. Treesort (Algorithms 113, 243), Comm. ACM, 5, No. 8,.

1962, 434, Comm. ACM, 7. No. 12, 1964, 701. 0 4 GILSTAD R. L. Polyphase Merge Sorting - An Advanced Technique.--

Proc. AFIPS Easter Jt. Сотр. Conf. 18, 1960, 143-148. 04 HOARE C. A R. Proof of Program. FIND. -Comm. ACM, 13, No. 1,

1970, 39-45.

25 HOARE C. A. R. Proof of Recursive Program: Quicksort. - Сотр. 14, No. 4, 1971, 391-395.

2.6. HOARE C. A. R. Quicksort. - Сотр. /., 5, No. 1, 1962, 10-15.

v. KNUTH D. E. The art of Computer Programming, 3, - Reading, Mass.: Addison-Wesley, 1973. [Имеется перевод: Кнут Д. Искусство программирования для ЭВМ, т. 3. - М.: Мир, 1978.]

2.8. KNUTH D. Е. The art of Computer Programming, 3, 86-95. [Имеется перевод: Кнут Д. Искусство программирования для ЭВМ, т. 3. - М.г Мир, 1978, с. 108-119.]

2.9. KNUTH D. Е. The art of Computer Programming, 3, 289. [Имеется перевод: Кнут Д. Искусство программирования для ЭВМ, т. 3. - М.г Мир, 1978, с 342.]

1.10. LORIN Н. А Guided Bibliography to Sorting. - IBM Syst. J., 10, No. 3,

1971, 244-254.

2.11. SHELL D. L. A Highspeed Sorting Procedure. - Comm. ACM, 2, No. 7,. 1959, 30-32.

112. SINGLETON R. C. An Efficient Algorithm for Sorting with Minimal Storage (Algorithm 347). -Comm. ACM, 12, No. 3, 1969, 185.

13. Van EMDEN M. H. Increasing the Efficiency of Quicksort (Algorithm

402). -Comm. ACM, 13, No. 9, 1970, 563-566, 693.

b-14. WILLIAMS J. W. J. Heapsort (Algorithm 232). -Comm. ACM, 7, No. 6, 1964, 347-348.

РЕКУРСИВНЫЕ АЛГОРИТМЫ

3.1. ВВЕДЕНИЕ

Объект называется рекурсивным, если он содержит сац себя или определен с помощью самого себя. Рекурсия ветре, чается не только в математике, но и в обыденной жизни Кто не видел рекламной картинки, которая содержит сво{ собственное изображение?

Рекурсия является особенно мощным средством в мате. матических определениях. Известны примеры рекурсивнщ определений натуральных чисел, древовидных структур и щ. которых функций:

1. Натуральные числа:

(a) 1 есть натуральное число;

(b) целое число, следующее за натуральным, есть нату. ральное число.

2. Древовидные структуры:

(a) О есть дерево (называемое пустым деревом);

(b) если tin t2 - деревья, то

А

есть дерево (нарисованное сверху вниз); )

3. Функция факториал п\ для неотрицательных целых чисеЯ

(a) 0! = 1,

(b) если rt >> О, то п! = п- (п - 1)!

Очевидно, что мощность рекурсии связана с тем, что она позволяет определить бесконечное множество объектов с помощью конечного высказывания. Точно так же бесконечны вычисления можно описать с помощью конечной рекурсиВ ной программы, даже если эта программа не содержит явных циклов. Однако лучще всего использовать рекурсивны алгоритмы в тех случаях, когда рещаемая задача, или вЫ числяемая функция, или обрабатываемая структура даннь' определены с помощью рекурсии. В общем виде рекурсивнУ программу Р можно изобразить как композицию базовь*