Сортировка ведром

Сортировка ведром

Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность	$O\left(n^{2}\right)$
Средняя производительность	$O\left(n+{\frac {n^{2}}{k}}+k\right)$, где k — количество сегментов. $O(n),{\text{when }}k\approx n$.
Наихудшая пространственная сложность	$O(n+k)$

Элементы распределяются по контейнерам

Затем элементы сортируются внутри каждого контейнера.

Сортировка сегментами или сортировка ячеек — это алгоритм сортировки , который работает путем распределения элементов массива по нескольким сегментам. Затем каждая корзина сортируется индивидуально, либо с использованием другого алгоритма сортировки, либо путем рекурсивного применения алгоритма сортировки корзин. Это сортировка по распределению , обобщение сортировки по ячейкам , которая позволяет использовать несколько ключей в сегменте и является двоюродным братом поразрядной сортировки в варианте от наиболее значимого к наименее значимому разряду. Сортировка сегментами может быть реализована с помощью сравнений и, следовательно, также может рассматриваться как алгоритм сортировки сравнением . Вычислительная сложность зависит от алгоритма, используемого для сортировки каждого сегмента, количества используемых сегментов и равномерности распределения входных данных.

Сортировка сегментами работает следующим образом:

1. Настройте массив изначально пустых «ведёр».
2. Scatter : просмотр исходного массива, помещая каждый объект в свою корзину.
3. Отсортируйте каждое непустое ведро.
4. Сбор : посетите сегменты по порядку и поместите все элементы обратно в исходный массив.

Псевдокод

function bucketSort(array, k) is
    buckets ← new array of k empty lists
    M ← 1 + the maximum key value in the array
    for i = 0 to length(array) do
        insert array[i] into buckets[floor(k × array[i] / M)]
    for i = 0 to k do 
        nextSort(buckets[i])
    return the concatenation of buckets[0], ...., buckets[k]

Пусть массив обозначает массив, который нужно отсортировать, а k обозначает количество используемых сегментов. Максимальное значение ключа можно вычислить за линейное время , однократно перебрав все ключи. Функция Floor должна использоваться для преобразования плавающего числа в целое число (и, возможно, также для приведения типов данных). Функция nextSort — это функция сортировки, используемая для сортировки каждого сегмента. Обычно используется сортировка вставками , но можно использовать и другие алгоритмы, например сортировку выбором или сортировку слиянием . Использование BucketSort в качестве nextSort создает родственник поразрядной сортировки ; в частности, случай n = 2 соответствует быстрой сортировке (хотя потенциально с плохим выбором опорной точки).

Анализ

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

Когда входные данные содержат несколько ключей, расположенных близко друг к другу (кластеризация), эти элементы, скорее всего, будут помещены в один и тот же сегмент, в результате чего некоторые сегменты будут содержать больше элементов, чем в среднем. Наихудший сценарий возникает, когда все элементы помещаются в одно ведро. Тогда общая производительность будет зависеть от алгоритма, используемого для сортировки каждого сегмента, например $O(n^{2})$ сортировка вставкой или $O(n\log(n))$ алгоритмы сортировки сравнением , такие как сортировка слиянием .

Анализ среднего случая

Рассмотрим случай, когда входные данные распределены равномерно. Первый шаг — инициализация сегментов и поиск максимального значения ключа в массиве — можно выполнить в $O(n)$ время. Если деление и умножение можно производить за постоянное время, то раскидывание каждого элемента по своему ведру тоже стоит $O(n)$. Предположим, что для сортировки каждого сегмента используется сортировка вставками, тогда затраты на третий шаг $O(\textstyle \sum _{i=1}^{k}\displaystyle n_{i}^{2})$, где $n_{i}$ длина сегмента индексируется $i$. Поскольку речь идет о среднем времени, ожидание $E(n_{i}^{2})$ вместо этого необходимо оценить. Позволять $X_{ij}$ быть случайной величиной, которая $1$ если элемент $j$ помещается в ведро $i$, и $0$ в противном случае. У нас есть $n_{i}=\sum _{j=1}^{n}X_{ij}$. Поэтому,

${\begin{aligned}E(n_{i}^{2})&=E\left(\sum _{j=1}^{n}X_{ij}\sum _{l=1}^{n}X_{il}\right)\\&=E\left(\sum _{j=1}^{n}\sum _{l=1}^{n}X_{ij}X_{il}\right)\\&=E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,l\leq n}\sum _{j\neq l}X_{ij}X_{il}\right)\end{aligned}}$

Последняя строка разделяет суммирование на случай $j=l$ и дело $j\neq l$. Поскольку вероятность того, что объект будет распределен по ведру $i$ является $1/k$, $X_{ij}$ равно 1 с вероятностью $1/k$ и 0 в противном случае.

$E(X_{ij}^{2})=1^{2}\cdot \left({\frac {1}{k}}\right)+0^{2}\cdot \left(1-{\frac {1}{k}}\right)={\frac {1}{k}}$

$E(X_{ij}X_{ik})=1\cdot \left({\frac {1}{k}}\right)\left({\frac {1}{k}}\right)={\frac {1}{k^{2}}}$

При суммировании получится

$E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k\leq n}\sum _{j\neq k}X_{ij}X_{ik}\right)=n\cdot {\frac {1}{k}}+n(n-1)\cdot {\frac {1}{k^{2}}}={\frac {n^{2}+nk-n}{k^{2}}}$

Наконец, сложность будет $O\left(\sum _{i=1}^{k}E(n_{i}^{2})\right)=O\left(\sum _{i=1}^{k}{\frac {n^{2}+nk-n}{k^{2}}}\right)=O\left({\frac {n^{2}}{k}}+n\right)$.

Последний шаг сортировки сегментов, который объединяет все отсортированные объекты в каждом сегменте, требует $O(k)$ время. Таким образом, общая сложность равна $O\left(n+{\frac {n^{2}}{k}}+k\right)$. Обратите внимание, что если k выбрано равным $k=\Theta (n)$, затем запускается сегментная сортировка $O(n)$ среднее время при равномерном распределении входных данных.

Оптимизации

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

Если входное распределение известно или может быть оценено, часто можно выбрать сегменты с постоянной плотностью (а не просто с постоянным размером). Это позволяет $O(n)$ средняя временная сложность даже без равномерно распределенных входных данных.

Варианты

Общая сортировка сегментов

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

ПроксмапСорт

Основная статья: Сортировка Proxmap

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

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

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

сортировка почтальона

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

Сортировка в случайном порядке

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

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

Сортировку сегментами можно рассматривать как обобщение сортировки по счету ; Фактически, если размер каждого сегмента равен 1, то сортировка сегментов вырождается в сортировку с подсчетом. Переменный размер сегмента сортировки сегментов позволяет использовать память O( n ) вместо памяти O( M ), где M — количество различных значений; взамен он отказывается от подсчета сортировки O( n + M худшего поведения ).

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

алгоритм n -сторонний сортировки слиянием также начинается с распределения списка на n подсписков и сортировки каждого из них; однако подсписки, созданные сортировкой слиянием, имеют перекрывающиеся диапазоны значений, поэтому их нельзя повторно объединить путем простой конкатенации, как при сортировке сегментов. Вместо этого они должны чередоваться с помощью алгоритма слияния. Однако эти дополнительные расходы уравновешиваются более простой фазой разброса и возможностью гарантировать, что каждый подсписок имеет одинаковый размер, обеспечивая хорошую временную привязку для наихудшего случая.

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

Ссылки

• Пол Э. Блэк «Сортировка почтальона» из Словаря алгоритмов и структур NIST данных .
• Роберт Рэми , «Сортировка почтальона» , журнал C Users Journal, август 1992 г.
• Словарь алгоритмов и структур данных NIST: сортировка по корзинам

Внешние ссылки

• Код сортировки сегментов для Ansi C
• Вариант сегментной сортировки с демонстрацией