WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте
Простая сеть сортировки 4х элементов с 5 модулями компараторов. Справа показан процесс сортировки элементов <3,2,4,1>.

Сеть сортиро́вки (англ. 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.

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии