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

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

Сортирующие сети с последовательной сортировкой

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

Сортировка пузырьком	Сортировка вставками	Сортировка выбором

Сортирующие сети с параллельной сортировкой

На один слой устанавливается несколько компараторов.

Сортировка пузырьком и вставками

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

Утверждение:

В результирующей сети будет $(2n - 3)$ слоев, где $n$ — количество входов.

$\triangleright$

Докажем данное утверждение по принципу математической индукции. База индукции: При $n = 2$. В сети всего два входа, на которых располагается один компаратор, тем самым наше предположение выполняется. Шаг индукции: Пусть $S(n) = 2n - 3$ — количество слоев в сети сортировки. При переходе от сортирующей сети с $n$ входами к сети с $n + 1$ входами, добавляем $n$ дополнительных компараторов ($[1:2],[2:3]\dots[n:n + 1]$ или $[n + 1:n],[n:n + 1]\dots[1:2]$, т.к. возможны две стратегии добавления; отсюда, кстати, тоже видна эквивалентность схем для обоих сортировок). Будем также поддерживать сортирующую сеть в виде "треугольной" сети. Таким образом компараторы $[i:i+1],\ i \geqslant 3$ можно расположить в существующих слоях над самым верхним компаратором в соответствующем слое. То есть в сети с $n$ входами был слой с единственным компаратором $[1:2]$, поэтому над ним можно разместить компаратор $[3 : 4]$, на $[2:3]$ — $[4:5]$. Затем на следующем слое будет уже два компаратора: $[3 : 4]$ над $[1:2]$, поэтому сверху можно добавить $[5: 6]$. В общем виде, на слое с номером $k \geqslant 0$ с конца (до середины треугольника), будет $\left\lfloor\dfrac{k}{2}\right\rfloor + 1$ компараторов, последним из которых является $[k + 1 : k + 2]$, следовательно, на этот слой можно добавить компаратор $[k + 3 : k + 4]$. Значит, новые слои создадутся лишь благодаря компаратором $[1:2]$ и $[2:3]$, поэтому число слоёв в новой сети составит $S(n+1) = 2n - 3 + 1 = 2n - 1 = 2(n + 1) - 3$, что удовлетворяет нашему соотношению.

$\triangleleft$

Сортирующая сеть для $n = 6$:

Сортировка выбором

Сеть для сортировки выбором выглядит иначе. При переходе к сети с $n + 1$ входами, добавляется $n$ компараторов: $[0:1],[0:2]\dots[0:n]$, .

Утверждение:

В результирующей сети будет $2n - 3$ слоев, где $n$ — количество входов.

$\triangleright$

Определим операцию вложения компаратора $[i:j]$ в компаратор $[t:s]$ : разместим компаратор $[i:j]$ и $[t:s]$ на одном слое, так, что $t \lt i \lt j \lt s$. Теперь воспользуемся принципом математической индукции. База индукции: $n = 2$. В сети всего два входа, на которых располагается один компаратор, тем самым наше предположение выполняется. Шаг индукции: Пусть $S(n)$ — количество слоев в сети сортировки с $n$ входами. При переходе от сортирующей сети с $n$ входами к сети с $n + 1$ входами, добавляем $n$ компараторов $\left( [0:1] \dots [0:n]\right)$. Заметим, что в $n - 2$ добавленных компаратора можно вложить $n - 2$ компараторов из предыдущей сети, так, вкладывая один компаратор в другой, образуется новый слой, т.е. количество слоев не изменяется. Тогда останется два компаратора: $[0:1], [0:2]$ в которые ничего нельзя вложить, т.е. количество слоев изменяется на $2 = S(n + 1) - S(n)$. Тогда наш переход выполняется и формула верна. Что и требовалось доказать.

$\triangleleft$

Пример правильной и ошибочной сети для $n = 4$. Если перенести свободные компараторы и слить их в один слой, то можно уменьшить количество слоев, но при этом сеть перестает быть сортирующей (при $n = 4$ ошибка будет возникать на последовательности $[0,1,0,0]$).

См.также

• Сортировочные сети с особыми свойствами

Источники информации

• Дональд Э. Кнут. Искусство программирования. Том 3. Сортировка и Поиск. стр. 238— ISBN 0-201-89685-0
• Кормен, Томас Х.,Рональд Л., Штайн, Клифорд. Глава 27. Сортирующие сети // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-e издание. — М.: «Вильямс», 2005. — С. 799 - 822. — ISBN 5-8459-0857-4.
• Википедия — Сети сортировки