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

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

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

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

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

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

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

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

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

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Сортировка для [math] n = 6 [/math]

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

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

См.также

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

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

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