418
правок
Изменения
Нет описания правки
Нечетно-четная сортирующая сеть действительно является сортирующей сетью.
|proof=
Докажем теорему методом математической индукции по <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>.
}}
== Перестановочная сеть ==
