Сортирующие сети — различия между версиями
Darkraven (обсуждение | вклад) |
Darkraven (обсуждение | вклад) |
||
| Строка 17: | Строка 17: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| − | '''K-компаратор''' — устройство, | + | '''K-компаратор''' — устройство, упорядочивающее значения на '''k''' проводах. |
}} | }} | ||
| Строка 24: | Строка 24: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| − | '''Сравнивающая сеть''' — несколько компараторов, соединенных проводами. Используется для | + | '''Сравнивающая сеть''' — несколько компараторов, соединенных проводами. Используется для упорядочивания числовых последовательностей. |
}} | }} | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| − | ''' | + | '''Глубина сети (depth)''' — количество слоев в сети. |
}} | }} | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| − | ''' | + | '''Размер сети (size)''' — количество компараторов в сети. |
}} | }} | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
| − | Сеть является сортирующей тогда и только тогда, когда она сортирует все наборы из 0 и 1. | + | Сеть компараторов является сортирующей тогда и только тогда, когда она сортирует все наборы из 0 и 1. |
}} | }} | ||
{{main | 0-1 принцип}} | {{main | 0-1 принцип}} | ||
Версия 14:21, 30 мая 2012
| Определение: |
| Сеть называется сортирующей (Sorting network), если в результате её работы любая входная последовательность данных преобразуется в монотонно неубывающую. |
Компараторы (сравнивающие устройства)
| Определение: |
| Компаратор (Comparator) — устройство, подключенное к двум проводам, которое упорядочивает текущие значения на проводах. |
Обычно компараторы меньшее значение передают на провод с меньшим номером, но бывают и направленные компараторы, у которых указано направление перемещения.
| Определение: |
| K-компаратор — устройство, упорядочивающее значения на k проводах. |
Компараторы можно располагать в одном слое, если они подключены к разным проводам. В этом случае сравнения будут выполняться параллельно.
Сети
| Определение: |
| Сравнивающая сеть — несколько компараторов, соединенных проводами. Используется для упорядочивания числовых последовательностей. |
| Определение: |
| Глубина сети (depth) — количество слоев в сети. |
| Определение: |
| Размер сети (size) — количество компараторов в сети. |
| Теорема: |
Сеть компараторов является сортирующей тогда и только тогда, когда она сортирует все наборы из 0 и 1. |
См.также
Сортирующие сети для квадратичных сортировок
Источники
- Кормен Глава 28 Сортирующее сети.
- Wikipedia - Sorting networks
