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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{В разработке}}»)
 
м (Сортировка выбором)
 
(не показано 36 промежуточных версий 8 участников)
Строка 1: Строка 1:
{{В разработке}}
+
Рассмотрим модели [[Сортирующие сети|сортирующих сетей]] для квадратичных сортировок.
 +
 
 +
== Сортирующие сети с последовательной сортировкой ==
 +
 
 +
На один слой будем устанавливать только один компаратор. Все последующие сети получаются простым моделированием соответствующих сортировок.
 +
{| cellpadding="10"
 +
| '''[[Сортировка пузырьком]]''' || '''[[Сортировка вставками]]''' || '''[[Сортировка выбором]]'''
 +
|-
 +
| [[Файл:Bubblesort.png]] || [[Файл:Insertsort.png]] || [[Файл:Choosesort.png‎]]
 +
|}
 +
 
 +
== Сортирующие сети с параллельной сортировкой ==
 +
 
 +
На один слой устанавливается несколько компараторов.
 +
 
 +
=== Сортировка пузырьком и вставками ===
 +
 
 +
Заметим, что если сжать последовательные сортирующие сети пузырьком и вставками, то результат будет одним и тем же. Это видно из симметрии расположения компараторов на картинках выше.
 +
{{
 +
Утверждение
 +
|statement=
 +
В результирующей сети будет <tex>(2n - 3)</tex> слоев, где <tex>n</tex> — количество входов.
 +
|proof=
 +
Докажем данное утверждение по принципу математической индукции.
 +
 
 +
'''База индукции''':
 +
 
 +
При <tex> n = 2 </tex>. В сети всего два входа, на которых располагается один компаратор, тем самым наше предположение выполняется.
 +
 
 +
'''Шаг индукции''':
 +
 
 +
Пусть <tex> S(n) = 2n - 3 </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>, что удовлетворяет нашему соотношению.
 +
 
 +
}}
 +
 
 +
Сортирующая сеть для <tex> n = 6 </tex>:
 +
 
 +
[[Файл:Parralelsort.png‎]]
 +
 
 +
=== Сортировка выбором ===
 +
 
 +
Сеть для [[Сортировка выбором | сортировки выбором]] выглядит иначе. При переходе к сети с <tex> n + 1 </tex> входами, добавляется <tex> n </tex> компараторов: <tex> [0:1],[0:2]\dots[0:n] </tex>, .
 +
 
 +
[[Файл:Choosesortparralel2.png‎]]
 +
 
 +
{{
 +
Утверждение
 +
|statement=
 +
В результирующей сети будет <tex>2n - 3</tex> слоев, где <tex> n </tex> — количество входов.
 +
|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> 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> [0,1,0,0] </tex>).
 +
 
 +
[[Файл:MyRis.jpg]]
 +
 
 +
==См.также==
 +
* [[Сортировочные сети с особыми свойствами]]
 +
 
 +
== Источники информации==
 +
*Дональд Э. Кнут. Искусство программирования. Том 3. Сортировка и Поиск. стр. 238— ISBN 0-201-89685-0
 +
*Кормен, Томас Х.,Рональд Л., Штайн, Клифорд. Глава 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 Википедия — Сети сортировки]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
 
 +
[[Категория: Сортирующие сети]]

Текущая версия на 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.
  • Википедия — Сети сортировки