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

Определение

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

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

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

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

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

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

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

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

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

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

Сравнивающие сети

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

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

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

Глубина сети (depth) — количество слоев в сети.

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

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

Теорема:

Сеть компараторов с [math]n[/math] входами является сортирующей тогда и только тогда, когда она сортирует [math]2^n[/math] различных последовательностей из 0 и 1.

См.также

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

0-1 принцип

Сеть Бетчера

Источники

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