Сортировочные сети с особыми свойствами — различия между версиями
Kabanov (обсуждение | вклад) |
Kabanov (обсуждение | вклад) |
||
Строка 19: | Строка 19: | ||
Нечетно-четная сортирующая сеть действительно является сортирующей сетью. | Нечетно-четная сортирующая сеть действительно является сортирующей сетью. | ||
|proof= | |proof= | ||
− | Докажем теорему методом математической индукции по <tex>n</tex> линиям. | + | Докажем теорему методом математической индукции по <tex>n</tex> линиям. Так же воспользуемся 0-1 принципом. |
+ | '''База индукции.''' При <tex>n=1</tex> в сети не будет компараторов, но она очевидно будет являться сортирующей. | ||
+ | Допустим, что наше предположение верно и для случая, где сеть имеет <tex>n-1</tex> линий. | ||
+ | Рассмотрим случай с <tex>n</tex> линиями. Пусть на вход подается последовательность нулей и единиц: <tex>a=a_0,...,a_{n-1}</tex>. | ||
+ | Появляется 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>. | ||
}} | }} | ||
== Перестановочная сеть == | == Перестановочная сеть == |
Версия 18:36, 10 июня 2013
Содержание
Нечетно-четная сортирующая сеть
Определение: |
Нечетно-четная сортирующая сеть (odd-even sorting network) на | входов — это транспозиционная сортирующая сеть с уровнями сравнивающих устройств, соединенных между собой по схеме "кирпичной кладки".
Примеры
Для | Для | (Вариант 1)Для | (Вариант 2)
Как видно, из рисунка, при
и линия соединена сравнивающим устройством на глубине c линией , если .Так же вполне очевидно, что если
четно, что имеется 2 варианта построения.Одним из основных достоинств является то, что такую сортировку легко реализовать аппаратно, поскольку выполняются попеременно только 2 вида действий.
Теорема: |
Нечетно-четная сортирующая сеть действительно является сортирующей сетью. |
Доказательство: |
Докажем теорему методом математической индукции по линиям. Так же воспользуемся 0-1 принципом.База индукции. При Случай 2. Если в сети не будет компараторов, но она очевидно будет являться сортирующей. Допустим, что наше предположение верно и для случая, где сеть имеет линий. Рассмотрим случай с линиями. Пусть на вход подается последовательность нулей и единиц: . Появляется 2 случая: Случай 1. Если , то компараторы ничего не изменят. И компараторы на линиях также не будет использовать элемент. По нашему предположению, наша сеть отсортирует последовательность длины . Итак, элемент a_{n-1} уже находится на правильной позиции, следовательно мы получим отсортированную последовательность . , то этот элемент столкнувшись с любым компаратором будет совершать обмен (даже если обмен не является необходимым, когда другой элемент также , результат будет таким же). Соответствующие компараторы могут быть замены путем скрещивания линий. По нашему предположению, наша сеть отсортирует последовательность длины . Итак, элемент a_{n-1} путем прохождения сети будет помещен на правильную позиции, следовательно мы получим отсортированную последовательность . |
Перестановочная сеть
Определение: |
Перестановочная сортирующая сеть (permutation sorting network) — сеть сортировки, содержащая на | входов и выходов переключатели, позволяющие соединять входы сети с её выходами в соответствии с любой из возможных перестановок.
Примеры
Периодическая сортировочная сеть
Определение: |
Периодическая сортировочная сеть (periodic sorting network) на | входов — сеть сортировки, содержащая входов</tex>, где - уровень сети, и у которой каждый уровень может быть построен с помощью рекурсивного алгоритма.
Примеры
Для начала раскрасим все линии красным или синим цветом в соответствии со следующими правилами: Показанная на рисунке сеть следует считать иллюстрацией рекурсивного построения t-уровневой сети при
в случае . Если пронумеровать линии входов от до , то -й уровень имеет компараторы , где и . Всего существует компараторов, как и в сети битонного слияния.Теорема: |
Если входные числа - упорядочены при некотором , то периодическая сеть приведет к выходу, который будет - упорядочен. |
Доказательство: |
Если
Теперь можно увидеть, что первые уровней сети состоят из двух отдельных сетей: одна из красных линий, а другая - из синих линий. Компараторы на -м уровне образуют сеть слияния, как в сетях битонного или четно-нечетного слияния. Таким образом, мы получили искомый результат при .Такой способ так же годится и для случая k=2. Если вход 4-упорядочен, красные линии содержат Теперь для чисел, которые являются 2-упорядоченными; то же самое можно сказать относительно синих линий. Очевидно, что результат является 2-упорядоченным. можно предположить, что k<=t. Первые уровней разделяются на отдельных сетей размеров , каждая из которых является -упорядоченной в случае ; следовательно, линии являются -упорядоченными после уровней. Последующие уровни, очевидно, сохраняют -упорядоченность, так как они обладают "вертикальной" периодичностью порядка . |
Таким образом мы сможем сортировать
чисел, пропуская их через сеть раз.См. также
Ссылки
- Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 27.5, стр. 819
- Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 5.3.4, стр. 275