113
правок
Изменения
Нет описания правки
== Определение ==
'''Сортирующая сеть (Sorting network)''' — модель, состоящая из нескольких проводов и сравнивающих устройств, предназначенная для сортировки данных. Схематически изображается в виде параллельных прямых (проводов), соединенных вертикальными линиями (сравнивающими устройствами). Особенность сети в том, что сравнения выполняются независимо от предыдущих. Кроме того, сравнения могут выполняться одновременно.
{| cellpadding="3"
| || [[Файл:Network.png|thumb|right|350px|Схематическое изображение сортирующей сети для последовательности из 4 чисел. Глубина сети: 4. Размер сети: 5 ]] || [[Файл:Sort1.png|thumb|right|400px|Процесс сортировки числовой последовательности (3, 2, 4, 1)]]
Обычно компараторы меньшее значение передают на провод с меньшим номером, но бывают и направленные компараторы, у которых указано направление перемещения.
'''K-компаратор''' — устройство, упорядочивающее значения на '''k''' проводах.
{{Определение
== Сети ==
Введем ряд определений, характеризующих сеть компараторов:
{{Определение
|definition =
'''Размер сети (size)''' — количество компараторов в сети.
}}
Для того, чтобы сортирующая сеть для <tex>n</tex> входов была корректна, она должна правильно сортировать все <tex>n!</tex> перестановок <tex>n</tex> различных чисел. Также можно сформулировать более сильное утверждение:
{{Теорема
