Изменения

Заметим, если сжать последовательные сортирующие сети пузырьком и вставками, то результат будет одним и тем же. Этот факт легко заметить, если сопоставлять сдвинув компараторы на уровне <tex> k </tex> компараторам на уровне <tex> k - 2</tex>, где (<tex> k </tex> — уровень между <tex> k - 1 </tex> вправо и <tex> k </tex> входом). Тем самым получаем картинку сводящуюся к "треугольнику"влево соответственно.

При <tex> n = 2 </tex> <tex> ( 2\cdot2 - 3 = 1) </tex>. В сети всего два входа, что вернона которых располагается один компаратор, тем самым наше предположение выполняется.

При переходе от <tex>n</tex> - й сортирующей сети к <tex>(n + 1)</tex> - й, добавляем дополнительный вход, который содержит <tex> n </tex> дополнительных компараторов со своим . При "соседомтреугольной"сети можно заметить, что <tex> n - 2 1</tex> входят в уже существующие слои, но тогда один компаратор из которых выполняются одновременно с компараторами предыдущей сортирующий сети и один из уровня <tex> n - 1 </tex>. Заметим, что два <tex> 2 </tex> компаратора добавленных не участвовали во вкладе вносят вклад в слоиколичество слоев. Тогда можно заметить, что получить рекуррентное соотношение: <tex> S(n + 1) = S(n) + 2 </tex>.

В результирующей сети будет <tex>n 2n - 13</tex> слой, где <tex> n </tex> — количество входов.

<tex> n = 2 </tex> (<tex> 2 - 1 = 1 </tex>) . В сети всего два входа, на которых располагается один компаратор, тем самым наше предположение выполняется.

При переходе от <tex>n</tex> - й сортирующей сети к <tex>(n + 1)</tex>-й, добавляем <tex> n </tex> компаратор. Заметим, что с <tex> n - 1 2 </tex> компараторможно сделать слои, используя слои из предыдущей сортирующей сети. Тогда остается два компаратора, которые сами являются одним слоемслоями. Тем самым получили рекуррентное соотношение:<tex> S(n + 1) = S(n) + 1 2 </tex> с начальными данными (<tex>S(2) = 1</tex>). Решением данного рекуррентного соотношения является <tex> S(n) = n 2n - 1 3 </tex>. Что и требовалось доказать