Изменения

Интересно два факта* Если сжать последовательные сортирующие сети пузырьком и вставками, то результат будет одним и тем же. {{Теорема|statement= В результирующей сети будет <tex>(2n - 3)</tex> слоев.|proof= Докажем данное утверждение по принципу математической индукции.  Базой индукции будет <tex> n = 2 </tex>.  Пусть <tex> S(n) = 2n - 3 </tex> - количество слоев в сети сортировки размера n.  Шаг индукции: При построении <tex>(n + 1)</tex>-й сортирующей сети, выносим сортирующую сеть, содержащую <tex>n</tex> компараторов и добавляем к ней компараторы: <tex>[n + 1; n], [n; n - 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> слоев.}}

==См.также==* [[Сортировочные сети с особыми свойствами]] == Источники информации==*Дональд Э. Кнут. Искусство программирования. Том 3. Сортировка и Поиск. — стр. 238— ISBN 0-201-89685-0*Кормен, Томас Х.,Рональд Л., Штайн, Клифорд. Глава 27. Сортирующие сети // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-e издание. — М.: «Вильямс», 2005. — С. 799 - 822. — ISBN 5-8459-0857-4.*[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 Википедия - Сети сортировки]