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

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

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

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

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

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

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

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

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

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

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

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

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

Источники

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