Сортирующие сети — различия между версиями
Darkraven (обсуждение | вклад) |
Darkraven (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| + | == Определение == | ||
| + | '''Сортирующая сеть (Sorting network)''' — модель, состоящая из нескольких проводов и сравнивающих устройств, предназначенная для сортировки данных. Схематически изображается в виде параллельных прямых (проводов), соединенных вертикальными линиями (сравнивающими устройствами). Особенность сети в том, что сравнения выполняются независимо от предыдущих. Кроме того, сравнения могут выполняться одновременно. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
{| cellpadding="3" | {| cellpadding="3" | ||
| || [[Файл:Network.png|thumb|right|350px|Схематическое изображение сортирующей сети для последовательности из 4 чисел. Глубина сети: 4. Размер сети: 5 ]] || [[Файл:Sort1.png|thumb|right|400px|Процесс сортировки числовой последовательности (3, 2, 4, 1)]] | | || [[Файл:Network.png|thumb|right|350px|Схематическое изображение сортирующей сети для последовательности из 4 чисел. Глубина сети: 4. Размер сети: 5 ]] || [[Файл:Sort1.png|thumb|right|400px|Процесс сортировки числовой последовательности (3, 2, 4, 1)]] | ||
| Строка 19: | Строка 14: | ||
Обычно компараторы меньшее значение передают на провод с меньшим номером, но бывают и направленные компараторы, у которых указано направление перемещения. | Обычно компараторы меньшее значение передают на провод с меньшим номером, но бывают и направленные компараторы, у которых указано направление перемещения. | ||
| − | |||
| − | |||
'''K-компаратор''' — устройство, упорядочивающее значения на '''k''' проводах. | '''K-компаратор''' — устройство, упорядочивающее значения на '''k''' проводах. | ||
| − | |||
{{Определение | {{Определение | ||
| Строка 32: | Строка 24: | ||
== Сети == | == Сети == | ||
| + | |||
| + | Введем ряд определений, характеризующих сеть компараторов: | ||
| + | |||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| Строка 44: | Строка 39: | ||
'''Размер сети (size)''' — количество компараторов в сети. | '''Размер сети (size)''' — количество компараторов в сети. | ||
}} | }} | ||
| + | |||
| + | Для того, чтобы сортирующая сеть для <tex>n</tex> входов была корректна, она должна правильно сортировать все <tex>n!</tex> перестановок <tex>n</tex> различных чисел. Также можно сформулировать более сильное утверждение: | ||
{{Теорема | {{Теорема | ||
Версия 20:28, 10 июня 2012
Определение
Сортирующая сеть (Sorting network) — модель, состоящая из нескольких проводов и сравнивающих устройств, предназначенная для сортировки данных. Схематически изображается в виде параллельных прямых (проводов), соединенных вертикальными линиями (сравнивающими устройствами). Особенность сети в том, что сравнения выполняются независимо от предыдущих. Кроме того, сравнения могут выполняться одновременно.
Компараторы (сравнивающие устройства)
| Определение: |
| Компаратор (Comparator) — устройство, подключенное к двум проводам, которое упорядочивает текущие значения на проводах. |
Обычно компараторы меньшее значение передают на провод с меньшим номером, но бывают и направленные компараторы, у которых указано направление перемещения.
K-компаратор — устройство, упорядочивающее значения на k проводах.
| Определение: |
| Пусть глубина входного провода сети равна нулю. Если глубины входных проводов компаратора равны и , то глубина его выходных проводов равна . Глубина компаратора — величина, равная глубине его выходных проводов. |
Компараторы можно располагать на одной глубине, если они подключены к разным проводам. В этом случае сравнения будут выполняться параллельно.
Сети
Введем ряд определений, характеризующих сеть компараторов:
| Определение: |
| Слой сети — множество компараторов, имеющих одинаковую глубину. |
| Определение: |
| Глубина сети (depth) — количество слоев в сети. |
| Определение: |
| Размер сети (size) — количество компараторов в сети. |
Для того, чтобы сортирующая сеть для входов была корректна, она должна правильно сортировать все перестановок различных чисел. Также можно сформулировать более сильное утверждение:
| Теорема: |
Сеть компараторов с входами является сортирующей тогда и только тогда, когда она сортирует различных последовательностей из 0 и 1. |
См.также
Источники
- Sorting network — Wikipedia
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 799 — 805. — ISBN 5-8489-0857-4
- Дональд Э. Кнут Искусство программирования. Том 3. Сортировка и поиск — 2-е изд. — М.: «Вильямс», 2012. — с. 238 — 242. — ISBN 0-201-89685-0
