n = 9 25 модулей, задержка 9

n = 10 29 модулей, задержка 9

n = 12 39 модулей, задержка 9

п = 13 45 модулей, задержка 10

п = 16 60 модулей, задержка 10

Рис. 49. Эффективные сети сортировки.

используется в них только для того, чтобы сохранить множитель logn; метод Бэтчера работает гораздо лучше до тех пор, пока п не выйдет за пределы доступной памяти на всех компьютерах старушки Земли! Но теорема Айтаи, Комлоса и Ше-мереди все-таки правильно устанавливает асимптотический рост §{п) до уровня постоянного множителя.

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

у компараторов, предшествующих данному (рис. 50, (а); в части (Ь) этого рисунка показана та же сеть, перерисованная так, чтобы каждое сравнение выполнялось как можно раньше.)

1231234435

1 2 3

5 6

(а) (Ь)

Рис. 50. Выполнение каждого сравнения как можно раньше по времени.

В описанной выше сети Бэтчера для четно-нечетного слияния затрачивается Тв{т,п) единиц времени, где 2в(т,0) = 2в(0,п) = О, 2в(1)1) = 1, и

Тв{т,п) = И-тах(Тв([т/2], [п/2]), Гв(Гт/2], Гп/21)) при тп > 2.

Используя эти соотношения, можно доказать по индукции, что

Тв{т,п+1) > Тв{т,п);

следовательно, Тв{пп,п) = 1 + Тв{\т/2], \п/2]) для тп > 2; отсюда заключаем, что

Тв{т,п) = 1 + \lgmax{m,n)] при mn > 1.

(12)

Таким образом, как показано в упр. 5, метод сортировки Бэтчера имеет время задержки

/1+Пё"Г

I 2

(13)

Пусть Т{п) - минимальное время задержки, достижимое в любой сети сортировки п элементов. Некоторые из описанных выше сетей можно так улучшить, не используя дополнительных компараторов, чтобы они имели меньшее время задержки, как показано на рис. 51 для п = 6ип = 9, ав упр. 7 - для п = 10. Можно получить еще меньшее время задержки, если добавить один или два дополнительных модуля, как показано на рис. 51 (см. сети для п = 10, 12 и 16). Эти схемы приводят к следующим верхним оценкам для Т{п) при малых значениях п:

п = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 , ,

Т{п) <0133556677889999

Известно, что приведенные здесь значения точны при п < 10 (см. упр. 4). Сети, изображенные на рис. 51, заслуживают тщательного изучения, поскольку вовсе не очевидно, что они годятся для сортировки; эти сети были созданы в 1969-1971 годах Дж. Шапиро (п = 6, 9, 12) и Д. Ван Борисом (п = 10, 16).

Сети слияния. Пусть М{т, п) обозначает минимальное число компараторов, необходимых для сети, которая сливает m элементов Xi < • < х с п элементами Уг < •• < 2/п, образуя рассортированную последовательность zi < < Zm+n- К настоящему времени не создано нй одной сети слияния, которая была бы лучше

п = б 12 модулей, задержка 5

п = 9 25 модулей, задержка 8

п = 10 31 модуль, задержка 7

п=12

40 модулей, задержка 8

п-\6 61 модуль, задержка 9

Рис. 51. Наиболее быстродействующие сети сортировки, предназначенные для параллельных вычислений.

описанной выше сети четно-нечетного слияния; следовательно, функция С{т, rt) и (б) представляет наилучшую известную верхнюю оценку для М{т,п).

Р. У. Флойд обнаружил интересный способ, позволяющий определить нижние оценки в этой задаче слияния.

Теорема F. М{2п, 2п) > 2М(п, п) + п для всех п > 1.

Доказательство. Рассмотрим сеть с М{2п, 2п) модулями компараторов, способную сортировать все входные последовательности {zi,..., .24„), такие, что .zi < < • • • < Z4„ i и Z2 < Zi < • < Zin- Мы можем считать, что каждый модуль заменяет {zi,Zj) элементом {min{zi,Zj),ma,x{zi,zj)) при некоторых г < j (упр. 16). Итак, компараторы можно разделить на три класса:

a) г < 2п и j < 2п;

b) г > 2п и j > 2п;

c) г < 2п и j > 2п.