3622
правки
Изменения
м
ТеоремаУтверждение
Сортировка Сортирующая сеть для <tex> n = 6 </tex> :
ТеоремаУтверждение
Воспользуемся Определим операцию вложения компаратора <tex> [i:j] </tex> в компаратор <tex> [t:s] </tex> : разместим компаратор <tex> [i:j] </tex> и <tex> [t:s] </tex> на одном слое, так, что <tex> t < i < j < s </tex>. Теперь воспользуемся принципом математической индукции.
→Сортировка выбором
На один слой будем устанавливать только один компаратор. Все последующие сети получаются простым моделированием соответствующих сортировок.
{| cellpadding="10"
| '''[[Сортировка пузырьком]]''' || '''[[Сортировка вставками]]''' || '''[[Сортировка выбором]]'''
|-
| [[Файл:Bubblesort.png]] || [[Файл:Insertsort.png]] || [[Файл:Choosesort.png]]
== Сортирующие сети с параллельной сортировкой ==
На один слой будем устанавливать устанавливается несколько компараторов.
=== Сортировка пузырьком и вставками ===
Заметим, что если сжать последовательные сортирующие сети пузырьком и вставками, то результат будет одним и тем же. Этот факт легко заметить, если сопоставлять компараторы на уровне <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> ( 2\cdot2 - 3 = 1) </tex>. В сети всего два входа, что вернона которых располагается один компаратор, тем самым наше предположение выполняется.
'''Шаг индукции''':
Пусть <tex> S(n) = 2n - 3 </tex> — количество слоев в сети сортировки.
При переходе от сортирующей сети с <tex>n</tex>-й сортирующей входами к сети к с <tex>(n + 1)</tex>-йвходами, добавляем дополнительный вход<tex> n </tex> дополнительных компараторов (<tex>[1:2], который содержит [2:3]\dots[n:n + 1]</tex> или <tex> [n + 1:n],[n:n + 1]\dots[1:2]</tex> компараторов со своим , т.к. возможны две стратегии добавления; отсюда, кстати, тоже видна эквивалентность схем для обоих сортировок). Будем также поддерживать сортирующую сеть в виде "соседомтреугольной"сети. Таким образом компараторы <tex>[i:i+1], \ i \geqslant 3</tex> можно расположить в существующих слоях над самым верхним компаратором в соответствующем слое. То есть в сети с <tex> n - </tex> входами был слой с единственным компаратором <tex>[1:2 ]</tex>, поэтому над ним можно разместить компаратор <tex>[3 : 4]</tex> из которых выполняются одновременно с компараторами из уровня , на <tex>[2:3]</tex> n {{--- 1 }} <tex>[4:5]</tex>. Заметим, что Затем на следующем слое будет уже два компаратора: <tex>[3 : 4]</tex> над <tex> [1:2 ]</tex>, поэтому сверху можно добавить <tex> [5: 6]</tex> компаратора не участвовали во вкладе в слои. Тогда можно заметитьВ общем виде, что на слое с номером <tex> k \geqslant 0 </tex> Sс конца (n до середины треугольника), будет <tex>\left\lfloor\dfrac{k}{2}\right\rfloor + 1</tex> компараторов, последним из которых является <tex>[k + 1) = S(n) : k + 2 ]</tex>, следовательно, на этот слой можно добавить компаратор <tex>[k + 3 : k + 4]</tex>. Данное рекуррентное соотношение имеет решение Значит, новые слои создадутся лишь благодаря компаратором <tex>[1:2]</tex> и <tex>[2:3]</tex>, поэтому число слоёв в новой сети составит <tex> S(n+1) = 2n - 3 + 1 = 2n - 1 = 2(n + 1) - 3 </tex>. Что и требовалось доказать, что удовлетворяет нашему соотношению.
}}
[[Файл:Parralelsort.png]]
=== Сортировка выбором ===
Сеть для [[Сортировка выбором | сортировки выбором]] выглядит иначе. При переходе к сети с <tex> n + 1 </tex> входами, добавляется <tex> n </tex> компараторов: <tex> [0:1],[0:2]\dots[0:n] </tex>, .
[[Файл:Choosesortparralel2.png]]
{{
|statement=
В результирующей сети будет <tex>n 2n - 13</tex> слойслоев, где <tex> n </tex> — количество входов.
|proof=
'''База индукции''':
<tex> n = 2 </tex> (<tex> 2 - 1 = 1 </tex>) . В сети всего два входа, на которых располагается один компаратор, тем самым наше предположение выполняется.
'''Шаг индукции''':
Пусть <tex> S(n) </tex> - — количество слоев в сети сортировки с <tex> n </tex> входами.
При переходе от сортирующей сети с <tex>n</tex>-й сортирующей входами к сети к с <tex>(n + 1)</tex>-йвходами, добавляем <tex> n - 1 </tex> компаратор, которые являются одним слоем. Тем самым получили рекуррентное соотношение:компараторов <tex> S\left([0:1] \dots [0:n + 1]\right) = S(</tex>. Заметим, что в <tex> n) + 1 - 2 </tex> с начальными данными (добавленных компаратора можно вложить <tex>S(n - 2) = </tex> компараторов из предыдущей сети, так, вкладывая один компаратор в другой, образуется новый слой, т.е. количество слоев не изменяется. Тогда останется два компаратора: <tex>[0:1], [0:2] </tex>)в которые ничего нельзя вложить, т.е. Решением данного рекуррентного соотношения является количество слоев изменяется на <tex> 2 = S(n+ 1) = - S(n - 1 ) </tex>. Тогда наш переход выполняется и формула верна. Что и требовалось доказать .
}}
Пример правильной и ошибочной сети для <tex> n = 4 </tex>. Если перенести свободные компараторы и слить их в один слой, то можно уменьшить количество слоев, но при этом сеть перестает быть сортирующей (при <tex> n = 4 </tex> ошибка будет возникать на последовательности <tex> [0,1,0,0] </tex>).
[[Файл:MyRis.jpg]]
==См.также==
*Дональд Э. Кнут. Искусство программирования. Том 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 Википедия - — Сети сортировки]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортирующие сети]]
