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

Определение

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

Схематическое изображение сортирующей сети для последовательности из 4 чисел. Глубина сети: 4. Размер сети: 5

Процесс сортировки числовой последовательности (3, 2, 4, 1)

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

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

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

Компаратор, подключенный к проводам [math]i, j[/math]. Входные данные: [math]x, y[/math]. Выходные данные: [math]min(x, y), max(x, y)[/math].

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

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

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

Пусть глубина входного провода сети равна нулю. Если глубины входных проводов компаратора равны [math]x[/math] и [math]y[/math], то глубина его выходных проводов равна [math]\max(x, y) + 1 [/math]. Глубина компаратора — величина, равная глубине его выходных проводов.

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

Сети

Введем ряд определений, характеризующих сеть компараторов:

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

Слой сети — множество компараторов, имеющих одинаковую глубину.

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

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

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

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

Для того, чтобы сортирующая сеть для [math]n[/math] входов была корректна, она должна правильно сортировать все [math]n![/math] перестановок [math]n[/math] различных чисел. Также можно сформулировать более сильное утверждение:

Теорема:

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

См.также

• Сортирующие сети для квадратичных сортировок
• 0-1 принцип
• Сеть Бетчера

Источники

• Sorting network — Wikipedia
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 799 — 805. — ISBN 5-8489-0857-4
• Дональд Э. Кнут Искусство программирования. Том 3. Сортировка и поиск — 2-е изд. — М.: «Вильямс», 2012. — с. 238 — 242. — ISBN 0-201-89685-0