где Oj - неотрицательные целые числа; но число 2(2 - 1) - 1 нельзя представить в таком виде. Более того, существует ровно 2*" (2* + s - 3) целых положительных чисел, которые нельзя представить в таком виде.

Найдите аналогичные формулы для случая, когда в этом представлении выражение 2* - 1 заменено выражением 2* + 1.

► 23. [М22} Докажите, что если hs+2 и hs+i - взаимно простые числа, то количество перезаписей в ходе выполнения алгоритма D при просмотре со смещением hs есть 0{Nhs+2hs+i/hs)- (Указание. См. упр. 21.)

24. [М42] Докажите, что теорема Р - наилучшая из возможных теорем в том смысле, что показатель 3/2 нельзя уменьшить.

► 25. [М22] Сколько существует перестановок множества {1,2,..,, N}, являющихся одновременно 3- и 2-упорядоченными? Каково максимальное число инверсий в такой перестановке? Чему равно суммарное число инверсий во всех таких перестановках?

26. [М35} Может ли 3-, 5- и 7-упорядоченный массив из N элементов содержать более Л инверсий? Оцените максимальное количество инверсий при большом N.

27. [M4I} (Бьерн Пунен (Bjorn Poonen).) (а) Докажите, что существует константа с, такая, что если т из смещений hs в алгоритме D имеют величину, меньшую N/2, то время выполнения будет в худшем случае равно (Л""). (Ь) Следовательно, время выполнения алгоритма D будет в худшем случае равно n(A(logA/loglogiV)) для всех последовательностей смещений.

28. [15] Какая из последовательностей смещений, указанных в табл. 6, наилучшая для программы D с точки зрения суммарного времени выполнения сортировки?

29. [40] Найдите для Л = 1000 и различных значений t эмпирические значения ht-i,

hi, ho, которые, быть может, минимизируют среднее число операций перемещения записей Save в алгоритме D.

30. [М23] (В. Пратт (V. Pratt).) Покажите, что если множество смещений при сортировке методом Шелла есть {23 23 < N}, то число проходов равно примерно i(log2 A)(log3 iV) и на каждый просмотр приходится не более N/2 операций перестановки записей. В действительности, если Kj-h > Kj, то на любом проходе Kj-sh, Kj-2h Kj < К j-h < Kj+h,Kj+2h; так что можно просто поменять местами Kj-h и Kj и увеличить j на 2h, сэкономив два сравнения в алгоритме D. (Указание. См. упр. 25.)

► 31. [25] Напишите MIX-программу для алгоритма сортировки, предложенного Праттом (упр. 30). Выразите время ее выполнения через параметры А, В, S, Т, N, аналогичные соответствующим параметрам в программе D.

32. [10] Каково будет окончательное содержимое связей LoLi ... Lie, если провести до конца сортировку списка посредством вставок в табл. 8?

► 33. [25] Как усовершенствовать программу L, чтобы время ее выполнения определялось величиной 5В, а не ТВ, где В5В - число инверсий. Проанализируйте возможность подобного улучшения применительно к программе S.

34. [М10] Проверьте формулу (14).

35. [21] Напишите MIX-программу, которая должна выполняться после программы М и объединять все списки в единый список. Созданная программа должна устанавливать поля LINK точно так, как если бы они были заполнены программой L.

36. [18] Предположим, что размер байта компьютера MIX равен ста и значения шестнадцати ключей в табл. 8 равны 503000, 087000, 512000,..., 703000. Определите время работы программ L и М с этими данными при М = 4.

37. [М25] Пусть gn(z) - производящая функция для числа инверсий в случайной перестановке п элементов (ср. с формулой 5.1.1-(11)). Пусть дмм{г) - соответствующая производящая функция для величины В в программе М. Покажите, что

n>0 Vn>0 /

И воспользуйтесь этой формулой для вывода дисперсии величины В.

38. [НМ23] (Р. М. Карп (R. М. Кагр).) Пусть F{x) - некоторая функция распределения вероятностей, причем F(0) = О и F(l) = 1. Докажите, что если ключи Ki,K2,.-,Kn независимо выбираются случайным образом из последовательности чисел с этим распределением и М = cN, где с - константа, а оо, то время выполнения программы М есть 0{N), если только F - достаточно гладкая функция. (Ключ К вставляется в список j, если [МК\ = j - 1; это случается с вероятностью F{j/M) - F{(j - 1)/М). В тексте раздела рассматривался лишь случай F(x) = х, О < х < 1.)

39. [НМ16] Если программа выполняется приблизительно за А/Ы + В машинных циклов и использует С + М ячеек памяти, то при каком выборе М достигается минимальное значение произведения пространства памяти на время выполнения?

► 40. [НМ24] Найдите выражение для асимптотической величины среднего числа максимумов слева направо (формула (15)), которое возникает при множестве вставок в список, если М = N/a для фиксированного а при N оо. Проанализируйте поведение абсолютной ошибки 0{N~), сформулировав ответ в терминах показательной интегральной функции Eiiz) = e-dt/t.

41. [НМ26] (а) Докажите, что сумма первых (*) элементов в (10) равна 0{р). (Ь) Теперь докажите теорему I.

42. [НМ43] Проанализируйте поведение усредненного показателя в ходе выполнения сортировки Шелла, если имеется t = 3 смещений Л, g и 1 и полагается, что h L д. Очевидно, что на первом проходе при выполнении Л-сортировки получим в среднем N/h + 0{N) перемещений записей.

a) Докажите, что второй проход, g-сортировка, даст {\/h - l/s/h)N/g -Ь 0{hN) перемещений записей.

b) Докажите, что третий проход, 1-сортировка, даст xj){h,g)N+0{9h) перемещений, где

*<M,.i:i:Cr)a)(-ir

м L д J

* 43. [25] В упр. 33 для ускоренного выполнения алгоритма S используется прием, который делает ненужной проверку "г > О" на шаге S4. Этот фокус не проходит в алгоритме D. Покажите, что, тем не менее, существует возможность избавиться от проверки "г > О" на шаге D5, повысив тем самым скорость выполнения внутреннего цикла сортировки Шелла. 44. [М25] Если 5г = aj... а„ и тг = oj... а„ - суть перестановки множества {1,..., п}, будем говорить, что тг < тг, если г-й наибольший элемент в {aj,..., } меньше или равен t-му наибольшему элементу в {oi,...,Oj} при 1 < г < j < п. (Другими словами, 5г < 5г, если для всех j сортировка посредством простых вставок тг является покомпонентно меньшей или равной сортировке посредством прямых вставок тг после того, как вставлены первые j элементов.)

a) Если 5г находится "выше" тг в смысле, определенном в упр. 5.1.1-12, следует ли из этого, что тг < 5г?

b) Если тг < 5г, следует ли из этого, что тг > тг?

c) Если 5г < тг, следует ли из этого, что тг расположена выше 5г?

5.2.2. Обменная сортировка

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

Реализацию метода простых вставок (алгоритм 5.2.IS) можно рассматривать как обменную сортировку: берем новую запись Rj и, по существу, меняем местами с соседями слева до тех пор, пока она не займет нужное место. Следовательно, классификацию методов сортировки по таким семействам, как вставки, обмены, выбор и т. д., нельзя считать слишком строгой. В этом разделе рассматриваются четыре типа методов сортировки, для которых обмен является основной операцией: обменную сортировку с выбором (метод пузырька), обменную сортировку со слиянием (параллельную сортировку Бэтчера), обменную сортировку с разделением (быструю сортировку Хоара) и поразрядную обменную сортировку.

Метод пузырька. Пожалуй, наиболее очевидный способ обменной сортировки - сравнить Ki с К2, меняя местами Ri и R2, если их ключи расположены не в нужном порядке, и затем проделать то же самое с Лг и Лз, Лз и Л4 и т. д. При выполнении этой последовательности операций записи с большими ключами будут продвигаться вправо; и действительно, все это закончится тем, что запись с наибольшим ключом займет положение Rn- При многократном выполнении данного процесса соответствующие записи попадут в позиции Rn-i, Rn-2 и т. д., так что, в конце концов, все записи будут упорядочены. На рис. 14 показано использование этого метода сортировки для шестнадцати ключей: 503 087 512 ... 703. Последовательность чисел удобно представлять не горизонтально, а вертикально, чтобы запись Лдг была в самом верху, а Л1 - в самом низу. Метод назван "методом пузырька" потому что большие элементы, подобно пузырькам, "всплывают" на соответствующую позицию в противоположность "методу погружения" (т. е. методу простых вставок), в котором элементы погружаются на соответствующий уровень. Метод пузырька известен и под более прозаическими именами, такими как "обменная сортировка с выбором" и "метод распространения".

Нетрудно видеть, что после каждого просмотра последовательности все записи, расположенные выше самой последней, которая участвовала в обмене, и сама эта запись должны занять свои окончательные позиции, так что их не нужно проверять при последующих просмотрах. На рис. 14 процесс сортировки с этой точки зрения отмечен подчеркиванием последнего элемента, занявшего верную позицию. Обратите внимание, например, на то, что после четвертого прохода видно, что еще пять записей сразу заняли свои окончательные позиции. При последнем просмотре перемещения записей вообще не было. Теперь, понаблюдав за процессом, мы готовы сформулировать алгоритм.

Алгоритм В {Метод пузырька). Записи Л1,..., Ллг перекомпоновываются в пределах того же пространства памяти; после завершения сортировки их ключи будут упорядочены так: Ki < < Км (рис. 15).

В1. [Начальная установка BOUND.] Присвоить BOUND <- N. (BOUND - индекс самого верхнего элемента, о котором еще не известно, занял ли он свою окончательную