Ковшовая сортировка - Bucket sort

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

Ковшовая сортировка

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

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

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

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

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

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

Псевдокод

функция bucketSort (массив; k) является    buckets ← новый массив из k пустых списков M ← максимальное значение ключа в массиве за я = 1 к длина (массив) делать        вставлять массив [я] в ковши [этаж (k × массив [i] / M)]    за я = 1 к k делать        nextSort (сегменты [i]) возвращаться объединение сегментов [1], ...., сегментов [k]

Здесь множество это массив для сортировки и k - количество используемых ведер. Максимальное значение ключа можно вычислить в линейное время просмотрев все ключи один раз. В функция пола должен использоваться для преобразования числа с плавающей запятой в целое число. Функция nextSort это функция сортировки, используемая для сортировки каждой корзины. Обычно вставка сортировки будут использоваться, но можно использовать и другие алгоритмы. С помощью bucketSort сам как nextSort производит родственника радиальная сортировка; в частности, дело п = 2 соответствует быстрая сортировка (хотя потенциально с плохим выбором опорных точек).

Анализ

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

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

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

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

${\displaystyle {\begin{aligned}E(n_{i}^{2})&=E\left(\sum _{j=1}^{n}X_{ij}\sum _{k=1}^{n}X_{ik}\right)\\&=E\left(\sum _{j=1}^{n}\sum _{k=1}^{n}X_{ij}X_{ik}\right)\\&=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)\end{aligned}}}$

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

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

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

При суммировании это будет

${\displaystyle 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}}}}$

Наконец, сложность будет ${\displaystyle 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)}$.

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

Оптимизация

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

Варианты

Общая сортировка по ведру

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

ProxmapSort

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

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

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

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

Сорт почтальона

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

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

В сортировка в случайном порядке^[6] это вариант сортировки по сегментам, которая начинается с удаления первой 1/8 части п элементы для сортировки, рекурсивно сортирует их и помещает в массив. Это создает п/ 8 «ведер», по которым распределяются оставшиеся 7/8 предметов. Затем каждое «ведро» сортируется, и «ведра» объединяются в отсортированный массив.

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

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

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

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

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

Рекомендации

1. Томас Х. Кормен; Чарльз Э. Лейзерсон; Рональд Л. Ривест & Клиффорд Штайн. Введение в алгоритмы. Сортировка ведром выполняется в среднем за линейное время. Как и сортировка с подсчетом, сортировка по ведру выполняется быстро, потому что предполагает что-то о вводе. В то время как подсчетная сортировка предполагает, что входные данные состоят из целых чисел в небольшом диапазоне, сегментная сортировка предполагает, что входные данные генерируются случайным процессом, который равномерно распределяет элементы по интервалу [0,1). Идея сортировки ведром состоит в том, чтобы разделить интервал [0, 1) в п равные по размеру подинтервалы или сегменты, а затем распределите п введите числа в ведра. Поскольку входы равномерно распределены по [0, 1), мы не ожидаем, что в каждую корзину попадет много чисел. Чтобы получить результат, мы просто сортируем числа в каждом сегменте, а затем просматриваем сегменты по порядку, перечисляя элементы в каждом.
2. Корвин, Э. и Логар, А. «Сортировка за линейное время - вариации на сортировке по ведру». Журнал компьютерных наук в колледжах, 20, 1, с.197–202. Октябрь 2004 г.
3. Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, и Клиффорд Штайн. Введение в алгоритмы, Второе издание. MIT Press и McGraw-Hill, 2001. ISBN  0-262-03293-7. Раздел 8.4: Сортировка по корзине, стр. 174–177.
4. Словарь алгоритмов и структур данных NIST: сортировка гистограмм
5. http://www.rrsd.com/psort/cuj/cuj.htm
6. Революционный новый сорт от Джона Коэна 26 ноября 1997 г.

• Пол Э. Блэк "Почтальон" из Словарь алгоритмов и структур данных в NIST.
• Роберт Рэми '"Почтальон" Журнал пользователей C Август 1992 г.
• Словарь алгоритмов и структур данных NIST: сегментная сортировка

внешняя ссылка

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