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