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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
 +
 +
 
== Определение ==
 
== Определение ==
 
{{Определение
 
{{Определение
Строка 4: Строка 7:
 
Сеть называется '''сортирующей (Sorting network)''', если в результате её работы любая  последовательность входных данных преобразуется в монотонно неубывающую.
 
Сеть называется '''сортирующей (Sorting network)''', если в результате её работы любая  последовательность входных данных преобразуется в монотонно неубывающую.
 
}}
 
}}
 +
{| cellpadding="10"
 +
| || [[Файл:Network.png|thumb|right|300px|Схематическое изображение сортирующей сети для последовательности из 4 чисел. Глубина сети: 4. Размер сети: 5 ]] || [[Файл:Sort.png|thumb|right|300px|Процесс сортировки числовой последовательности (3, 2, 4, 1)]]
 +
|}
  
 
== Компараторы (сравнивающие устройства) ==
 
== Компараторы (сравнивающие устройства) ==

Версия 17:25, 30 мая 2012


Определение

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

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

Определение:
Компаратор (Comparator) — устройство, подключенное к двум проводам, которое упорядочивает текущие значения на проводах.


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


Определение:
K-компаратор — устройство, упорядочивающее значения на k проводах.


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

Сравнивающие сети

Определение:
Сравнивающая сеть — несколько компараторов, соединенных проводами. Используется для упорядочивания числовых последовательностей.


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


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


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

См.также

Источники

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