Сортировочные сети с особыми свойствами
Содержание
Нечетно-четная сортирующая сеть
Определение: |
Нечетно-четная сортирующая сеть (англ. 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