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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 18 промежуточных версий 3 участников)
Строка 5: Строка 5:
 
На один слой будем устанавливать только один компаратор. Все последующие сети получаются простым моделированием соответствующих сортировок.
 
На один слой будем устанавливать только один компаратор. Все последующие сети получаются простым моделированием соответствующих сортировок.
 
{| cellpadding="10"
 
{| cellpadding="10"
| '''[[Сортировка пузырьком]]''' || '''[[Сортировка вставками]]''' || '''Сортировка выбором'''
+
| '''[[Сортировка пузырьком]]''' || '''[[Сортировка вставками]]''' || '''[[Сортировка выбором]]'''
 
|-
 
|-
 
| [[Файл:Bubblesort.png]] || [[Файл:Insertsort.png]] || [[Файл:Choosesort.png‎]]
 
| [[Файл:Bubblesort.png]] || [[Файл:Insertsort.png]] || [[Файл:Choosesort.png‎]]
Строка 12: Строка 12:
 
== Сортирующие сети с параллельной сортировкой ==
 
== Сортирующие сети с параллельной сортировкой ==
  
На один слой будем устанавливать несколько компараторов.
+
На один слой устанавливается несколько компараторов.
  
 
=== Сортировка пузырьком и вставками ===
 
=== Сортировка пузырьком и вставками ===
  
Заметим, если сжать последовательные сортирующие сети пузырьком и вставками, то результат будет одним и тем же. Этот факт легко заметить, если сопоставлять компараторы на уровне <tex> k </tex> компараторам на уровне <tex> k - 2</tex>, где (<tex> k </tex> — уровень между <tex> k - 1 </tex> и <tex> k </tex> входом). Тем самым получаем картинку сводящуюся к "треугольнику".
+
Заметим, что если сжать последовательные сортирующие сети пузырьком и вставками, то результат будет одним и тем же. Это видно из симметрии расположения компараторов на картинках выше.
 
 
 
{{
 
{{
Теорема
+
Утверждение
 
|statement=
 
|statement=
  В результирующей сети будет <tex>(2n - 3)</tex> слоев, где <tex>n</tex> - количество входов.
+
  В результирующей сети будет <tex>(2n - 3)</tex> слоев, где <tex>n</tex> количество входов.
 
|proof=  
 
|proof=  
 
Докажем данное утверждение по принципу математической индукции.  
 
Докажем данное утверждение по принципу математической индукции.  
Строка 27: Строка 26:
 
'''База индукции''':
 
'''База индукции''':
  
При <tex> n = 2 </tex>   <tex> ( 2\cdot2 - 3 = 1) </tex>, что верно.  
+
При <tex> n = 2 </tex>. В сети всего два входа, на которых располагается один компаратор, тем самым наше предположение выполняется.  
  
 
'''Шаг индукции''':  
 
'''Шаг индукции''':  
Строка 33: Строка 32:
 
Пусть <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>[1:2],[2:3]\dots[n:n + 1]</tex> или <tex>[n + 1:n],[n:n + 1]\dots[1:2]</tex>, т.к. возможны две стратегии добавления; отсюда, кстати, тоже видна эквивалентность схем для обоих сортировок). Будем также поддерживать сортирующую сеть в виде "треугольной" сети. Таким образом компараторы <tex>[i:i+1],\ i \geqslant 3</tex> можно расположить в существующих слоях над самым верхним компаратором в соответствующем слое. То есть в сети с <tex> n </tex> входами был слой с единственным компаратором <tex>[1:2]</tex>, поэтому над ним можно разместить компаратор <tex>[3 : 4]</tex>, на <tex>[2:3]</tex> {{---}} <tex>[4:5]</tex>. Затем на следующем слое будет уже два компаратора: <tex>[3 : 4]</tex> над <tex>[1:2]</tex>, поэтому сверху можно добавить <tex> [5: 6]</tex>. В общем виде, на слое с номером <tex> k \geqslant 0 </tex> с конца (до середины треугольника), будет <tex>\left\lfloor\dfrac{k}{2}\right\rfloor + 1</tex> компараторов, последним из которых является <tex>[k + 1 : k + 2]</tex>, следовательно, на этот слой можно добавить компаратор
Данное рекуррентное соотношение имеет решение <tex> S(n) = 2n - 3 </tex>. Что и требовалось доказать.
+
<tex>[k + 3 : k + 4]</tex>.
 +
 
 +
Значит, новые слои создадутся лишь благодаря компаратором <tex>[1:2]</tex> и <tex>[2:3]</tex>, поэтому число слоёв в новой сети составит <tex>S(n+1) = 2n - 3 + 1 = 2n - 1 = 2(n + 1) - 3</tex>, что удовлетворяет нашему соотношению.
  
 
}}
 
}}
Строка 43: Строка 44:
  
 
=== Сортировка выбором ===
 
=== Сортировка выбором ===
 +
 +
Сеть для [[Сортировка выбором | сортировки выбором]] выглядит иначе. При переходе к сети с <tex> n + 1 </tex> входами, добавляется <tex> n </tex> компараторов: <tex> [0:1],[0:2]\dots[0:n] </tex>, .
 +
 +
[[Файл:Choosesortparralel2.png‎]]
 +
 
{{
 
{{
Теорема
+
Утверждение
 
|statement=
 
|statement=
В результирующей сети будет <tex>n - 1</tex> слой, где <tex> n </tex> — количество входов.
+
В результирующей сети будет <tex>2n - 3</tex> слоев, где <tex> n </tex> — количество входов.
 
|proof=  
 
|proof=  
Воспользуемся принципом математической индукции.
+
Определим операцию вложения компаратора <tex> [i:j] </tex> в компаратор <tex> [t:s] </tex> : разместим компаратор  <tex> [i:j] </tex> и <tex> [t:s] </tex> на одном слое, так, что <tex> t < i < j < s </tex>.
 +
 
 +
Теперь воспользуемся принципом математической индукции.
  
 
'''База индукции''':
 
'''База индукции''':
  
<tex> n = 2 </tex> (<tex> 2 - 1 = 1 </tex>)
+
<tex> n = 2 </tex>. В сети всего два входа, на которых располагается один компаратор, тем самым наше предположение выполняется.
  
 
'''Шаг индукции''':
 
'''Шаг индукции''':
  
Пусть <tex> S(n) </tex> - количество слоев в сети сортировки с <tex> n </tex> входами.
+
Пусть <tex> S(n) </tex> количество слоев в сети сортировки с <tex> n </tex> входами.
 +
 
 +
При переходе от сортирующей сети с <tex>n</tex> входами к сети с <tex>n + 1</tex> входами, добавляем <tex> n </tex> компараторов <tex>\left( [0:1] \dots [0:n]\right) </tex>. Заметим, что в <tex> n - 2 </tex> добавленных компаратора можно вложить <tex> n - 2 </tex> компараторов из предыдущей сети, так, вкладывая один компаратор в другой, образуется новый слой, т.е. количество слоев не изменяется. Тогда останется два компаратора: <tex>[0:1], [0:2] </tex> в которые ничего нельзя вложить, т.е. количество слоев изменяется на <tex> 2 = S(n + 1) - S(n) </tex>.  
  
При переходе от <tex>n</tex> - й сортирующей сети к <tex>(n + 1)</tex>-й, добавляем <tex> n - 1 </tex> компаратор, которые являются одним слоем. Тем самым получили рекуррентное соотношение:
+
Тогда наш переход выполняется и формула верна. Что и требовалось доказать.
<tex> S(n + 1) = S(n) + 1 </tex> с начальными данными (<tex>S(2) = 1</tex>). Решением данного рекуррентного соотношения является <tex> S(n) = n - 1 </tex>. Что и требовалось доказать  
 
  
 
}}
 
}}
 +
 +
Пример правильной и ошибочной сети для <tex> n = 4 </tex>. Если перенести свободные компараторы и слить их в один слой, то можно уменьшить количество слоев, но при этом сеть перестает быть сортирующей (при <tex> n = 4 </tex> ошибка будет возникать на последовательности <tex> [0,1,0,0] </tex>).
 +
 +
[[Файл:MyRis.jpg]]
  
 
==См.также==
 
==См.также==
Строка 69: Строка 82:
 
*Дональд Э. Кнут. Искусство программирования. Том 3. Сортировка и Поиск. стр. 238— ISBN 0-201-89685-0
 
*Дональд Э. Кнут. Искусство программирования. Том 3. Сортировка и Поиск. стр. 238— ISBN 0-201-89685-0
 
*Кормен, Томас Х.,Рональд Л., Штайн, Клифорд. Глава 27. Сортирующие сети // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-e издание. — М.: «Вильямс», 2005. — С. 799 - 822. — ISBN 5-8459-0857-4.
 
*Кормен, Томас Х.,Рональд Л., Штайн, Клифорд. Глава 27. Сортирующие сети // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-e издание. — М.: «Вильямс», 2005. — С. 799 - 822. — ISBN 5-8459-0857-4.
*[https://ru.wikipedia.org/wiki/%D0%A1%D0%B5%D1%82%D1%8C_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8 Википедия - Сети сортировки]
+
*[https://ru.wikipedia.org/wiki/%D0%A1%D0%B5%D1%82%D1%8C_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8 Википедия Сети сортировки]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Сортирующие сети]]
 
[[Категория: Сортирующие сети]]

Текущая версия на 19:19, 4 сентября 2022

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

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

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

Сортировка пузырьком Сортировка вставками Сортировка выбором
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][1:2],[2:3]\dots[n:n + 1][/math] или [math][n + 1:n],[n:n + 1]\dots[1:2][/math], т.к. возможны две стратегии добавления; отсюда, кстати, тоже видна эквивалентность схем для обоих сортировок). Будем также поддерживать сортирующую сеть в виде "треугольной" сети. Таким образом компараторы [math][i:i+1],\ i \geqslant 3[/math] можно расположить в существующих слоях над самым верхним компаратором в соответствующем слое. То есть в сети с [math] n [/math] входами был слой с единственным компаратором [math][1:2][/math], поэтому над ним можно разместить компаратор [math][3 : 4][/math], на [math][2:3][/math][math][4:5][/math]. Затем на следующем слое будет уже два компаратора: [math][3 : 4][/math] над [math][1:2][/math], поэтому сверху можно добавить [math] [5: 6][/math]. В общем виде, на слое с номером [math] k \geqslant 0 [/math] с конца (до середины треугольника), будет [math]\left\lfloor\dfrac{k}{2}\right\rfloor + 1[/math] компараторов, последним из которых является [math][k + 1 : k + 2][/math], следовательно, на этот слой можно добавить компаратор [math][k + 3 : k + 4][/math].

Значит, новые слои создадутся лишь благодаря компаратором [math][1:2][/math] и [math][2:3][/math], поэтому число слоёв в новой сети составит [math]S(n+1) = 2n - 3 + 1 = 2n - 1 = 2(n + 1) - 3[/math], что удовлетворяет нашему соотношению.
[math]\triangleleft[/math]

Сортирующая сеть для [math] n = 6 [/math]:

Parralelsort.png

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

Сеть для сортировки выбором выглядит иначе. При переходе к сети с [math] n + 1 [/math] входами, добавляется [math] n [/math] компараторов: [math] [0:1],[0:2]\dots[0:n] [/math], .

Choosesortparralel2.png

Утверждение:
В результирующей сети будет [math]2n - 3[/math] слоев, где [math] n [/math] — количество входов.
[math]\triangleright[/math]

Определим операцию вложения компаратора [math] [i:j] [/math] в компаратор [math] [t:s] [/math] : разместим компаратор [math] [i:j] [/math] и [math] [t:s] [/math] на одном слое, так, что [math] t \lt i \lt j \lt s [/math].

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

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

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

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

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

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

Тогда наш переход выполняется и формула верна. Что и требовалось доказать.
[math]\triangleleft[/math]

Пример правильной и ошибочной сети для [math] n = 4 [/math]. Если перенести свободные компараторы и слить их в один слой, то можно уменьшить количество слоев, но при этом сеть перестает быть сортирующей (при [math] n = 4 [/math] ошибка будет возникать на последовательности [math] [0,1,0,0] [/math]).

MyRis.jpg

См.также

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

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