Введение

Алгоритм сортировки

Сортировка подсистемами (или сортировка по корзинам) — это алгоритм сортировки, работающий путем распределения элементов массива по нескольким подсистемам (корзинам). Каждая подсистема затем сортируется индивидуально, либо с использованием другого алгоритма сортировки, либо рекурсивным применением алгоритма сортировки подсистемами. Это распределяющая сортировка, обобщение сортировки «pigeonhole» (сортировки ячейками), допускающая несколько ключей в каждой подсистеме, и является разновидностью поразрядной сортировки, работающей от старшего к младшему разряду. Сортировку подсистемами можно реализовать с использованием сравнений и, следовательно, рассматривать как алгоритм сортировки сравнением. Вычислительная сложность зависит от алгоритма, используемого для сортировки каждой подсистемы, количества используемых подсистем и равномерности распределения входных данных. Сортировка подсистемами работает следующим образом:
Создайте массив изначально пустых "подсистем". Распределение: пройдитесь по исходному массиву, помещая каждый элемент в соответствующую подсистему. Отсортируйте каждую непустую подсистему. Сборка: пройдитесь по подсистемам в порядке возрастания и верните все элементы в исходный массив.

Анализ наихудшего сценария

Когда входные данные содержат несколько ключей, расположенных близко друг к другу (кластеризация), эти элементы с большой вероятностью попадут в один и тот же бакет, что приведет к тому, что некоторые бакеты будут содержать больше элементов, чем в среднем. В наихудшем случае все элементы окажутся в одном бакете. В этом случае общая производительность будет определяться алгоритмом, используемым для сортировки каждого бакета, например, сортировкой вставками или алгоритмами сортировки сравнением, такими как сортировка слиянием.

Общий сортировщик

Наиболее распространенный вариант сортировки в корзинах работает со списком из n числовых входных данных в диапазоне от нуля до некоторого максимального значения M и делит диапазон значений на n корзин, каждая из которых имеет размер M/n. Если каждая корзина сортируется с использованием сортировки вставками, то можно показать, что сортировка выполняется в среднем за линейное время (где усреднение производится по всем возможным входным данным). Однако производительность этой сортировки снижается при кластеризации: если многие значения оказываются близкими друг к другу, они все попадают в одну корзину и сортируются медленно. Это ухудшение производительности избегается в оригинальном алгоритме сортировки в корзинах, предполагая, что входные данные генерируются случайным процессом, который равномерно распределяет элементы по интервалу [0,1).

ProxmapSort (по умолчанию)

Подобно обычной сортировке в корзины, описанной выше, ProxmapSort работает путем разделения массива ключей на подмассивы с использованием функции "ключевой карты", которая сохраняет частичный порядок ключей. По мере добавления каждого ключа в свой подмассив используется сортировка вставками для поддержания порядка в этом подмассиве, что приводит к тому, что весь массив оказывается отсортированным после завершения работы ProxmapSort. ProxmapSort отличается от сортировки в корзины тем, что использует ключевую карту для приблизительного размещения данных в том месте, где они должны находиться в отсортированном порядке, создавая "proxmap" – карту близости ключей.

Сортировка гистограммы

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

Почтовый.

Почтовый сортировщик — это вариант алгоритма сортировки разрядами, использующий иерархическую структуру элементов, обычно описываемую набором атрибутов. Этот алгоритм применяется в почтовых отделениях для сортировки писем: сначала почта разделяется на внутреннюю и международную, затем — по штатам, провинциям или территориям, далее — по почтовым отделениям назначения, затем — по маршрутам и т.д. Поскольку ключи не сравниваются между собой, время сортировки составляет O(cn), где c зависит от размера ключа и количества корзин. Это аналогично сортировке разрядами, работающей "сверху вниз" или "начиная со старшего разряда".

Смешивание

Сортировка перемешиванием — это вариант сортировки по ведрам, который начинается с удаления первых 1/8 из n элементов, подлежащих сортировке, рекурсивной сортировки этих элементов и помещения их в массив. Это создает n/8 "ведер", в которые распределяются оставшиеся 7/8 элементов. Каждое "ведро" затем сортируется, и "ведра" объединяются в отсортированный массив.

Сравнение с другими алгоритмами сортировки

Сортировка по ведрам может рассматриваться как обобщение сортировки подсчётом; фактически, если размер каждого ведра равен 1, то сортировка по ведрам вырождается в сортировку подсчётом. Переменный размер ведра в сортировке по ведрам позволяет использовать память O(n) вместо памяти O(M), где M — количество различных значений; в обмен на это теряется гарантированная сложность O(n + M) в худшем случае, присущая сортировке подсчётом. Сортировка по ведрам с двумя ведрами по сути является вариантом быстрой сортировки, в котором опорный элемент всегда выбирается как среднее значение диапазона значений. Хотя этот выбор эффективен для равномерно распределённых данных, другие способы выбора опорного элемента в быстрой сортировке, такие как случайный выбор, делают её более устойчивой к скоплениям в распределении входных данных. Алгоритм n-путевого слияния также начинается с распределения списка на n подсписков и сортировки каждого из них; однако подсписки, создаваемые слиянием, имеют перекрывающиеся диапазоны значений и поэтому не могут быть объединены простым конкатенированием, как в сортировке по ведрам. Вместо этого их необходимо перемежать алгоритмом слияния. Однако эти дополнительные затраты компенсируются более простой фазой распределения и возможностью гарантировать, что каждый подсписок имеет одинаковый размер, что обеспечивает хорошую оценку времени в худшем случае. Поразрядная сортировка сверху вниз может рассматриваться как частный случай сортировки по ведрам, в котором как диапазон значений, так и количество ведер ограничены степенью двойки. Следовательно, размер каждого ведра также является степенью двойки, и процедуру можно применять рекурсивно. Этот подход может ускорить фазу распределения, поскольку для определения ведра необходимо проверять только префикс битового представления каждого элемента.