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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Сортировка пузырьком)
(Сортировка вставками)
Строка 11: Строка 11:
 
[[Файл:Bubblesort.png]]
 
[[Файл:Bubblesort.png]]
  
=== Сортировка вставками ===
+
=== [[Сортировка вставками]] ===
  
 
[[Файл:Insertsort.png]]
 
[[Файл:Insertsort.png]]

Версия 22:43, 14 июня 2011

Эта статья находится в разработке!

Рассмотрим модели сортирующих сетей для квадратичных сортировок.

Сортирующие сети с последовательной сортировкой

На один слой будем устанавливать только один компаратор. Все последующие сети получаются простым моделированием соответствующих сортировок.

Сортировка пузырьком

Bubblesort.png

Сортировка вставками

Insertsort.png

Сортировка выбором

Choosesort.png

Сортирующие сети с параллельной сортировкой

На один слой будем устанавливать несколько компараторов.

Сортировка пузырьком и вставками

Интересно два факта:

  • Если сжать последовательные сортирующие сети пузырьком и вставками, то результат будет одним и тем же.
  • В результирующей сети будет [math](2n - 3)[/math] слоев.

Parralelsort.png

Сортировка выбором

Choosesortparralel.png

Источники

  • Дональд Э. Кнут. Искусство программирования. Том 3. Сортировка и Поиск.