Изменения

При переходе от сортирующей сети с <tex>n</tex> входами к сети с <tex>n + 1</tex> входами, добавляем <tex> n </tex> дополнительных компараторов (<tex>[1:2],[2:3]\dots[n - 1:n+ 1]</tex> или <tex>[n - + 1:n],[n - 2:n - + 1]\dots[1:2]</tex>, т.к. возможны две стратегии добавления; отсюда, кстати, тоже видна эквивалентность схем для обоих сортировок). В полученной Будем также поддерживать сортирующую сеть в виде "треугольной" сети . Таким образом компараторы <tex>[i:i+1],\ i \geqslant 3</tex> можно заметить, что расположить в существующих слоях над самым верхним компаратором в соответствующем слое. То есть в сети с <tex>n - 1</tex> компаратор входят в уже существующие слои (входами был слой с единственным компаратором <tex>[1:2:3]</tex>,поэтому над ним можно разместить компаратор <tex>[3:4]\dots</tex>, на <tex>[n 2:3]</tex> {{--- 1}} <tex>[4:n5] </tex> или . Затем на следующем слое будет уже два компаратора: <tex>[n - 13 :n4],</tex> над <tex>[n - 1:2:n - 3]\dots</tex>, поэтому сверху можно добавить <tex> [25:36]</tex>).т.е. В общем виде, на каждом четном слое самым верхним компаратором с номером <tex> k \geqslant 0 </tex> с конца (до середины треугольника), будет <tex>\left\lfloor\dfrac{k}{2}\right\rfloor + 1</tex> компараторов, последним из которых является <tex> [k + 1 : k + 2]</tex>, следовательно, на этот слой можно добавить компаратор <tex>[k + 3 :3k + 4] </tex>. Значит, а на нечетном новые слои создадутся лишь благодаря компаратором <tex>[1:2]</tex> и <tex>[2:3]</tex>, но тогда один компаратор из предыдущей сортирующий поэтому число слоёв в новой сети и один из добавленных не вносят вклад в количество слоев. Тогда видно, что количество слоев увеличилось на составит <tex> 2 = S(n + 1) = 2n - 3 + 1 = 2n - S1 = 2(n+ 1) - 3</tex>, т.е. наш переход выполняется и наша формула верна. Что и требовалось доказатьчто удовлетворяет нашему соотношению.

Сеть для [[Сортировка выбором | сортировки выбором ]] выглядит иначе. При переходе к сети с <tex> n + 1 </tex> входами, добавляется <tex> n </tex> компараторов: <tex> [0:1],[0:2]\dots[0: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> [0,1,0,0] </tex>).

Тогда наш переход выполняется и наша формула верна. Что и требовалось доказать.

Пример правильной и ошибочной сети для <tex> n = 4 </tex> . Если перенести свободные компараторы и слить их в один слой, то можно уменьшить количество слоев, но при этом сеть перестает быть сортирующей (при <tex> n = 4 </tex> ошибка будет возникать на последовательности <tex> [0,1,0,0] </tex>).