Interested Article - Сеть сортировки
![](/images/005/908/5908814/1.jpg?rand=370079)
![](https://cdn.wafarin.com/avatars/3feb2d8fe13b4e9c3c81de0734257103.jpg)
- 2020-12-31
- 1
![](/images/005/908/5908814/1.jpg?rand=223211)
Сеть сортиро́вки ( англ. sorting network ) — класс алгоритмических методов сортировки, в которых последовательность сравнений не зависит от результатов предыдущих сравнений.
Часто изображаются в виде сети, горизонтальные линии в которой соответствуют передаче сортируемого элемента слева направо, а вертикальными соединениями пар линий обозначены так называемые «модули компараторов», имеющие два входа и два выхода. Модуль компаратора производит сравнение элементов на входе и обменивает их местами таким образом, чтобы на нижнем выходе было, например, большее число. Сети сортировки допускают эффективную аппаратную реализацию.
Введение
![](/images/005/908/5908814/2.jpg?rand=145103)
Сети вставки и выбора
Возможно представление в виде сети сортировки различных алгоритмов внутренней сортировки.
Топологически структура сетей, созданных на базе алгоритмов сортировки пузырьком и сортировки вставками , близка. Если расположить независимые модули компараторов друг над другом, можно получить сеть, выполняющую несколько сравнений одновременно.
![]() |
![]() |
![]() |
Эффективность сетей
Литература
- Дональд Кнут . Глава *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. — С. - 822. — ISBN 5-8459-0857-4 .
Ссылки
![](https://cdn.wafarin.com/avatars/3feb2d8fe13b4e9c3c81de0734257103.jpg)
- 2020-12-31
- 1