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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 16: Строка 16:
 
=== Сортировка пузырьком и вставками ===
 
=== Сортировка пузырьком и вставками ===
  
−
Заметим, если сжать последовательные сортирующие сети пузырьком и вставками, то результат будет одним и тем же. Этот факт легко заметить, если сопоставлять компараторы на уровне <tex> k </tex> компараторам на уровне <tex> k - 2</tex>, где (<tex> k </tex> — уровень между <tex> k - 1 </tex> и <tex> k </tex> входом). Тем самым получаем картинку сводящуюся к "треугольнику".
+
Заметим, если сжать последовательные сортирующие сети пузырьком и вставками, то результат будет одним и тем же. Этот факт легко заметить, сдвинув компараторы вправо и влево соответственно.
  
 
{{
 
{{
Строка 27: Строка 27:
 
'''База индукции''':
 
'''База индукции''':
  
−
При <tex> n = 2 </tex>   <tex> ( 2\cdot2 - 3 = 1) </tex>, что верно.  
+
При <tex> n = 2 </tex>. В сети всего два входа, на которых располагается один компаратор, тем самым наше предположение выполняется.  
  
 
'''Шаг индукции''':  
 
'''Шаг индукции''':  
Строка 33: Строка 33:
 
Пусть <tex> S(n) = 2n - 3 </tex> — количество слоев в сети сортировки.
 
Пусть <tex> S(n) = 2n - 3 </tex> — количество слоев в сети сортировки.
  
−
При переходе от <tex>n</tex> - й сортирующей сети к <tex>(n + 1)</tex> - й, добавляем дополнительный вход, который содержит <tex> n </tex> компараторов со своим "соседом", <tex> n - 2 </tex> из которых выполняются одновременно с компараторами из уровня <tex> n - 1 </tex>. Заметим, что два <tex> 2 </tex> компаратора не участвовали во вкладе в слои. Тогда можно заметить, что <tex> S(n + 1) = S(n) + 2 </tex>.  
+
При переходе от <tex>n</tex> - й сортирующей сети к <tex>(n + 1)</tex> - й, добавляем <tex> n </tex> дополнительных компараторов. При "треугольной" сети можно заметить, что <tex>n - 1</tex> входят в уже существующие слои, но тогда один компаратор из предыдущей сортирующий сети и один из добавленных не вносят вклад в количество слоев. Тогда можно получить рекуррентное соотношение: <tex> S(n + 1) = S(n) + 2 </tex>.
 
Данное рекуррентное соотношение имеет решение <tex> S(n) = 2n - 3 </tex>. Что и требовалось доказать.
 
Данное рекуррентное соотношение имеет решение <tex> S(n) = 2n - 3 </tex>. Что и требовалось доказать.
  
Строка 43: Строка 43:
  
 
=== Сортировка выбором ===
 
=== Сортировка выбором ===
 +
Будем объединять в слой
 
{{
 
{{
 
Теорема
 
Теорема
 
|statement=
 
|statement=
−
В результирующей сети будет <tex>n - 1</tex> слой, где <tex> n </tex> — количество входов.
+
В результирующей сети будет <tex>2n - 3</tex> слой, где <tex> n </tex> — количество входов.
 
|proof=  
 
|proof=  
 
Воспользуемся принципом математической индукции.
 
Воспользуемся принципом математической индукции.
Строка 52: Строка 53:
 
'''База индукции''':
 
'''База индукции''':
  
−
<tex> n = 2 </tex> (<tex> 2 - 1 = 1 </tex>)
+
<tex> n = 2 </tex>. В сети всего два входа, на которых располагается один компаратор, тем самым наше предположение выполняется.
  
 
'''Шаг индукции''':
 
'''Шаг индукции''':
Строка 58: Строка 59:
 
Пусть <tex> S(n) </tex> - количество слоев в сети сортировки с <tex> n </tex> входами.
 
Пусть <tex> S(n) </tex> - количество слоев в сети сортировки с <tex> n </tex> входами.
  
−
При переходе от <tex>n</tex> - й сортирующей сети к <tex>(n + 1)</tex>-й, добавляем <tex> n - 1 </tex> компаратор, которые являются одним слоем. Тем самым получили рекуррентное соотношение:
+
При переходе от <tex>n</tex> - й сортирующей сети к <tex>(n + 1)</tex>-й, добавляем <tex> n </tex> компаратор. Заметим, что с <tex> n - 2 </tex> можно сделать слои, используя слои из предыдущей сортирующей сети. Тогда остается два компаратора, которые сами являются слоями. Тем самым получили рекуррентное соотношение:
−
<tex> S(n + 1) = S(n) + 1 </tex> с начальными данными (<tex>S(2) = 1</tex>). Решением данного рекуррентного соотношения является <tex> S(n) = n - 1 </tex>. Что и требовалось доказать  
+
<tex> S(n + 1) = S(n) + 2 </tex> с начальными данными (<tex>S(2) = 1</tex>). Решением данного рекуррентного соотношения является <tex> S(n) = 2n - 3 </tex>. Что и требовалось доказать  
  
 
}}
 
}}
  
 +
[[Файл:Choosesortparralel.png‎]]
 
==См.также==
 
==См.также==
 
* [[Сортировочные сети с особыми свойствами]]
 
* [[Сортировочные сети с особыми свойствами]]

Версия 11:08, 20 мая 2015

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

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

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

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

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

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

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

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

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

Докажем данное утверждение по принципу математической индукции.

База индукции:

При [math] n = 2 [/math]. В сети всего два входа, на которых располагается один компаратор, тем самым наше предположение выполняется.

Шаг индукции:

Пусть [math] S(n) = 2n - 3 [/math] — количество слоев в сети сортировки.

При переходе от [math]n[/math] - й сортирующей сети к [math](n + 1)[/math] - й, добавляем [math] n [/math] дополнительных компараторов. При "треугольной" сети можно заметить, что [math]n - 1[/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]2n - 3[/math] слой, где [math] n [/math] — количество входов.
Доказательство:
[math]\triangleright[/math]

Воспользуемся принципом математической индукции.

База индукции:

[math] n = 2 [/math]. В сети всего два входа, на которых располагается один компаратор, тем самым наше предположение выполняется.

Шаг индукции:

Пусть [math] S(n) [/math] - количество слоев в сети сортировки с [math] n [/math] входами.

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

[math] S(n + 1) = S(n) + 2 [/math] с начальными данными ([math]S(2) = 1[/math]). Решением данного рекуррентного соотношения является [math] S(n) = 2n - 3 [/math]. Что и требовалось доказать
[math]\triangleleft[/math]

Choosesortparralel.png

См.также

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

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