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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Сортирующие сети с последовательной сортировкой)
(Сортирующие сети с последовательной сортировкой)
Строка 7: Строка 7:
 
| '''[[Сортировка пузырьком]]''' || '''[[Сортировка вставками]]''' || '''Сортировка выбором'''
 
| '''[[Сортировка пузырьком]]''' || '''[[Сортировка вставками]]''' || '''Сортировка выбором'''
 
|-
 
|-
| [[Файл:Bubblesort.png]] || [[Файл:Insertsort.png]] || [[Файл:Choosesort.png‎]]
+
| [[Файл:Bubblesort.svg]] || [[Файл:Insertsort.png]] || [[Файл:Choosesort.png‎]]
 
|}
 
|}
  

Версия 12:02, 7 июня 2012

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

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

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

Сортировка пузырьком Сортировка вставками Сортировка выбором
Файл:Bubblesort.svg Insertsort.png Choosesort.png

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

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

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

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

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

Parralelsort.png

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

Choosesortparralel.png

Источники

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