Сеть сортировки

Сеть сортиро́вки (англ. sorting network) — класс алгоритмических методов сортировки, в которых последовательность сравнений не зависит от результатов предыдущих сравнений.

Часто изображаются в виде сети, горизонтальные линии в которой соответствуют передаче сортируемого элемента слева направо, а вертикальными соединениями пар линий обозначены так называемые «модули компараторов», имеющие два входа и два выхода. Модуль компаратора производит сравнение элементов на входе и обменивает их местами таким образом, чтобы на нижнем выходе было, например, большее число. Сети сортировки допускают эффективную аппаратную реализацию.

Введение

Сети вставки и выбора

Возможно представление в виде сети сортировки различных алгоритмов внутренней сортировки.

Топологически структура сетей, созданных на базе алгоритмов сортировки пузырьком и сортировки вставками, близка. Если расположить независимые модули компараторов друг над другом, можно получить сеть, выполняющую несколько сравнений одновременно.

Эффективность сетей

Литература

• Дональд Кнут. Глава *5.3.4. Сети сортировки // Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol. 3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2005. — С. 245 - 273. — ISBN 5-8459-0082-4.
• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд. Глава 27. Сортирующие сети // Алгоритмы: построение и анализ. — 2-e издание. — М.: «Вильямс», 2005. — С. 799 - 822. — ISBN 5-8459-0857-4.

Ссылки

• Sorting Networks
• Sorting Networks
• List of Sorting Networks
• Sorting networks and the END algorithm

Эта страница в последний раз была отредактирована 11 декабря 2021 в 08:38.