Сортировочные сети с особыми свойствами — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 18: Строка 18:
 
|statement=
 
|statement=
 
Нечетно-четная сортирующая сеть действительно является сортирующей сетью.
 
Нечетно-четная сортирующая сеть действительно является сортирующей сетью.
|proof=
+
}}
 
Докажем теорему методом математической индукции по <tex>n</tex> линиям. Так же воспользуемся 0-1 принципом.
 
Докажем теорему методом математической индукции по <tex>n</tex> линиям. Так же воспользуемся 0-1 принципом.
  
Строка 25: Строка 25:
 
Рассмотрим случай с <tex>n</tex> линиями. Пусть на вход подается последовательность нулей и единиц: <tex>a=a_0,...,a_{n-1}</tex>.
 
Рассмотрим случай с <tex>n</tex> линиями. Пусть на вход подается последовательность нулей и единиц: <tex>a=a_0,...,a_{n-1}</tex>.
 
Появляется 2 случая:
 
Появляется 2 случая:
'''Случай 1.''' Если <tex>a_{n-1}=1</tex>, то компараторы <tex>[n-2:n-1]</tex> ничего не изменят. И компараторы на линиях <tex>\{0...n-1\}</tex> также не будет использовать <tex>a_{n-1}</tex> элемент. По нашему предположению, наша сеть отсортирует последовательность <tex>a_0,...,a_{n-2}</tex> длины <tex>n-1</tex>. Итак, элемент a_{n-1} уже находится на правильной позиции, следовательно мы получим отсортированную последовательность <tex>a</tex>.
+
 
'''Случай 2.''' Если <tex>a_{n-1}=0</tex>, то этот элемент столкнувшись с любым компаратором будет совершать обмен (даже если обмен не является необходимым, когда другой элемент также <tex>0</tex>, результат будет таким же). Соответствующие компараторы могут быть замены путем скрещивания линий. По нашему предположению, наша сеть отсортирует последовательность <tex>a_0,...,a_{n-2}</tex> длины <tex>n-1</tex>.  Итак, элемент a_{n-1} путем прохождения сети будет помещен на правильную позиции, следовательно мы получим отсортированную последовательность <tex>a</tex>.
+
{| cellpadding="0"
}}
+
| '''Случай 1.''' Если <tex>a_{n-1}=1</tex>, то компараторы <tex>[n-2:n-1]</tex> ничего не изменят. И компараторы на линиях <tex>\{0...n-1\}</tex> также не будет использовать <tex>a_{n-1}</tex> элемент. По нашему предположению, наша сеть отсортирует последовательность <tex>a_0,...,a_{n-2}</tex> длины <tex>n-1</tex>. Итак, элемент a_{n-1} уже находится на правильной позиции, следовательно мы получим отсортированную последовательность <tex>a</tex>. || [[Файл:odd-even__sorting_network_proof(1).png|thumb|300px]]
 +
|-
 +
| '''Случай 2.''' Если <tex>a_{n-1}=0</tex>, то этот элемент столкнувшись с любым компаратором будет совершать обмен (даже если обмен не является необходимым, когда другой элемент также <tex>0</tex>, результат будет таким же). Соответствующие компараторы могут быть замены путем скрещивания линий. По нашему предположению, наша сеть отсортирует последовательность <tex>a_0,...,a_{n-2}</tex> длины <tex>n-1</tex>.  Итак, элемент <tex>a_{n-1}</tex> путем прохождения сети будет помещен на правильную позиции, следовательно мы получим отсортированную последовательность <tex>a</tex>. || [[Файл:odd-even__sorting_network_proof(2).png|thumb|300px]]
 +
|}
 +
 
 
== Перестановочная сеть ==
 
== Перестановочная сеть ==
 
{{Определение
 
{{Определение
Строка 38: Строка 42:
 
|definition=
 
|definition=
 
<b>Периодическая сортировочная сеть (periodic sorting network)</b> на <tex>n</tex> входов <tex><a_1,a_2,...,a_n></tex> {{---}} сеть сортировки, содержащая <tex>n = 2^t</tex> входов</tex>, где <tex>t</tex> - уровень сети, и у которой каждый уровень может быть построен с помощью рекурсивного алгоритма.  
 
<b>Периодическая сортировочная сеть (periodic sorting network)</b> на <tex>n</tex> входов <tex><a_1,a_2,...,a_n></tex> {{---}} сеть сортировки, содержащая <tex>n = 2^t</tex> входов</tex>, где <tex>t</tex> - уровень сети, и у которой каждый уровень может быть построен с помощью рекурсивного алгоритма.  
}}
+
 
 
=== Примеры ===
 
=== Примеры ===
 
[[Файл:periodic_sorting_network.png|thumb]]
 
[[Файл:periodic_sorting_network.png|thumb]]
Строка 47: Строка 51:
 
|statement=
 
|statement=
 
Если входные числа <tex>2^k</tex> - упорядочены при некотором <tex>k \geqslant 1</tex>, то периодическая сеть приведет к выходу, который будет <tex>2^{k-1}</tex> - упорядочен.
 
Если входные числа <tex>2^k</tex> - упорядочены при некотором <tex>k \geqslant 1</tex>, то периодическая сеть приведет к выходу, который будет <tex>2^{k-1}</tex> - упорядочен.
 +
 
|proof=
 
|proof=
 
[[Файл:periodic_sorting_network_proof.png|thumb]]
 
[[Файл:periodic_sorting_network_proof.png|thumb]]

Версия 18:53, 10 июня 2013

Нечетно-четная сортирующая сеть

Определение:
Нечетно-четная сортирующая сеть (odd-even sorting network) на [math]n[/math] входов [math]\lt a_1,a_2,...,a_n\gt [/math] — это транспозиционная сортирующая сеть с [math]n[/math] уровнями сравнивающих устройств, соединенных между собой по схеме "кирпичной кладки".

Примеры

Odd-even sorting network(n=5).png Odd-even sorting network(n=6v1).png Odd-even sorting network(n=6v2).png
Для [math]n=5[/math] Для [math]n=6[/math] (Вариант 1) Для [math]n=6[/math] (Вариант 2)

Как видно, из рисунка, при [math]i=1,2,...,n[/math] и [math]d=1,2,...,n[/math] линия [math]i[/math] соединена сравнивающим устройством на глубине [math]d[/math] c линией [math]j=i+(-1)^{i+d}[/math], если [math]1 \leqslant j \leqslant n[/math].

Так же вполне очевидно, что если [math]n[/math] четно, что имеется 2 варианта построения.

Одним из основных достоинств является то, что такую сортировку легко реализовать аппаратно, поскольку выполняются попеременно только 2 вида действий.

Теорема:
Нечетно-четная сортирующая сеть действительно является сортирующей сетью.

Докажем теорему методом математической индукции по [math]n[/math] линиям. Так же воспользуемся 0-1 принципом.

База индукции. При [math]n=1[/math] в сети не будет компараторов, но она очевидно будет являться сортирующей. Допустим, что наше предположение верно и для случая, где сеть имеет [math]n-1[/math] линий. Рассмотрим случай с [math]n[/math] линиями. Пусть на вход подается последовательность нулей и единиц: [math]a=a_0,...,a_{n-1}[/math]. Появляется 2 случая:

Случай 1. Если [math]a_{n-1}=1[/math], то компараторы [math][n-2:n-1][/math] ничего не изменят. И компараторы на линиях [math]\{0...n-1\}[/math] также не будет использовать [math]a_{n-1}[/math] элемент. По нашему предположению, наша сеть отсортирует последовательность [math]a_0,...,a_{n-2}[/math] длины [math]n-1[/math]. Итак, элемент a_{n-1} уже находится на правильной позиции, следовательно мы получим отсортированную последовательность [math]a[/math].
Odd-even sorting network proof(1).png
Случай 2. Если [math]a_{n-1}=0[/math], то этот элемент столкнувшись с любым компаратором будет совершать обмен (даже если обмен не является необходимым, когда другой элемент также [math]0[/math], результат будет таким же). Соответствующие компараторы могут быть замены путем скрещивания линий. По нашему предположению, наша сеть отсортирует последовательность [math]a_0,...,a_{n-2}[/math] длины [math]n-1[/math]. Итак, элемент [math]a_{n-1}[/math] путем прохождения сети будет помещен на правильную позиции, следовательно мы получим отсортированную последовательность [math]a[/math].
Odd-even sorting network proof(2).png

Перестановочная сеть

Определение:
Перестановочная сортирующая сеть (permutation sorting network) — сеть сортировки, содержащая на [math]n[/math] входов и [math]n[/math] выходов переключатели, позволяющие соединять входы сети с её выходами в соответствии с любой из [math]n![/math] возможных перестановок.

Примеры

Периодическая сортировочная сеть

{{Определение |definition= Периодическая сортировочная сеть (periodic sorting network) на [math]n[/math] входов [math]\lt a_1,a_2,...,a_n\gt [/math] — сеть сортировки, содержащая [math]n = 2^t[/math] входов</tex>, где [math]t[/math] - уровень сети, и у которой каждый уровень может быть построен с помощью рекурсивного алгоритма.

Примеры

Periodic sorting network.png

Для начала раскрасим все линии красным или синим цветом в соответствии со следующими правилами: Показанная на рисунке сеть следует считать иллюстрацией рекурсивного построения t-уровневой сети при [math]n=2^t[/math] в случае [math]t=4[/math]. Если пронумеровать линии входов от [math]0[/math] до [math]2^t-1[/math], то [math]l[/math]-й уровень имеет компараторы [math][i:j][/math], где [math]i \mod 2^{t+1-l} \lt 2^{t-l}[/math] и [math]j=i 0x (2^{t+1-l}-1)[/math]. Всего существует [math]t\cdot2^{t-1}[/math] компараторов, как и в сети битонного слияния.

Теорема:
Если входные числа [math]2^k[/math] - упорядочены при некотором [math]k \geqslant 1[/math], то периодическая сеть приведет к выходу, который будет [math]2^{k-1}[/math] - упорядочен.
Доказательство:
[math]\triangleright[/math]
Periodic sorting network proof.png

Если [math]i \mod 4 = [/math]

  • [math]0 \Rightarrow[/math] красный
  • [math]1 \Rightarrow[/math] синий
  • [math]2 \Rightarrow[/math] синий
  • [math]3 \Rightarrow[/math] красный

Теперь можно увидеть, что первые [math]t-1[/math] уровней сети состоят из двух отдельных сетей: одна из [math]2^{t-1}[/math] красных линий, а другая - из [math]2^{t-1}[/math] синих линий. Компараторы на [math]t[/math]-м уровне образуют сеть слияния, как в сетях битонного или четно-нечетного слияния. Таким образом, мы получили искомый результат при [math]k=1[/math].

Такой способ так же годится и для случая k=2. Если вход 4-упорядочен, красные линии содержат [math]2^{t-1}[/math] чисел, которые являются 2-упорядоченными; то же самое можно сказать относительно синих линий. Очевидно, что результат является 2-упорядоченным.

Теперь для [math]k \geqslant 2[/math] можно предположить, что k<=t. Первые [math]t-k+2[/math] уровней разделяются на [math]2^{k-2}[/math] отдельных сетей размеров [math]2^{t-k+2}[/math], каждая из которых является [math]2[/math]-упорядоченной в случае [math]k=2[/math]; следовательно, линии являются [math]2^{k-1}[/math]-упорядоченными после [math]t-k+2[/math] уровней. Последующие уровни, очевидно, сохраняют [math]2^{k-1}[/math]-упорядоченность, так как они обладают "вертикальной" периодичностью порядка [math]2^{k-2}[/math].
[math]\triangleleft[/math]

Таким образом мы сможем сортировать [math]2^t[/math] чисел, пропуская их через сеть [math]t[/math] раз.

См. также

Ссылки

  • Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 27.5, стр. 819
  • Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 5.3.4, стр. 275