9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 26

26

27

28 •

29 •

30 •

31 •

32 •

33

34 36

36 •

37

38 •

39 •

40

41

42

43

7

9

- 10

• 11

• 12

13

14

16

• 16

• 17

18

• 19

• 20

• 21

22

• 23 24

• 26

26

• 27 28

Го

31 32 33 34 36 36 37 38 39 40 41 42 43

Рис. 60. Семейство сетей, возможность которых выполнять сортировку очень сложно проверить. Показан вариант при m = 3 и п = 5 (см. упр. 52).

► 52. [32] (М. О. Рабин (М. О. Rabin), 1980.) Докажите, что в общем случае исключительно трудно дать заключение, является ли данная последовательность компараторов сетью сортировки, анализируя сеть, аналогичную представленной на рис. 60. Принято перенумеровывать входы хо до xn, где N = 2тп + т + 2п; положительные целые числа являются параметрами. Первые компараторы - [j:j + 2пк] при 1 < j < 2п и 1 < А; < т. Тогда имеем [2j-l:2j][0:2j] при 1 <j <п параллельно со специальной подсетью, которая использует только индексы > 2п. Далее сравниваем [Q:2mn+2n+j] при I < j < т. И наконец, существует законченная сеть сортировки для (xi,... ,xn), за которой следует [О; 1][1:2] .. . [iV-t-1: N-t], где t=:mn +n + l.

a) Опишите все входы {xo,xi,... ,xn), которые не сортируются такой сетью, в терминах поведения специальной подсети.

b) Задав множество выражений наподобие (j/i V уг V уз) Л (уг V уз V у4) Л ..., объясните, как построить специальную подсеть по типу сети, показанной на рис. 60, которая сортировала бы все входы тогда и только тогда, когда выражение не удовлетворяется.

53. [30] (Периодическая сеть сортировки.) Две показанные ниже сети следует считать иллюстрацией рекурсивного построения t-уровневой сети при п = 2 в случае t = 4. Если пронумеровать линии входов от О до 2 - 1, то 1-й уровень в случае (а) имеет компараторы [i:j], где г mod 2+" < 2" и j = гф (2+" - 1); всего существует t2" компараторов, как и в сети битонного слияния. В случае (Ь) компараторы первого уровня суть [2j: 2j +1] при О < j < 2" и г-уровневые компараторы при 2 < I < t суть [2j + l:2j + 2+"] при О < j < 2t-i 2-; всего имеется (t- 1)2" -1-1 компараторов, как в сети четно-нечетного слияния.

Докажите, что если входные числа 2*-упорядочены, как в теореме 5.2.Ш при некотором А; > 1, то обе сети приведут к выходу, который будет 2*"-упорядочен. Таким образом, мы сможем сортировать 2* чисел, пропуская их через любую из сетей t раз. [Когда t велико, такие сети сортировки выполняют примерно вдвое больше сравнений, чем алгоритм 5.2.2М; но общая временная задержка та же, что и на рис. 57, а реализация выполняется проще, поскольку та же самая сеть используется многократно.]

99999999�

54. [.й] Проансшизируйте свойства сетей сортировки, построенных не из 2-элементных сортировщиков, а из т-сортирующих модулей. (Например, Дж. Шапиро (G. Shapiro) построил сеть

для сортировки 16 элементов, использовав четырнадцать 4-элементных сортировщиков. Наилучшее ли это решение? Докажите, что элементов можно рассортировать с помощью не более 16 уровней т-элементных сортировщиков, если т достаточно велико.)

55. [23] Перестановочной сетью называется последовательность модулей [п -.ji]... [iV : jr], где каждый модуль [i-.j] может устанавливаться извне в одно из двух состояний: либо он передает свои входы без изменений, либо меняет местами и Xj (независимо от значений Xi к Xj). Последовательность модулей должна быть такой, чтобы на выходе можно было получить любую перестановку входов при соответствующей установке модулей. Любая сеть сортировки является, очевидно, перестановочной сетью, но обратное неверно. Найдите перестановочную сеть для пяти элементов, имеющую только восемь модулей.

► 56. [25] Предположим, что битовый вектор х € Dn не рассортирован. Покажите, что существует стандартная п-сеть Ох, которая не сможет рассортировать х, хотя она и сортирует другие элементы D„.

57. [М55] Четно-нечетное слияние аналогично четно-четному слиянию Бэтчера, но, если тп > 2, процесс рекурсивно сливает последовательность (im mod 2+ь . ., т-з, am-i}

с (г/1,УЗ,...,У2Гп/21-1) и (X{rn + l)mod2+l,---,Xm-2,Xm) С {У2, У4, , У2[п/2}) ПреЖде, Чем

будет сформировано множество [т/2] -I- [п/2] - 1 сравнений-обменов, аналогичных (1). Покажите, что при четно-нечетном слиянии достигается оптимальное для битонного слияния время задержки [lg(m -I- п)], поскольку не делается сравнений больше, чем в методе битонного слияния. Фактически нужно доказать, что число сравнений А{т,п), выполняемых при четно-нечетном слиянии, удовлетворяет условию C(m,n) < А{т,п) < j(m--п) Ig min(m, n) -I- m 4- n.

УПРАЖНЕНИЯ (часть 2)

Следующие упражнения имеют отношение к различным аспектам оптимизации, касающимся сортировки. Несколько первых упражнений основаны на интересном "многого-ловочном" обобщении метода пузырька, предложенном Ф. Н. Армстронгом (Р. N. Armstrong) и Р. Дж. Нельсоном (R. J. Nelson) еще в 1954 году. [См. U. S. Patents 3029413, 3034102.] П}сть 1 = hi < h2 < < hm = п - возрастающая последовательность целых чисел; будем называть ее последовательностью голов длиной m с диапазоном п. Она будет использоваться при определении методов сортировки специального вида. Сортировка записей Ri ... Rn осуществляется за несколько проходов, а каждый проход состоит из N + п - 1 шагов. На шаге j при j = 1 - п, 2 - п, ..., N - 1 рассматриваются записи Rj..h[l], Rj..ц2], , Ri+h[m] и в случае необходимости переставляются так, чтобы их ключи оказались упорядоченными. (Мы говорим, что Rj.h[ij,..., Rj+h[m] находятся "под головками чтения/записи". Если j + h[k] либо < 1, либо > N, то запись Rj+h[k] не рассматривается. Иначе говоря, ключи Ko,K-i,K-2,... считаются равными -оо, а Kn+1, Kn+2, .. считаются равными --оо. Поэтому при j < -h[m - 1] или j > N - h[2] шаг j становится тривиальным.)

Например, ниже показан один проход сортировки при m = 3, iV = 9 и /ц = 1, /12 = 2, /13 =4.

Если m = 2, /ll = 1 и /i2 = 2, этот "многоголовочный" метод сводится к методу пузырька (алгоритм 5.2.2В).

58. [21] (Джеймс Дугунджи (James Dugundji).) Докажите, что если h[k + l] = h[k] + l при некотором к, I < к < т, то миогоголовочный сортировщик, описанный выше, рассортирует любой входной файл за конечное число проходов. Но если h[k +1] > h[k] + 2 при 1 < к <т, то не исключен вариант, когда входная последовательность никогда не будет упорядочена.

► 59. [30] (Армстронг (Armstrong) и Нельсон (Nelson).) Пусть h[k -I-1] < h[k] + к при 1 < к <ти N >п-1. Докажите, что в течение первого прохода наибольшие п - 1 элементов всегда займут свои окончательные места. [Указание. Используйте принцип нулей и единиц; докажите, что если сортируется последовательность из нулей и единиц, причем единиц меньше п, то все головки могут читать единицы лишь в том случае, когда все нули лежат слева от головок.] Докажите, что если головки удовлетворяют сформулированным условиям, то сортировка будет закончена не более чем за \{N - 1)/(п - 1)] проходов. Существует ли входной файл, для которого необходимо так много проходов?

во. [26] Докажите, что, если п = N, при первом проходе наименьший ключ будет помещен в позицию Ri тогда и только тогда, когда h[k -1-1] < 2h[k] при I < к < т.