Сортировочные сети с особыми свойствами — различия между версиями
Kabanov (обсуждение | вклад) м (→Примеры) |
м (rollbackEdits.php mass rollback) |
||
(не показано 18 промежуточных версий 6 участников) | |||
Строка 2: | Строка 2: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | <b>Нечетно-четная сортирующая сеть (odd-even sorting network) | + | <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> также не | + | | '''Случай 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>Перестановочная сеть</b> (англ. ''permutation network'') {{---}} сеть сортировки, содержащая на <tex>n</tex> входов и <tex>n</tex> выходов переключатели, позволяющие соединять входы сети с её выходами в соответствии с любой из <tex>n!</tex> возможных перестановок. |
}} | }} | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | <b>Перестановочная сортирующая сеть (permutation sorting network) | + | <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> переключателей | + | | [[Файл: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>Периодическая сортировочная сеть</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> {{---}} уровень сети, и у которой каждый уровень может быть построен с помощью рекурсивного алгоритма. |
}} | }} | ||
Строка 55: | Строка 55: | ||
[[Файл: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 \ | + | Показанная на рисунке сеть следует считать иллюстрацией рекурсивного построения 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 \ | + | Если <tex>i \bmod 4 = </tex> |
* <tex>0 \Rightarrow</tex> красный | * <tex>0 \Rightarrow</tex> красный | ||
* <tex>1 \Rightarrow</tex> синий | * <tex>1 \Rightarrow</tex> синий | ||
Строка 70: | Строка 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< | + | Теперь для <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> раз. | ||
Строка 83: | Строка 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) на транспозиционная сортирующая сеть с уровнями сравнивающих устройств, соединенных между собой по схеме "кирпичной кладки". | входов — это
Примеры
![]() |
![]() |
![]() |
Для | Для | (Вариант 1)Для | (Вариант 2)
Как видно, из рисунка, при
и линия соединена сравнивающим устройством на глубине c линией , если .Так же вполне очевидно, что если
четно, что имеется 2 варианта построения.Одним из основных достоинств является то, что такую сортировку легко реализовать аппаратно, поскольку выполняются попеременно только 2 вида действий.
Теорема: |
Нечетно-четная сортирующая сеть действительно является сортирующей сетью. |
Докажем теорему методом математической индукции по 0-1 принципом.
линиям. Так же воспользуемсяБаза индукции. При
в сети не будет компараторов, но она очевидно будет являться сортирующей. Допустим, что наше предположение верно и для случая, где сеть имеет линий. Рассмотрим случай с линиями. Пусть на вход подается последовательность нулей и единиц: . Появляется 2 случая:Случай 1. Если | , то компараторы ничего не изменят. И компараторы на линиях также не будут использовать элемент. По нашему предположению, наша сеть отсортирует последовательность длины . Итак, элемент уже находится на правильной позиции, следовательно мы получим отсортированную последовательность .|
Случай 2. Если | , то этот элемент столкнувшись с любым компаратором будет совершать обмен (даже если обмен не является необходимым, когда другой элемент также , результат будет таким же). Соответствующие компараторы могут быть замены путем скрещивания линий. По нашему предположению, наша сеть отсортирует последовательность длины . Итак, элемент путем прохождения сети будет помещен на правильную позиции, следовательно мы получим отсортированную последовательность .
Перестановочная сеть
Определение: |
Перестановочная сеть (англ. permutation network) — сеть сортировки, содержащая на | входов и выходов переключатели, позволяющие соединять входы сети с её выходами в соответствии с любой из возможных перестановок.
Определение: |
Перестановочная сортирующая сеть (англ. permutation sorting network) — сеть сортировки, содержащая последовательность компараторов | , где каждый модуль может устанавливаться извне в одно из двух остояний: либо он передает свои входы без изменений, либо меняет местами и независимо от значений и .
Примеры
Периодическая сортировочная сеть
Определение: |
Периодическая сортировочная сеть (англ. periodic sorting network) на | входов — сеть сортировки, содержащая входов, где — уровень сети, и у которой каждый уровень может быть построен с помощью рекурсивного алгоритма.
Примеры
Для начала раскрасим все линии красным или синим цветом в соответствии со следующими правилами: Показанная на рисунке сеть следует считать иллюстрацией рекурсивного построения t-уровневой сети при
в случае . Если пронумеровать линии входов от до , то -й уровень имеет компараторы , где и . Всего существует компараторов, как и в сети битонного слияния.Теорема: |
Если входные числа -упорядочены при некотором , то периодическая сеть приведет к выходу, который будет -упорядочен. |
Доказательство: |
Если
Теперь можно увидеть, что первые уровней сети состоят из двух отдельных сетей: одна из красных линий, а другая — из синих линий. Компараторы на -м уровне образуют сеть слияния, как в сетях битонного или четно-нечетного слияния. Таким образом, мы получили искомый результат при .Такой способ так же годится и для случая Теперь для . Если вход -упорядочен, красные линии содержат чисел, которые являются -упорядоченными; то же самое можно сказать относительно синих линий. Очевидно, что результат является -упорядоченным. можно предположить, что . Первые уровней разделяются на отдельных сетей размеров , каждая из которых является -упорядоченной в случае ; следовательно, линии являются -упорядоченными после уровней. Последующие уровни, очевидно, сохраняют -упорядоченность, так как они обладают "вертикальной" периодичностью порядка . |
Таким образом мы сможем сортировать
чисел, пропуская их через сеть раз.См. также
Источники информации
- Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 27.5, стр. 819
- Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 5.3.4, стр. 275
- Bachelor-Studiengang Angewandte Informatik — Odd-even transposition sort