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

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

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

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

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

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

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

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

Заметим, если сжать последовательные сортирующие сети пузырьком и вставками, то результат будет одним и тем же. Этот факт легко заметить, если сопоставлять компараторы на уровне $k$ компараторам на уровне $k - 2$, где ($k$ — уровень между $k - 1$ и $k$ входом). Тем самым получаем картинку сводящуюся к "треугольнику".

Теорема:

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

Доказательство:

$\triangleright$

Докажем данное утверждение по принципу математической индукции. База индукции: При $n = 2$ $( 2\cdot2 - 3 = 1)$, что верно. Шаг индукции: Пусть $S(n) = 2n - 3$ — количество слоев в сети сортировки. При переходе от $n$-й сортирующей сети к $(n + 1)$-й, добавляем дополнительный вход, который содержит $n$ компараторов со своим "соседом", $n - 2$ из которых выполняются одновременно с компараторами из уровня $n - 1$. Заметим, что два $2$ компаратора не участвовали во вкладе в слои. Тогда можно заметить, что $S(n + 1) = S(n) + 2$. Данное рекуррентное соотношение имеет решение $S(n) = 2n - 3$. Что и требовалось доказать.

$\triangleleft$

Сортировка для $n = 6$

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

Теорема:

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

Доказательство:

$\triangleright$

Воспользуемся принципом математической индукции. База индукции: $n = 2$ ($2 - 1 = 1$) Шаг индукции: Пусть $S(n)$ - количество слоев в сети сортировки с $n$ входами. При переходе от $n$-й сортирующей сети к $(n + 1)$-й, добавляем $n - 1$ компаратор, которые являются одним слоем. Тем самым получили рекуррентное соотношение: $S(n + 1) = S(n) + 1$ с начальными данными ($S(2) = 1$). Решением данного рекуррентного соотношения является $S(n) = n - 1$. Что и требовалось доказать

$\triangleleft$

См.также

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

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

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