Сеть сортировки (англ. sorting network) — класс методов сортировки, в которых последовательность сравнений не зависит от результатов предыдущих сравнений. Часто изображаются в виде сети, горизонтальные линии в которой соответствуют передаче сортируемого элемента слева направо, а вертикальными соединениями пар линий обозначены «модули компараторов», имеющие два входа и два выхода. Модуль компаратора производит сравнение элементов на входе и обменивает их местами таким образом, чтобы на нижнем выходе было большее число. Сети сортировки допускают эффективную реализацию в аппаратуре.
Содержание |
Возможно представление в виде сети сортировки различных алгоритмов внутренней сортировки.
Топологически структура сетей, созданных на базе алгоритмов сортировки пузырьком и сортировки вставками близка. Если расположить независимые модули компараторов друг над другом, можно получить сеть, выполняющую несколько сравнений одновременно.
|
Сеть сортировки, построенная на базе сортировки пузырьком
|
| Алгоритмы сортировки | |
|---|---|
| Теория |
Сложность • О-нотация • Отношение порядка • Типы сортировки: Устойчивая • Внутренняя • Внешняя |
| Алгоритмы |
Обменные: Пузырьком • Перемешиванием • Гномья • Быстрая • Расчёской • Выбором: Выбором • Пирамидальная • Вставками: Вставками • Шелла • Деревом • Слиянием: Слиянием • Без дополнительной памяти • Без сравнений: Подсчётом • Поразрядная • Блочная • Гибридные: Introsort • Timsort • Прочее: Топологическая • Сети • Непрактичные: Bogosort • Stooge sort • Глупая • Блинная |
Алгоритм сортировки 3 значений, сортировки картофеля своими руками, лорин г сортировки и системы сортировки м наука 1983, сортировки рыбы в ручную.
Инсталляция (ПО), Гайнан Хайри, Файл:Bitwa na jeziorach Mazurskich 4 IX-7 IX 1914.jpg.
