47
правок
Изменения
м
Сеть называется '''сортирующейСортирующая сеть''' если для любой входной последовательности получающаяся из нее выходная последовательность монотонно возрастает(англ. ''Sorting network'') — метод сортировки, основанный только на сравнениях данных. Схематически изображается в виде параллельных прямых (проводов), соединенных вертикальными линиями (сравнивающими устройствами). Особенность сети сортировки в том, что сравнения выполняются независимо от предыдущих. Кроме того, сравнения могут выполняться одновременно.
[[Image:Sorting-network-comparator-demonstration..png|thumb|130px|Сортирующая сеть с 2 проводами]]
== Компараторы ==
Обычно компараторы меньшее значение передают на провод с меньшим номером, но бывают и направленные компараторы, у которых указано направление перемещения.
Компаратороы Компараторы можно располагать в одном слое на одной глубине, если они подключены к разным проводам.В этом случае сравнения будут выполняться параллельно.
Кооператор -> компаратор
== Определение ==
{{Определение
|definition =
}}
{| cellpadding="3"
| || [[Файл:Network.png|thumb|right|350px|Схематическое изображение сортирующей сети для последовательности из 4 чисел. Глубина сети: 4. Размер сети: 5 ]] || [[Файл:Sort1.png|thumb|right|400px|Процесс сортировки числовой последовательности (3, 2, 4, 1)]]
|}
== Компараторы (сравнивающие устройства) ==
{{Определение
|definition =
'''Компаратор''' (англ. ''Comparator'') — устройство, подключенное к двум проводам, которое упорядочивает текущие значения на проводах.
}}
{| cellpadding="3"
| [[Файл:Comp1.png|thumb|500px|Компаратор, подключенный к проводам <tex>i, j</tex>. Входные данные: <tex>x, y</tex>. Выходные данные: <tex>\min(x, y), \max(x, y)</tex>.]]
|}
Обычно компараторы меньшее значение передают на провод с меньшим номером, но бывают и направленные компараторы, у которых указано направление перемещения.
{{Определение
|definition ='''КомпараторомK-компаратор''' называется (англ. ''K-comparator'') — устройство подключенное к двум проводам, которое упорядочивает текущие упорядочивающее значения на <tex>k</tex> проводах.
}}
{{Определение
|definition =
Пусть глубина входного провода сети равна нулю. Если глубины входных проводов компаратора равны <tex>x</tex> и <tex>y</tex>, то глубина его выходных проводов равна <tex>\max(x, y) + 1 </tex>. '''k-компараторомГлубина компаратора''' называется устройство упорядочивающие значения на (англ. ''Depth of comparator'k''' проводах) — величина, равная глубине его выходных проводов.
}}
== Сети ==
Введем ряд определений, характеризующих сеть компараторов:
{{Определение
|definition =
'''Глубиной Слой сети ''' (depth)англ. ''layer'' называется количество слоев в сети) — множество компараторов, имеющих одинаковую глубину.
}}
{{Определение
|definition =
'''Размером Глубина сети ''' (sizeангл. ''depth'')— количество слоев в сети.}}{{Определение|definition ='''Размер сети'''(англ. '' называется size'') — количество компараторов в сети.
}}
Для того, чтобы сортирующая сеть для <tex>n</tex> входов была корректна, она должна правильно сортировать все <tex>n!</tex> перестановок <tex>n</tex> различных чисел. Также можно сформулировать более сильное утверждение:
{{Теорема
|statement=
Сеть компараторов с <tex>n</tex> входами является сортирующей тогда и только тогда, когда она сортирует все наборы <tex>2^n</tex> различных последовательностей из 0 и 1.
}}
{{main | 0-1 принцип}}
== См.также ==
*[[Сортирующие сети для квадратичных сортировок]] *[[0-1 принцип]] *[[Сеть Бетчера]]
== Источники информации==* [[wikipedia:Sorting_network | Wikipedia {{---}} Sorting network]]* Томас Х. Кормен Глава 28 Сортирующее сети, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 799 — 805.— ISBN 5-8489-0857-4* [httpДональд Э. Кнут Искусство программирования. Том 3. Сортировка и поиск — 2-е изд. — М.://en«Вильямс», 2012.wikipedia— с. 238 — 242.org/wiki/Sorting_network Wikipedia — ISBN 0-201-89685- Sorting networks]0
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортирующие сети]]
