a) Покажите, что дм{ы+1){г) = 9mn{z) + ((1 - г)/М)дмм{г)-

b) Найдите при помощи указанного соотношения простые выражения для математического ожидания и дисперсии этого распределения вероятностей как функций от М и TV.

7. [20] Проанализируйте, в чем состоит сходство и отличие алгоритма R и обменной поразрядной сортировки (алгоритм 5.2.2R).

► 8. [20] В алгоритмах поразрядной сортировки, обсуждавшихся в тексте раздела, предполагалось, что все сортируемые ключи неотрицательны. Какие изменения следует внести в эти алгоритмы в том случае, когда ключами являются и отрицательные числа, представленные в дополнительном или обратном коде?

9. [20] (Продолжение упр. 8.) Какие изменения нужно внести в эти алгоритмы в случае, когда ключами являются числа, представленные в виде абсолютной величины со знаком?

10. [30] Разработайте алгоритм поразрядной СЦ-сортировки, использующий связное распределение памяти. (Так как размер подмассивов все уменьшается, разумно уменьшить М, а для сортировки коротких массивов применить метод, отличный от поразрядной сортировки.)

11. [16] Перестановка 16 исходных чисел, показанная в табл. 1, содержит вначале 41 инверсию. По завершении сортировки инверсий, разумеется, нет совсем. Сколько инверсий осталось бы в массиве, если пропустить первый просмотр и выполнить поразрядную сортировку лишь по цифрам десятков и сотен? Сколько инверсий останется, если пропустить как первый, так и второй просмотры?

12. [24] (М. Д. Мак-Ларен (М. D. MacLaren).) Предположим, алгоритм R применили только к р старшим цифрам реальных ключей; тогда массив, если его читать по порядку, указанному связями, почти рассортирован, но ключи, старшие р цифр которых совпадают, могут быть неупорядочены. Придумайте такой алгоритм перекомпоновки записей в пределах того же объема памяти, чтобы ключи расположились в порядке Ki < К2 < < Км-[Указание. Частный случай, когда массив полностью рассортирован, можно найти в ответе к упр. 5.2-12; его можно скомбинировать с простыми вставками без потери эффективности, так как в массиве оста/юсь мало инверсий.]

13. [40] Реализуйте метод внутренней сортировки, предложенный в тексте в конце этого раздела, и разработайте программу сортировки случайных данных за 0{n) машинных циклов, требующую всего 0{\/м) дополнительных ячеек памяти.

14. [22] Последовательность игральных карт можно рассортировать в порядке возрастания от верхней карты к нижней за два просмотра, раскладывая их каждый раз лишь в две Стопки:

Разложите карты лицевой стороной вниз в две стопки, содержащие А 2 ... J Q К соответственно (от нижней карты к верхней). Затем положите вторую стопку поверх первой, поверните колоду лицевой стороной вверх и разложите в две стопки; А293 10 и4Л56 Q К 7 8. Сложите эти две стопки и поверните их лицевой стороной вверх. Колода будет рассортирована.

Докажите, что приведенную выше последовательность карт нельзя рассортировать в порядке убывания К Q J ... 2 А от верхней карты к нижней за два просмотра, даже если разрешено раскладывать карты в три стопки, (Сдавать карты нужно всегда сверху колоды, поворачивая их рубашкой вверх. На рисунке верхняя карта колоды изображена справа, а нижняя - слева.)

15. [М25] Рассмотрите задачу из упр. 14 для случая, когда карты раздаются лицевой стороной вверх, а не вниз. Таким образом, один просмотр можно потратить на преобразование возрастающего порядка в убывающий. Сколько нужно просмотров?

► 16. [25] Разработайте алгоритм сортировки строк ai, ..., а„, состоящих из т букв в лексикографическом порядке. Суммарное время выполнения этого, алгоритма должно быть порядка 0{тп + п + N), где TV = ai 4- -I- \ап\ - суммарная длина всех строк.

17. [15] Почему в двухуровневом методе сортировки, предложенном Тамминеном (см. теорему Т), метод, аналогичный алгоритму Мак-Ларена, используется на втором и не используется на первом уровне?

18. [НМ26] Докажите теорему Т. Укозоние. Сначала покажите, что алгоритм Мак-Ларена действительно выполняет в среднем 0(BN) операций, если его применять по отношению к независимым случайным ключам, для которых функция плотности вероятностей удовлетворяет условию f{x) < В при О < а; < 1.

Для сортировки корней и слов нам понадобится 1100 ящиков *1 лотков для форм.

- ДЖОРДЖ В. ВИГРАМ (GEORGE V. WIGRAM) (1843)

5.3. ОПТИМАЛЬНАЯ СОРТИРОВКА

Теперь, когда мы проанализировали множество методов внутренней сортировки, пришло время обратиться к более обш;ему вопросу: какой метод внутренней сортировки наилучший? Существует ли такой верхний предел скорости сортировки, которого бы не мог достичь ни один программист, как бы искусен он ни был?

Разумеется, не существует наилучшего возможного способа сортировки; мы должны точно определить, что понимать под словом "наилучший" но не существует наилучшего возможного способа определения слова "наилучший" Аналогичную проблему, связанную с оптимальностью алгоритмов, мы обсуждали в разделах 4.3.3, 4.6.3 и 4.6.4, в которых рассматривались умножение с повышенной точностью и вычисление полиномов. В каждом случае, для того чтобы задача была поставлена в терминах конкретных математических структур, необходимо было сформулировать довольно простое определение "наилучшего из возможных" алгоритма. И в каждом случае перед нами вставали интереснейшие проблемы, настолько сложные, что они до сих пор полностью не решены. Так же обстоит дело и с сортировкой: были получены некоторые интересные результаты, но осталось еще много интригующих вопросов, на которые до сих пор нет ответов.

Изучение внутреннего механизма методов сортировки обычно было направлено на минимизацию числа сравнений ключей при сортировке п элементов или слиянии т элементов с п элементами, или выборе t-ro наибольшего элемента из неупорядоченного набора п элементов. В разделах 5.3.1-5.3.3 эти вопросы обсуждаются для общего случая; в разделе 5.3.4 рассматриваются аналогичные вопросы с интересным ограничением: схема (структура) сравнений должна быть, по сути, заранее фиксированной. Другие интересные теоретические вопросы, связанные с оптимальной сортировкой, можно найти в упражнениях к разделу 5.3.4 и в разделах 5.4.4, 5.4.8 и 5.4.9, в которых анализируется внешняя сортировка.

Как только появится аналитическая машина, она, безусловно, определит дальнейший путь развития науки. Всякий раз, когда с ее помощью будет найден какой-либо результат, возникнет вопрос: "Существует ли метод вычислений, которым можно получить на этой машине тот же результат, но затратив минимум времени?"

- ЧАРЛЬЗ БЭББИДЖ (1864) 5.3.1. Сортировка с минимальным числом сравнений

Очевидно, минимальное число сравнений ключей, необходимое для сортировки п элементов, равно нулю, поскольку, как мы видели, существуют методы поразрядной сортировки, в которых сравнения вообще не выполняются. В самом деле, можно разработать MIX-программы, способные сортировать и, тем не менее, не содержащие ни одной команды условного перехода! (См. упр. 5-8 в начале этой главы.) Мы также встречались с несколькими методами сортировки, которые, по сути, были основаны на сравнении ключей, но время выполнения которых на деле определялось другими факторами, такими как перезапись данных, вспомогательные операции и т. д.

Поэтому ясно, что подсчет числа сравнений - не единственный способ измерения эффективности метода сортировки. Однако в любом случае небезынтерес-