=== Сортировка пузырьком и вставками ===
* Если Заметим, если сжать последовательные сортирующие сети пузырьком и вставками, то результат будет одним и тем же. Этот факт легко заметить, если сопоставлять компараторы на уровне <tex> k </tex> компараторам на уровне <tex> k - 2</tex>, где (<tex> k </tex> — уровень между <tex> k - 1 </tex> и <tex> k </tex> входом). Тем самым получаем картинку сводящуюся к "треугольнику".
{{
Теорема
|statement=
В результирующей сети будет <tex>(2n - 3)</tex> слоев, где <tex>n</tex> - количество входов.
|proof=
Докажем данное утверждение по принципу математической индукции.
Базой '''База индукции будет <tex> n = 2 </tex>. ''':
Пусть При <tex> S(n) = 2n 2 </tex> <tex> ( 2\cdot2 - 3 = 1) </tex> - количество слоев в сети сортировки размера n, что верно.
'''Шаг индукции''':
Пусть <tex> S(n) = 2n - 3 </tex> — количество слоев в сети сортировки. При построении переходе от <tex>n</tex>-й сортирующей сети к <tex>(n + 1)</tex>-й сортирующей сети, выносим сортирующую сетьдобавляем дополнительный вход, содержащую который содержит <tex>n</tex> компараторов и добавляем к ней компараторы: со своим "соседом", <tex> n - 2 </tex> из которых выполняются одновременно с компараторами из уровня <tex> n - 1 </tex>. Заметим, что два <tex> 2 </tex> компаратора не участвовали во вкладе в слои. Тогда можно заметить, что <tex>[S(n + 1; ) = S(n], [n; ) + 2 </tex>. Данное рекуррентное соотношение имеет решение <tex> S(n ) = 2n - 1]\dots[3; 2], [2; 1] </tex>. Что и требовалось доказать.
Подсчитаем количество компараторов: <tex> S(n + 1) = n + n - 1 = 2n - 1 </tex> , заметим, что данное количество слоев удовлетворяет нашему шагу индукции <tex>(S(n + 1) = 2(n + 1) - 3 = 2n + 2 - 3 = 2n - 1)</tex>
}}
Сортировка для <tex> n = 6 </tex>
[[Файл:Parralelsort.png]]
Теорема
|statement=
В результирующей сети будет <tex>\dfrac{n(n - 1)}{2}</tex> компараторовслой, где <tex> n </tex> — количество входов.
|proof=
Воспользуемся принципом математической индукции.
Базой '''База индукции будет ''': <tex> n = 2 </tex> (<tex> 2 - 1 = 1 </tex>)
'''Шаг индукции''':
Рассмотрим метод построения сетей для сортировок выборомПусть <tex> S(n) </tex> - количество слоев в сети сортировки с <tex> n </tex> входами.
Пусть При переходе от <tex> S(n) </tex> - количество компараторов в й сортирующей сети сортировки с к <tex> (n + 1)</tex> входами-й, тогда для получения добавляем <tex>(n + - 1)</tex>-й сети сортировки надо к предыдущей добавить компараторыкомпаратор, которые являются одним слоем. Тем самым получили рекуррентное соотношение: <tex>[S(n + 1; 1], [) = S(n; ) + 1]\dots[3; </tex> с начальными данными (<tex>S(2) = 1], [2; </tex>). Решением данного рекуррентного соотношения является <tex> S(n) = n - 1] </tex>. Что и требовалось доказать
Подсчитаем общее количество компараторов: <tex>S(n + 1) = \dfrac{n(n - 1)}{2} + n = \dfrac{n(n + 1)}{2} </tex>, заметим, что данное количество компараторов удовлетворяет нашему шагу индукции.
}}
[[Файл:Choosesortparralel.png]]
==См.также==
