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

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

Сеть называется сортирующей (Sorting network), если в результате её работы любая входная последовательность данных преобразуется в монотонно неубывающую.

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

Компараторы (сравнивающие устройства)

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

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

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

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

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

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

Сети

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

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

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

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

Теорема:

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

См.также

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

0-1 принцип

Сеть Бетчера

Источники

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