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

Материал из Викиконспекты
Перейти к: навигация, поиск

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

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

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

Сортировка пузырьком Сортировка вставками Сортировка выбором
Bubblesort.png Insertsort.png Choosesort.png

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

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

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

Заметим, если сжать последовательные сортирующие сети пузырьком и вставками, то результат будет одним и тем же. Этот факт легко заметить, если сопоставлять компараторы на уровне [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] Parralelsort.png

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

Теорема:
В результирующей сети будет [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.
  • Википедия - Сети сортировки