59
правок
Изменения
Нет описания правки
На один слой будем устанавливать только один компаратор. Все последующие сети получаются простым моделированием соответствующих сортировок.
{| cellpadding="10"
| '''[[Сортировка пузырьком]]''' || '''[[Сортировка вставками]]''' || '''[[Сортировка выбором]]'''
|-
| [[Файл:Bubblesort.png]] || [[Файл:Insertsort.png]] || [[Файл:Choosesort.png]]
Пусть <tex> S(n) = 2n - 3 </tex> — количество слоев в сети сортировки.
При переходе от сортирующей сети с <tex>n</tex> входами к сети с <tex>n + 1</tex> входами, добавляем <tex> n </tex> дополнительных компараторов (<tex>[1:2],[2:3]\dots[n - 1:n]</tex> или <tex>[n - 1:n],[n - 2:n - 1]\dots[1:2]</tex>, т.к. возможны две стратегии добавления). В полученной "треугольной" сети можно заметить, что <tex>n - 1</tex> компаратор входят в уже существующие слои (<tex>[2:3],[3:4]\dots[n - 1:n] </tex> или <tex>[n - 1:n],[n - 2:n - 3]\dots[2:3]</tex>).т.е. на каждом четном слое самым верхним компаратором будет <tex> [2:3] </tex>, а на нечетном <tex>[1:2]</tex>, но тогда один компаратор из предыдущей сортирующий сети и один из добавленных не вносят вклад в количество слоев. Тогда видно, что количество слоев увеличилось на <tex> 2 = S(n + 1) - S(n) </tex>, т.е. наш переход выполняется и наша формула верна. Что и требовалось доказать.
}}
=== Сортировка выбором ===
Сеть для сортировки выбором выглядит иначе. Будем компаратор "вкладывать" в компараторПри переходе к сети с <tex> n + 1 </tex> входами, для получения слоевдобавляется <tex> n </tex> компараторов: <tex> [0:1],[0:2]\dots[0:n] </tex>.
[[Файл:Choosesortparralel2.png]]
Пусть <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> [0,1,0,0] </tex>). Тогда наш переход выполняется и наша формула верна. Что и требовалось доказать.
}}
