Изменения

На один слой будем устанавливать устанавливается несколько компараторов.

Заметим, если сжать последовательные сортирующие сети пузырьком и вставками, то результат будет одним и тем же. Этот факт легко заметить, сдвинув компараторы вправо и влево соответственно и разрешив выполнять одновременные вычисленияЭто видно из симметрии расположения компараторов на картинках выше.  

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

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

Сеть для сортировки выбором выглядит иначе. Будем объединять компаратор "вкладывать" в слой компаратор, для получения слоев.

Пусть <tex> S(n) </tex> - — количество слоев в сети сортировки с <tex> n </tex> входами.

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

*[https://ru.wikipedia.org/wiki/%D0%A1%D0%B5%D1%82%D1%8C_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8 Википедия - — Сети сортировки]