Редактирование: Сортирующие сети

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
== Определение ==
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Сортирующая сеть''' (англ. ''Sorting network'') — метод сортировки, основанный только на сравнениях данных. Схематически изображается в виде параллельных прямых (проводов), соединенных вертикальными линиями (сравнивающими устройствами). Особенность сети сортировки в том, что сравнения выполняются независимо от предыдущих. Кроме того, сравнения могут выполняться одновременно.
+
Сеть называется '''сортирующей (Sorting network)''', если в результате её работы любая входная последовательность данных преобразуется в монотонно неубывающую.
 
}}
 
}}
 +
[[Image:Sorting-network-comparator-demonstration..png|thumb|130px|Сортирующая сеть с 2 проводами]]
 +
 +
  
{| cellpadding="3"
 
| || [[Файл:Network.png|thumb|right|350px|Схематическое изображение сортирующей сети для последовательности из 4 чисел. Глубина сети: 4. Размер сети: 5 ]] || [[Файл:Sort1.png|thumb|right|400px|Процесс сортировки числовой последовательности (3, 2, 4, 1)]]
 
|}
 
  
 
== Компараторы (сравнивающие устройства) ==
 
== Компараторы (сравнивающие устройства) ==
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Компаратор''' (англ. ''Comparator'') — устройство, подключенное к двум проводам, которое упорядочивает текущие значения на проводах.
+
'''Компаратор (Comparator)''' — устройство, подключенное к двум проводам, которое упорядочивает текущие значения на проводах.
 
}}
 
}}
{| cellpadding="3"
 
| [[Файл:Comp1.png|thumb|500px|Компаратор, подключенный к проводам <tex>i, j</tex>. Входные данные: <tex>x, y</tex>. Выходные данные: <tex>\min(x, y), \max(x, y)</tex>.]]
 
|}
 
  
 
Обычно компараторы меньшее значение передают на провод с меньшим номером, но бывают и направленные компараторы, у которых указано направление перемещения.
 
Обычно компараторы меньшее значение передают на провод с меньшим номером, но бывают и направленные компараторы, у которых указано направление перемещения.
 
{{Определение
 
|definition =
 
'''K-компаратор''' (англ. ''K-comparator'') — устройство, упорядочивающее значения на <tex>k</tex> проводах.
 
}}
 
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Пусть глубина входного провода сети равна нулю. Если глубины входных проводов компаратора равны <tex>x</tex> и <tex>y</tex>, то глубина его выходных проводов равна <tex>\max(x, y) + 1 </tex>. '''Глубина компаратора''' (англ. ''Depth of comparator'') — величина, равная глубине его выходных проводов.
+
'''K-компаратор''' — устройство, упорядочивающие значения на '''k''' проводах.
 
}}
 
}}
  
Компараторы можно располагать на одной глубине, если они подключены к разным проводам. В этом случае сравнения будут выполняться параллельно.
+
Компараторы можно располагать в одном слое, если они подключены к разным проводам. В этом случае сравнения будут выполняться параллельно.
 
 
 
== Сети ==
 
== Сети ==
 
Введем ряд определений, характеризующих сеть компараторов:
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Слой сети''' (англ. ''layer'') множество компараторов, имеющих одинаковую глубину.
+
'''Сравнивающая сеть''' — несколько компараторов, соединенных проводами. Используется для
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Глубина сети''' (англ. ''depth'') — количество слоев в сети.
+
'''Глубиной сети (depth)''' называется количество слоев в сети.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Размер сети''' (англ. ''size'') — количество компараторов в сети.
+
'''Размером сети (size)''' называется количество компараторов в сети.
 
}}
 
}}
 
Для того, чтобы сортирующая сеть для <tex>n</tex> входов была корректна, она должна правильно сортировать все <tex>n!</tex> перестановок <tex>n</tex> различных чисел. Также можно сформулировать более сильное утверждение:
 
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Сеть компараторов с <tex>n</tex> входами является сортирующей тогда и только тогда, когда она сортирует <tex>2^n</tex> различных последовательностей из 0 и 1.
+
Сеть является сортирующей тогда и только тогда, когда она сортирует все наборы из 0 и 1.
 
}}
 
}}
 
{{main | 0-1 принцип}}
 
{{main | 0-1 принцип}}
  
 
== См.также ==
 
== См.также ==
*[[Сортирующие сети для квадратичных сортировок]]
+
[[Сортирующие сети для квадратичных сортировок]]
*[[0-1 принцип]]
+
 
*[[Сеть Бетчера]]
+
[[0-1 принцип]]
 +
 
 +
[[Сеть Бетчера]]
 +
 
  
== Источники информации==
+
== Источники ==
* [[wikipedia:Sorting_network | Wikipedia {{---}} Sorting network]]
+
* Кормен Глава 28 Сортирующее сети.
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 799 — 805. — ISBN 5-8489-0857-4
+
* [http://en.wikipedia.org/wiki/Sorting_network Wikipedia - Sorting networks]
* Дональд Э. Кнут Искусство программирования. Том 3. Сортировка и поиск — 2-е изд. — М.: «Вильямс», 2012. — с. 238 — 242. — ISBN 0-201-89685-0
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Сортирующие сети]]
 
[[Категория: Сортирующие сети]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)