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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Примеры)
м (rollbackEdits.php mass rollback)
 
(не показано 20 промежуточных версий 6 участников)
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<b>Нечетно-четная сортирующая сеть (odd-even sorting network)</b> на <tex>n</tex> входов <tex><a_1,a_2,...,a_n></tex> {{---}} это транспозиционная сортирующая сеть с <tex>n</tex> уровнями сравнивающих устройств, соединенных между собой по схеме "кирпичной кладки".
+
<b>Нечетно-четная сортирующая сеть</b> (англ. ''odd-even sorting network'') на <tex>n</tex> входов <tex>\langle a_1,a_2,...,a_n \rangle</tex> {{---}} это [[Примитивные_сортирующие_сети | транспозиционная сортирующая сеть]] с <tex>n</tex> уровнями сравнивающих устройств, соединенных между собой по схеме "кирпичной кладки".
 
}}
 
}}
 
=== Примеры ===
 
=== Примеры ===
Строка 27: Строка 27:
  
 
{| cellpadding="0"
 
{| 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]]
+
| '''Случай 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>. Итак, элемент <tex>a_{n-1}</tex> уже находится на правильной позиции, следовательно мы получим отсортированную последовательность <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]]
 
| '''Случай 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]]
Строка 35: Строка 35:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<b>Перестановочная сеть (permutation network)</b> {{---}} сеть сортировки, содержащая на <tex>n</tex> входов и <tex>n</tex> выходов переключатели, позволяющие соединять входы сети с её выходами в соответствии с любой из <tex>n!</tex> возможных перестановок.
+
<b>Перестановочная сеть</b> (англ. ''permutation network'') {{---}} сеть сортировки, содержащая на <tex>n</tex> входов и <tex>n</tex> выходов переключатели, позволяющие соединять входы сети с её выходами в соответствии с любой из <tex>n!</tex> возможных перестановок.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<b>Перестановочная сортирующая сеть (permutation sorting network)</b> {{---}} сеть сортировки, содержащая последовательность компараторов <tex>[i_1:j_1]...[i_r:j_r]</tex>, где каждый модуль [i:j] может устанавливаться извне в одно из двух остояний: либо он передает свои входы без изменений, либо меняет местами <tex>x_i</tex> и <tex>x_j</tex> (независимо от значений <tex>x_i</tex> и <tex>x_j</tex>)
+
<b>Перестановочная сортирующая сеть</b> (англ. ''permutation sorting network'') {{---}} сеть сортировки, содержащая последовательность компараторов <tex>[i_1:j_1]...[i_r:j_r]</tex>, где каждый модуль <tex>[i:j]</tex> может устанавливаться извне в одно из двух остояний: либо он передает свои входы без изменений, либо меняет местами <tex>x_i</tex> и <tex>x_j</tex> <tex>(</tex>независимо от значений <tex>x_i</tex> и <tex>x_j)</tex>.
 
}}
 
}}
 
=== Примеры ===
 
=== Примеры ===
 
{| cellpadding="0"
 
{| cellpadding="0"
| [[Файл:permutation_network.png|thumb|300px|На рисунке показана рекурсивная схема перестановочной сети <tex>P_8</tex> на <tex>8</tex> входов и <tex>8</tex>, которая содержит две копии <tex>P_4</tex> и <tex>8</tex> переключателей (<tex>P_2</tex>).]] || [[Файл:permutation_sorting_network.png|thumb|300px|Перестановочная сортирующая сеть для <tex>n=8</tex>]]
+
| [[Файл:permutation_network.png|thumb|300px|На рисунке показана рекурсивная схема перестановочной сети <tex>P_8</tex> на <tex>8</tex> входов и <tex>8</tex>, которая содержит две копии <tex>P_4</tex> и <tex>8</tex> переключателей <tex>(P_2)</tex>.]]
 
|}
 
|}
  
Строка 49: Строка 49:
 
{{Определение
 
{{Определение
 
|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>Периодическая сортировочная сеть</b> (англ. ''periodic sorting network'') на <tex>n</tex> входов <tex>\langle a_1,a_2,...,a_n \rangle</tex> {{---}} сеть сортировки, содержащая <tex>n = 2^t</tex> входов, где <tex>t</tex> {{---}} уровень сети, и у которой каждый уровень может быть построен с помощью рекурсивного алгоритма.  
 +
}}
  
 
=== Примеры ===
 
=== Примеры ===
 
[[Файл:periodic_sorting_network.png|thumb]]
 
[[Файл:periodic_sorting_network.png|thumb]]
 
Для начала раскрасим все линии красным или синим цветом в соответствии со следующими правилами:
 
Для начала раскрасим все линии красным или синим цветом в соответствии со следующими правилами:
Показанная на рисунке сеть следует считать иллюстрацией рекурсивного построения t-уровневой сети при <tex>n=2^t</tex> в случае <tex>t=4</tex>. Если пронумеровать линии входов от <tex>0</tex> до <tex>2^t-1</tex>, то <tex>l</tex>-й уровень имеет компараторы <tex>[i:j]</tex>, где <tex>i \mod 2^{t+1-l} < 2^{t-l}</tex> и <tex>j=i 0x (2^{t+1-l}-1)</tex>. Всего существует <tex>t\cdot2^{t-1}</tex> компараторов, как и в сети битонного слияния.
+
Показанная на рисунке сеть следует считать иллюстрацией рекурсивного построения t-уровневой сети при <tex>n=2^t</tex> в случае <tex>t=4</tex>. Если пронумеровать линии входов от <tex>0</tex> до <tex>2^t-1</tex>, то <tex>l</tex>-й уровень имеет компараторы <tex>[i:j]</tex>, где <tex>i \bmod 2^{t+1-l} < 2^{t-l}</tex> и <tex>j=i \oplus (2^{t+1-l}-1)</tex>. Всего существует <tex>t\cdot2^{t-1}</tex> компараторов, как и в сети битонного слияния.
  
 
{{Теорема
 
{{Теорема
 
|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]]
  
Если <tex>i \mod 4 = </tex>
+
Если <tex>i \bmod 4 = </tex>
 
* <tex>0 \Rightarrow</tex> красный
 
* <tex>0 \Rightarrow</tex> красный
 
* <tex>1 \Rightarrow</tex> синий
 
* <tex>1 \Rightarrow</tex> синий
Строка 69: Строка 70:
 
* <tex>3 \Rightarrow</tex> красный
 
* <tex>3 \Rightarrow</tex> красный
  
Теперь можно увидеть, что первые <tex>t-1</tex> уровней сети состоят из двух отдельных сетей: одна из <tex>2^{t-1}</tex> красных линий, а другая - из <tex>2^{t-1}</tex> синих линий. Компараторы на <tex>t</tex>-м уровне образуют сеть слияния, как в сетях битонного или четно-нечетного слияния. Таким образом, мы получили искомый результат при <tex>k=1</tex>.
+
Теперь можно увидеть, что первые <tex>t-1</tex> уровней сети состоят из двух отдельных сетей: одна из <tex>2^{t-1}</tex> красных линий, а другая {{---}} из <tex>2^{t-1}</tex> синих линий. Компараторы на <tex>t</tex>-м уровне образуют сеть слияния, как в сетях битонного или четно-нечетного слияния. Таким образом, мы получили искомый результат при <tex>k=1</tex>.
  
Такой способ так же годится и для случая k=2. Если вход 4-упорядочен, красные линии содержат <tex>2^{t-1}</tex> чисел, которые являются 2-упорядоченными; то же самое можно сказать относительно синих линий.
+
Такой способ так же годится и для случая <tex>k=2</tex>. Если вход <tex>4</tex>-упорядочен, красные линии содержат <tex>2^{t-1}</tex> чисел, которые являются <tex>2</tex>-упорядоченными; то же самое можно сказать относительно синих линий.
Очевидно, что результат является 2-упорядоченным.
+
Очевидно, что результат является <tex>2</tex>-упорядоченным.
  
Теперь для <tex>k \geqslant 2</tex> можно предположить, что k<=t. Первые <tex>t-k+2</tex> уровней разделяются на <tex>2^{k-2}</tex> отдельных сетей размеров <tex>2^{t-k+2}</tex>, каждая из которых является <tex>2</tex>-упорядоченной в случае <tex>k=2</tex>; следовательно, линии являются <tex>2^{k-1}</tex>-упорядоченными после <tex>t-k+2</tex> уровней. Последующие уровни, очевидно, сохраняют <tex>2^{k-1}</tex>-упорядоченность, так как они обладают "вертикальной" периодичностью порядка <tex>2^{k-2}</tex>.
+
Теперь для <tex>k \geqslant 2</tex> можно предположить, что <tex>k \leqslant t</tex>. Первые <tex>t-k+2</tex> уровней разделяются на <tex>2^{k-2}</tex> отдельных сетей размеров <tex>2^{t-k+2}</tex>, каждая из которых является <tex>2</tex>-упорядоченной в случае <tex>k=2</tex>; следовательно, линии являются <tex>2^{k-1}</tex>-упорядоченными после <tex>t-k+2</tex> уровней. Последующие уровни, очевидно, сохраняют <tex>2^{k-1}</tex>-упорядоченность, так как они обладают "вертикальной" периодичностью порядка <tex>2^{k-2}</tex>.
 
}}
 
}}
 
Таким образом мы сможем сортировать <tex>2^t</tex> чисел, пропуская их через сеть <tex>t</tex> раз.
 
Таким образом мы сможем сортировать <tex>2^t</tex> чисел, пропуская их через сеть <tex>t</tex> раз.
Строка 82: Строка 83:
 
* [[Сортирующие сети для квадратичных сортировок]]
 
* [[Сортирующие сети для квадратичных сортировок]]
  
== Ссылки ==
+
== Источники информации ==
 
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 27.5, стр. 819
 
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 27.5, стр. 819
 
* Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 5.3.4, стр. 275
 
* Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 5.3.4, стр. 275
 
+
* [http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/oetsen.htm Bachelor-Studiengang Angewandte Informatik {{---}} Odd-even transposition sort]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Сортирующие сети]]
 
[[Категория: Сортирующие сети]]

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

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

Определение:
Нечетно-четная сортирующая сеть (англ. odd-even sorting network) на [math]n[/math] входов [math]\langle a_1,a_2,...,a_n \rangle[/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]. Итак, элемент [math]a_{n-1}[/math] уже находится на правильной позиции, следовательно мы получим отсортированную последовательность [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 network) — сеть сортировки, содержащая на [math]n[/math] входов и [math]n[/math] выходов переключатели, позволяющие соединять входы сети с её выходами в соответствии с любой из [math]n![/math] возможных перестановок.


Определение:
Перестановочная сортирующая сеть (англ. permutation sorting network) — сеть сортировки, содержащая последовательность компараторов [math][i_1:j_1]...[i_r:j_r][/math], где каждый модуль [math][i:j][/math] может устанавливаться извне в одно из двух остояний: либо он передает свои входы без изменений, либо меняет местами [math]x_i[/math] и [math]x_j[/math] [math]([/math]независимо от значений [math]x_i[/math] и [math]x_j)[/math].

Примеры

На рисунке показана рекурсивная схема перестановочной сети [math]P_8[/math] на [math]8[/math] входов и [math]8[/math], которая содержит две копии [math]P_4[/math] и [math]8[/math] переключателей [math](P_2)[/math].

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

Определение:
Периодическая сортировочная сеть (англ. periodic sorting network) на [math]n[/math] входов [math]\langle a_1,a_2,...,a_n \rangle[/math] — сеть сортировки, содержащая [math]n = 2^t[/math] входов, где [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 \bmod 2^{t+1-l} \lt 2^{t-l}[/math] и [math]j=i \oplus (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 \bmod 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].

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

Теперь для [math]k \geqslant 2[/math] можно предположить, что [math]k \leqslant t[/math]. Первые [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] раз.

См. также

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