порядок? Объясните, как выбрать смещения xj, хг, ..., хр с тем, чтобы в худшем случае требовалось как можно меньше буферов.

25. [23] Повторите при.мер из текста раздела, рассмотренный в связи с рандомизированным разделением, изменив условия: пусть Q = 3 вместо Q = 4. Что окажется в буферах в отличие от (24)?

26. [26] Сколько выходных буферов необходимо, чтобы выполнение Р-путевого слияния с рандомизированным разделением никогда не было приостановлено из-за отсутствия места в памяти для размещения только что полученных в результате слияния данных? Считайте, что время записи блока равно времени считывания.

27. [НМ27] (Проблема циклической занятости.) Предположим, что п пустых урн расставлены по кругу и им присвоены номера О, 1, ..., п - 1. При к = 1, 2, ..., р мы бросаем mk шаров в урны (Хк + j) mod п, j = О, 1, ..., тк - 1, где целые числа Хк выбираются случайно. Пусть Sn{mi,..., тр) - число шаров в урне О, а En{mi,..., тр) - ожидаемое число шаров в самой заполненной урне.

a) Докажите, что E„(mi,... ,тр) < JZtli min(l, nPr(Sn(mi,... ,тр) > t)), где m = mi + ----h тр.

b) Используя неравенство в соотношении 1.2.10-(25), докажите, что

E„{mi,...,mp) <ymyn[l, -- J

(1+а,)*

для любых неотрицательных действительных чисел ai, аг, ..., Qm- Какие значения ai, ..., От дадут нгшлучшую верхнюю оценку?

28. [НМ47] Продолжая упр. 27, ответьте, справедливо ли неравенство En{mi,..., тр) > En{mi + т2,тз,... ,тр)1

► 29. [МЗО] Назначение этого упражнения - вывести верхнюю оценку среднего времени, необходимого для ввода любой последовательности блоков в хронологическом порядке при выполнении процедуры рандомизированного разделения, когда блоки представляют Р серий и D дисков. Мы говорим, что блок, ожидаемый на некотором временном цикле в то время, когда выполняется алгоритм (см. (24)), является "маркированным"; таким образом. Суммарное время ввода пропорционально числу маркированных блоков. Маркирование зависит только от хронологической последовательности доступа к блокам (см. (20)).

a) Докажите, что если Q + 1 последовательных блоков в хронологическом порядке имеют Nj блоков на диске j, то не более max(yVo, Ni,..., Np-i) из них являются маркированными.

b) Усильте результат (а), показав, что он имеет место также для Q + 2 последовательных блоков.

c) Теперь используйте результаты анализа проблемы циклической занятости из упр. 27 и получите верхнюю оценку среднего времени выгюлнения в терминах функции r{D, Q+ 2), как в табл. 2, задав любой хронологический порядок.

30. [НМЗО] Докажите, что для функции r{d,m) из упр. 29 при s оо выполняется условие r{d,sdlogd) = 1 + 0{l/\/s) для фиксированного d.

31. [НМ48] Проанализируйте рандомизированное разделение и определите поведение этого алгоритма в среднем, а не только по отношению к верхней оценке, как функцию от Р, Q и D. (Интересен даже случай для Q = О, когда требуется в среднем Q{L/\/D ) циклов чтения.)

5.5. РЕЗЮМЕ. ИСТОРИЯ И БИБЛИОГРАФИЯ

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

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

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

Было бы прекрасно, если бы один или два метода сортировки превосходили все остальные безотносительно к приложению или используемой машине. На самом же деле каждый метод имеет свои собственные, одному ему присущие достоинства. Например, метод пузырька (алгоритм 5.2.2В) не имеет ярко выраженных преимуществ, так как всегда можно найти лучший способ сделать то, что он делает; но даже он после соответствующего обобщения оказывается полезным для сортировки с двумя лентами (см. раздел 5.4.8). Итак, приходим к заключению, что почти все алгоритмы заслуживают того, чтобы о них помнили, так как существуют приложения, в которых какой-либо из них оказывается самым подходящим.

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

1. Распределяющий подсчет. Если диапазон ключей невелик, очень полезен алгоритм 5.2D. Метод устойчив (не изменяет порядок записей с равными ключами), но требуется память для счетчиков и 2N записей. Одна из модификаций, позволяющая сэкономить N из этих записей ценой устойчивости, встречается в упр. 5.2-13.

2. Простая вставка. Алгоритм 5.2.IS наиболее прост для программной реализации, не требует дополнительного объема памяти и довольно эффективен при малых N (скажем, при Л < 25). При больших N он становится невыносимо медленным, если только исходные данные не окажутся сразу почти упорядоченными.

3. Сортировка с убывающим смещением. Алгоритм 5.2.ID (метод Шелла) также довольно просто программируется, использует минимальный объем памяти и весьма эффективен при умеренно больших N (скажем, при N < 1000).

4. Вставка в список. Алгоритм 5.2.1L основан на той же идее, что и алгоритм простой вставки, и поэтому годится только при небольших N. Как и в других методах сортировки списков, в нем благодаря операциям со ссылками экономятся затраты на пересылку длинных записей; это особенно удобно, когда записи имеют переменную длину или являются частью других структур данных.

5. Сортировка с вычислением адреса эффективна, если ключи подчиняются известному (обычно - равномерному) закону распределения; важнейшими вариантами этого подхода являются вставки в несколько списков (программа 5.2.1М) и комбинированная поразрядная сортировка со вставками Мак-Ларена (рассмотренная в конце раздела 5.2.5). Для последнего метода достаточно иметь (9(-\/iV) дополнительных ячеек памяти. Двухпроходный метод, который позволяет иметь дело с неравномерным распределением, анализируется в теореме 5.2.5Т.

6. Обменная сортировка со слиянием. Алгоритм 5.2.2М (метод Бэтчера) и родственный ему алгоритм битонной сортировки (упр. 5.3.4-10) полезны, если можно одновременно выполнять большое число сравнений.

7. Обменная сортировка с разделением (метод Хоара, широко известный как быстрая сортировка). Алгоритм 5.2.2Q, вероятно, - самый полезный универсальный алгоритм внутренней сортировки, поскольку он требует очень мало памяти и опережает своих конкурентов по среднему времени вьшолнения на большинстве компьютеров. Однако в наихудшем случае он может работать очень медленно. Поэтому, если вероятность неслучайных данных достаточно велика, приходится тщательно выбирать разделяющие элементы. Если выбирается медиана из трех элементов (как предлагается в упр. 5.2.2-55), то такое поведение, как в наихудшем случае, становится крайне маловероятным и, кроме того, несколько уменьшается среднее время работы.

8. Простой выбор. Алгоритм 5.2.3S довольно прост и особенно подходит в случае, когда имеется специальное оборудование для быстрого поиска наименьшего элемента в списке.

9. Пирамидальная сортировка. Алгоритм 5.2.3Н при минимальных требованиях к памяти обеспечивает достаточно высокую скорость сортировки; как среднее, так и максимальное время работы примерно вдвое больше среднего времени быстрой сортировки.

10. Слияние списков. Алгоритм 5.2.4L осуществляет сортировку списков, обеспечивая при этом, так же как и алгоритм пирамидальной сортировки, весьма высокую скорость даже в наихудшем случае. Кроме того, данный метод устойчив по отношению к равным ключам.

11. Поразрядная сортировка с использованием алгоритма 5.2.5R - это не что иное, как сортировка списков, которая приемлема для ключей либо очень коротких, либо имеющих необычный порядок лексикографического сравнения. Вместо ссылок можно применить распределяющий подсчет (п. 1 нашего обзора); такая процедура потребует пространства для 2N записей и для таблицы счетчиков, но благодаря простоте внутреннего цикла она особенно хороша для сверхбыстрых компьютеров - "пожирателей чисел", имеющих опережающее управление. [Предостережение. Поразрядную сортировку не следует использовать при малых N\)

12. Сортировка методом вставок и слияния (см. раздел 5.3.1) наиболее приемлема при очень малых N в "прямолинейных" программах. Например, этот метод оказался бы подходящим в тех приложениях, в которых требуется сортировать много групп из пяти или шести записей.