Сортирующие сети — различия между версиями

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

Текущая версия на 08:25, 22 мая 2017

Определение[править]

Определение:
Сортирующая сеть (англ. Sorting network) — метод сортировки, основанный только на сравнениях данных. Схематически изображается в виде параллельных прямых (проводов), соединенных вертикальными линиями (сравнивающими устройствами). Особенность сети сортировки в том, что сравнения выполняются независимо от предыдущих. Кроме того, сравнения могут выполняться одновременно.


Схематическое изображение сортирующей сети для последовательности из 4 чисел. Глубина сети: 4. Размер сети: 5
Процесс сортировки числовой последовательности (3, 2, 4, 1)

Компараторы (сравнивающие устройства)[править]

Определение:
Компаратор (англ. Comparator) — устройство, подключенное к двум проводам, которое упорядочивает текущие значения на проводах.
Компаратор, подключенный к проводам [math]i, j[/math]. Входные данные: [math]x, y[/math]. Выходные данные: [math]\min(x, y), \max(x, y)[/math].

Обычно компараторы меньшее значение передают на провод с меньшим номером, но бывают и направленные компараторы, у которых указано направление перемещения.


Определение:
K-компаратор (англ. K-comparator) — устройство, упорядочивающее значения на [math]k[/math] проводах.


Определение:
Пусть глубина входного провода сети равна нулю. Если глубины входных проводов компаратора равны [math]x[/math] и [math]y[/math], то глубина его выходных проводов равна [math]\max(x, y) + 1 [/math]. Глубина компаратора (англ. Depth of comparator) — величина, равная глубине его выходных проводов.


Компараторы можно располагать на одной глубине, если они подключены к разным проводам. В этом случае сравнения будут выполняться параллельно.

Сети[править]

Введем ряд определений, характеризующих сеть компараторов:

Определение:
Слой сети (англ. layer) — множество компараторов, имеющих одинаковую глубину.


Определение:
Глубина сети (англ. depth) — количество слоев в сети.


Определение:
Размер сети (англ. size) — количество компараторов в сети.


Для того, чтобы сортирующая сеть для [math]n[/math] входов была корректна, она должна правильно сортировать все [math]n![/math] перестановок [math]n[/math] различных чисел. Также можно сформулировать более сильное утверждение:

Теорема:
Сеть компараторов с [math]n[/math] входами является сортирующей тогда и только тогда, когда она сортирует [math]2^n[/math] различных последовательностей из 0 и 1.
Основная статья: 0-1 принцип

См.также[править]

Источники информации[править]

  • Wikipedia — Sorting network
  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 799 — 805. — ISBN 5-8489-0857-4
  • Дональд Э. Кнут Искусство программирования. Том 3. Сортировка и поиск — 2-е изд. — М.: «Вильямс», 2012. — с. 238 — 242. — ISBN 0-201-89685-0