Сортирующие сети — различия между версиями
Tanfilyev (обсуждение | вклад) |
|||
| Строка 5: | Строка 5: | ||
Сеть называется '''сортирующей''' если для любой входной последовательности получающаяся из не выходная последовательность не убывает. | Сеть называется '''сортирующей''' если для любой входной последовательности получающаяся из не выходная последовательность не убывает. | ||
}} | }} | ||
| + | [[Image:Sorting-network-comparator-demonstration..png|thumb|130px|Сортирующая сеть с 2 проводами]] | ||
| + | |||
| + | |||
| + | |||
== Компараторы == | == Компараторы == | ||
| Строка 41: | Строка 45: | ||
== Источники == | == Источники == | ||
| + | * Кормен Глава 28 Сортирующее сети. | ||
* [http://en.wikipedia.org/wiki/Sorting_network Wikipedia - Sorting networks] | * [http://en.wikipedia.org/wiki/Sorting_network Wikipedia - Sorting networks] | ||
[[Категория: Сортирующие сети]] | [[Категория: Сортирующие сети]] | ||
Версия 23:06, 7 июня 2011
Эта статья находится в разработке!
| Определение: |
| Сеть называется сортирующей если для любой входной последовательности получающаяся из не выходная последовательность не убывает. |
Содержание
Компараторы
| Определение: |
| Компаратором называется устройство подключенное к двум проводам, которое упорядочивает текущие значения на проводах. |
Обычно компараторы меньшее значение передают на провод с меньшим номером, но бывают и направленные компараторы, у которых указано направление перемещения.
| Определение: |
| k-компаратором называется устройство упорядочивающая значения на k проводах. |
Компаратором можно располагать в одном слое если они подключены к разным проводам.
Сети
| Определение: |
| Глубиной сети (depth) называется количество слоев в сети. |
| Определение: |
| Размером сети (size) называется количество компараторов в сети. |
| Теорема: |
Сеть является сортирующей тогда и только тогда, когда она сортирует все наборы из 0 и 1. |
Подробнее в статье 0-1 принцип.
См.также
Сортирующие сети для квадратичных сортировок.
Источники
- Кормен Глава 28 Сортирующее сети.
- Wikipedia - Sorting networks
