Изменения

Сеть называется '''сортирующейСортирующая сеть''' если она сортирует все наборы из 0 и 1(англ. ''Sorting network'') — метод сортировки, основанный только на сравнениях данных. Схематически изображается в виде параллельных прямых (проводов), соединенных вертикальными линиями (сравнивающими устройствами). Особенность сети сортировки в том, что сравнения выполняются независимо от предыдущих. Кроме того, сравнения могут выполняться одновременно.

{| cellpadding=== Компараторы ==="3"| || [[Файл:Network.png|thumb|right|350px|Схематическое изображение сортирующей сети для последовательности из 4 чисел. Глубина сети: 4. Размер сети: 5 ]] || [[Файл:Sort1.png|thumb|right|400px|Процесс сортировки числовой последовательности (3, 2, 4, 1)]]|}

'''КомпараторомКомпаратор''' называется (англ. ''Comparator'') — устройство , подключенное к двум проводам, которое упорядочивает текущие значения на проводах.

Компараторы бывают:* '''Прямыми''' - когда Обычно компараторы меньшее значение идет передают на провод с меньшим номером.* '''Обратными''' - когда меньшее значение идет на провод с большим номером, но бывают и направленные компараторы, у которых указано направление перемещения.

Компаратором можно располагать в одном слое если они подключены к разным проводам{{Определение|definition = '''K-компаратор''' (англ.''K-comparator'') — устройство, упорядочивающее значения на <tex>k</tex> проводах.}}

Пусть глубина входного провода сети равна нулю. Если глубины входных проводов компаратора равны <tex>x</tex> и <tex>y</tex>, то глубина его выходных проводов равна <tex>\max(x, y) + 1 </tex>. '''k-компараторомГлубина компаратора''' называется устройство упорядочивающая значения на (англ. ''Depth of comparator'k''' проводах) — величина, равная глубине его выходных проводов.

Компараторы можно располагать на одной глубине, если они подключены к разным проводам. В этом случае сравнения будут выполняться параллельно. === Характеристики сети =Сети ==

'''Глубиной Размер сети''' называется (англ. ''size'') — количество слоев компараторов в сети.}} Для того, чтобы сортирующая сеть для <tex>n</tex> входов была корректна, она должна правильно сортировать все <tex>n!</tex> перестановок <tex>n</tex> различных чисел. Также можно сформулировать более сильное утверждение: {{Теорема|statement=Сеть компараторов с <tex>n</tex> входами является сортирующей тогда и только тогда, когда она сортирует <tex>2^n</tex> различных последовательностей из 0 и 1.