Сеть сортиро́вки (англ. sorting network) — класс алгоритмических методов сортировки, в которых последовательность сравнений не зависит от результатов предыдущих сравнений.
Часто изображаются в виде сети, горизонтальные линии в которой соответствуют передаче сортируемого элемента слева направо, а вертикальными соединениями пар линий обозначены так называемые «модули компараторов», имеющие два входа и два выхода. Модуль компаратора производит сравнение элементов на входе и обменивает их местами таким образом, чтобы на нижнем выходе было, например, большее число. Сети сортировки допускают эффективную аппаратную реализацию.
Возможно представление в виде сети сортировки различных алгоритмов внутренней сортировки.
Топологически структура сетей, созданных на базе алгоритмов сортировки пузырьком и сортировки вставками, близка. Если расположить независимые модули компараторов друг над другом, можно получить сеть, выполняющую несколько сравнений одновременно.
Этот раздел не завершён. |