Сортирующие сети

Определение:

Сеть называется сортирующей если для любой входной последовательности получающаяся из нее выходная последовательность монотонно возрастает.

Сортирующая сеть с 2 проводами

Компараторы

Определение:

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

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

Определение:

k-компаратором называется устройство упорядочивающие значения на k проводах.

Компаратороы можно располагать в одном слое если они подключены к разным проводам.

Сети

Определение:

Глубиной сети (depth) называется количество слоев в сети.

Определение:

Размером сети (size) называется количество компараторов в сети.

Теорема:

Сеть является сортирующей тогда и только тогда, когда она сортирует все наборы из 0 и 1.

Подробнее в статье 0-1 принцип.

См.также

Сортирующие сети для квадратичных сортировок

0-1 принцип

Сеть Бетчера

Источники

• Кормен Глава 28 Сортирующее сети.
• Wikipedia - Sorting networks