11.64. Выполнить упражнения 11.62 и 11.63, но при этом в обоих случаях замените нечетно-четное слияние Бэтчера (программа 11.3) на программу 8.2.

11.65. Найти значения Р, для которых {N/P)\g N= NP\gP, ддя N = \0\ 10 10 и lOl

11.66. Найти приближенные выражения вида CiAlg cjNддя определения числа сравнений элементов данных, используемых параллельной поблочной сортировки Бэтчера для Р= 1,4, 16, 64 и 256.

11.67. Сколько параллельных шагов потребуется для сортировки Ш записей, которые распределены на 1000 дисков, используя для этой цели 100 процессоров?

Ссылки на источники к части 3

Основным источником для ссылок в данном разделе является том 3 многотомной монографии Кнута (Knuth), посвященный вопросам сортировки и поиска. Практически по каждой теме, которые мы затрагивали до сих пор, в этой книге можно найти полезную информацию В частности, все результаты, касающиеся рабочих характеристик различных алгоритмов, которые обсуждались в данной книге, в указанной монографии обоснованы исчерпывающим математическим анализом.

Имеется обширная литература по вопросам сортировки. Опубликованная Кнутом и Ривестом (Rivest) в 1973 г. библиография содержит сотни ссылок, благодаря которым можно ознакомиться с положением дел в области разработки и совершенствования множества классических методов, часть из которых была рассмотрена здесь. Более поздние ссылки, сопровождаемые обширной библиографией, охватывающей последние работы, вы найдете в книге Баеца-Ятца (Baeza-Yates) и Тонне (Gonnet). Обзор состояния наших знаний о сортировке Шелла можно найти в статье Седжви-ка (Sadgewick) за 1996 г.

Что касается быстрой сортировки, то наилучшей ссылкой может служить пионерская статья Хоара (Ноаге), вышедшая в свет в 1962 г., где рассматриваются все наиболее важные варианты, которые обсуждались в главе 7. Более подробные детали, касающиеся математического анализа и практических применений многих модификаций и усовершенствований, появившихся уже после того, как этот алгоритм нашел широкое применение на практике, можно найти в статье Седжвика, опубликованной в 1978 г. Бентли (Bently) и Мак-Илрой (МсПгоу) дали его современную трактовку. Материал по трехпутевому разбиению в главе 7 и трехпутевой поразрядной быстрой сортировке в главе 10 основан именно на этой статье и статье Бентли и Мак-Илроя, появившейся в печати в 1978 г. Первый алгоритм, использующий разбиения (двоичная быстрая сортировка или поразрядная сортировка с обменами) были опубликованы в статье Хильдебрандта (Hildebrandt) и Исбитца (Isbitz) в 1959 г.

Структура данных биномиальной очереди Вийемана (Vuillemin) в том виде, в каком она была реализована и исследована Брауном (Brown), поддерживает все операции над очередями с приоритетами элегантно и эффективно. Двоичные сортирующие деревья, описанные Фредманом (Fredman), Седжвиком, Слеатором (Sleator) и Тарь-яном (Tarjan), являются усовершенствованиями базового понятия и представляют немалый практический интерес.

В статье, появившейся в 1993 г., Мак-Илрой, Бостик (Bostic) и Мак-Илрой представляют положение дел с реализацией поразрядной сортировки.

Список литературы

R. Baeza-Yates and G. Н. Gonnet, Handbook of Algorithms and Data Structures, second edition, Addison-Wesley, Reading,MA, 1984.

J. L. Bentley and M. D. Mcllroy, Engineering a sort function, Software-Practice and Experience 23, 1 (January, 1993).

J. L. Bentley and R. Sedgewick, Sorting and searching strings, Eighth Symposium on Discrete Algorithms, New Orleans, January, 1997.

M. R. Brown, Implementation and analysis of binomial queue algorithms, SIAM Journal of Computing 7, 3 (August, 1978).

M. L. Fredman, R. Sedgewick, D. D. Sleator, and R. E. Tarjan, The pairing heap: a new form of self-adjusting heap, Algorithmica 1, 1 (1986).

P. Hildebrandt and H. Isbitz, Radix exchange - an internal sorting method for digital computers, Journal of the ACM, 6, 2 (1959).

C. A. R. Hoare, Quicksort, Computer Journal, 5, 1 (1962).

D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching, second edition, Addison-Wesley, Reading, MA, 1997.

P. M. Mcllroy, K. Bostie, and M. D. Mcllroy, Engineering radix sort, Computing Systems 6, 1 (1993).

R. L. Rivest and D. E. Knuth, Bibfiography 26: Computing Sorting, Computing Reviews, 13 6 (June, 1972).

R. Sedgewick, Implementing quicksort programs, Communications of the ACM 21, 10 (October 1978).

R. Sedgewick, Analysis of shellsort and related algorithms, Fourth European Symposium on Algorithms, Barcelona, September, 1996.

J. Vuillemin, A data structure for manipulating priority queues, Communications of the ACM 21, 4 (April 1978).