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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Сортировка выбором)
(не показано 8 промежуточных версий 2 участников)
Строка 5: Строка 5:
 
На один слой будем устанавливать только один компаратор. Все последующие сети получаются простым моделированием соответствующих сортировок.
 
На один слой будем устанавливать только один компаратор. Все последующие сети получаются простым моделированием соответствующих сортировок.
 
{| cellpadding="10"
 
{| cellpadding="10"
| '''[[Сортировка пузырьком]]''' || '''[[Сортировка вставками]]''' || '''Сортировка выбором'''
+
| '''[[Сортировка пузырьком]]''' || '''[[Сортировка вставками]]''' || '''[[Сортировка выбором]]'''
 
|-
 
|-
 
| [[Файл:Bubblesort.png]] || [[Файл:Insertsort.png]] || [[Файл:Choosesort.png‎]]
 
| [[Файл:Bubblesort.png]] || [[Файл:Insertsort.png]] || [[Файл:Choosesort.png‎]]
Строка 16: Строка 16:
 
=== Сортировка пузырьком и вставками ===
 
=== Сортировка пузырьком и вставками ===
  
Заметим, если сжать последовательные сортирующие сети пузырьком и вставками, то результат будет одним и тем же. Это видно из симметрии расположения компараторов на картинках выше.
+
Заметим, что если сжать последовательные сортирующие сети пузырьком и вставками, то результат будет одним и тем же. Это видно из симметрии расположения компараторов на картинках выше.
 
{{
 
{{
 
Утверждение
 
Утверждение
Строка 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: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>[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>, что удовлетворяет нашему соотношению.
  
 
}}
 
}}
Строка 41: Строка 44:
  
 
=== Сортировка выбором ===
 
=== Сортировка выбором ===
Сеть для сортировки выбором выглядит иначе. Будем компаратор "вкладывать" в компаратор, для получения слоев.
+
 
 +
Сеть для [[Сортировка выбором | сортировки выбором]] выглядит иначе. При переходе к сети с <tex> n + 1 </tex> входами, добавляется <tex> n </tex> компараторов: <tex> [0:1],[0:2]\dots[0:n] </tex>, .
 +
 
 +
[[Файл: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>.
  
 
Теперь воспользуемся принципом математической индукции.
 
Теперь воспользуемся принципом математической индукции.
Строка 59: Строка 66:
 
Пусть <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>.  
 +
 
 +
Тогда наш переход выполняется и формула верна. Что и требовалось доказать.
  
 
}}
 
}}
  
[[Файл:Choosesortparralel.png‎]]
+
Пример правильной и ошибочной сети для <tex> n = 4 </tex>. Если перенести свободные компараторы и слить их в один слой, то можно уменьшить количество слоев, но при этом сеть перестает быть сортирующей (при <tex> n = 4 </tex> ошибка будет возникать на последовательности <tex> [0,1,0,0] </tex>).
 +
 
 
[[Файл:MyRis.jpg]]
 
[[Файл:MyRis.jpg]]
 +
 
==См.также==
 
==См.также==
 
* [[Сортировочные сети с особыми свойствами]]
 
* [[Сортировочные сети с особыми свойствами]]

Версия 21:06, 25 мая 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: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.
  • Википедия — Сети сортировки