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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 32: Строка 32:
 
Пусть <tex> S(n) = 2n - 3 </tex> — количество слоев в сети сортировки.
 
Пусть <tex> S(n) = 2n - 3 </tex> — количество слоев в сети сортировки.
  
−
При переходе от сортирующей сети с <tex>n</tex> входами к сети с <tex>n + 1</tex> входами, добавляем <tex> n </tex> дополнительных компараторов(<tex>[1:2]\dots[n - 1:n]</tex> или <tex>[n - 1:n]\dots[1:2]</tex>, т.к. возможны две стратегии добавления). В полученной "треугольной" сети можно заметить, что <tex>n - 1</tex> компаратор входят в уже существующие слои, но тогда один компаратор из предыдущей сортирующий сети и один из добавленных не вносят вклад в количество слоев. Тогда видно, что количество слоев увеличилось на <tex> 2 = S(n + 1) - S(n) </tex>, т.е. наш переход выполняется и наша формула верна. Что и требовалось доказать.
+
При переходе от сортирующей сети с <tex>n</tex> входами к сети с <tex>n + 1</tex> входами, добавляем <tex> n </tex> дополнительных компараторов (<tex>[1:2][2:3]\dots[n - 1:n]</tex> или <tex>[n - 1:n][n - 2:n - 1]\dots[1:2]</tex>, т.к. возможны две стратегии добавления). В полученной "треугольной" сети можно заметить, что <tex>n - 1</tex> компаратор входят в уже существующие слои (<tex>[2:3][3:4]\dots[n - 1:n] </tex> или <tex>[n - 1:n][n - 2:n - 3]\dots[2:3]</tex>), но тогда один компаратор из предыдущей сортирующий сети и один из добавленных не вносят вклад в количество слоев. Тогда видно, что количество слоев увеличилось на <tex> 2 = S(n + 1) - S(n) </tex>, т.е. наш переход выполняется и наша формула верна. Что и требовалось доказать.
  
 
}}
 
}}
Строка 44: Строка 44:
 
Сеть для сортировки выбором выглядит иначе. Будем компаратор "вкладывать" в компаратор, для получения слоев.
 
Сеть для сортировки выбором выглядит иначе. Будем компаратор "вкладывать" в компаратор, для получения слоев.
  
−
[[Файл:Choosesortparralel.png‎]]
+
[[Файл:Choosesortparralel2.png‎]]
  
 
{{
 
{{
 
Утверждение
 
Утверждение
 
|statement=
 
|statement=
−
В результирующей сети будет <tex>2n - 3</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> [i:j] </tex> в компаратор <tex> [t:s] </tex> : разместим компаратор  <tex> [i:j] </tex> и <tex> [t:s] </tex> на одном слое, так, что <tex> t < i < j < s </tex>.
  
 
Теперь воспользуемся принципом математической индукции.
 
Теперь воспользуемся принципом математической индукции.
Строка 63: Строка 63:
 
Пусть <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 = 4 </tex> можно перенести свободные компараторы и слить их в один слой, но при этом сеть перестает быть сортирующей (при <tex> n = 4 </tex> ошибка будет возникать на векторе <tex> 0100 </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 = 4 </tex> можно перенести свободные компараторы и слить их в один слой, но при этом сеть перестает быть сортирующей (при <tex> n = 4 </tex> ошибка будет возникать на векторе <tex> [0,1,0,0] </tex>). Тогда наш переход выполняется и наша формула верна. Что и требовалось доказать.
  
 
}}
 
}}

Версия 16:43, 24 мая 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][1:2][2:3]\dots[n - 1:n][/math] или [math][n - 1:n][n - 2:n - 1]\dots[1:2][/math], т.к. возможны две стратегии добавления). В полученной "треугольной" сети можно заметить, что [math]n - 1[/math] компаратор входят в уже существующие слои ([math][2:3][3:4]\dots[n - 1:n] [/math] или [math][n - 1:n][n - 2:n - 3]\dots[2:3][/math]), но тогда один компаратор из предыдущей сортирующий сети и один из добавленных не вносят вклад в количество слоев. Тогда видно, что количество слоев увеличилось на [math] 2 = S(n + 1) - S(n) [/math], т.е. наш переход выполняется и наша формула верна. Что и требовалось доказать.
[math]\triangleleft[/math]

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

Parralelsort.png

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

Сеть для сортировки выбором выглядит иначе. Будем компаратор "вкладывать" в компаратор, для получения слоев.

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] n = 4 [/math] можно перенести свободные компараторы и слить их в один слой, но при этом сеть перестает быть сортирующей (при [math] n = 4 [/math] ошибка будет возникать на векторе [math] [0,1,0,0] [/math]). Тогда наш переход выполняется и наша формула верна. Что и требовалось доказать.
[math]\triangleleft[/math]

Пример правильной и ошибочной сети для [math] n = 4 [/math]

MyRis.jpg

См.также

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

  • Дональд Э. Кнут. Искусство программирования. Том 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=46836»