Сортировка по сегментам

редактировать

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

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

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

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

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

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

Содержание

1 Псевдокод
2 Анализ
- 2.1 Анализ наихудшего случая
- 2.2 Анализ среднего случая
3 Оптимизация
4 Варианты
- 4.1 Общая сортировка по корзине
- 4.2 ProxmapSort
- 4.3 Сортировка гистограммы
- 4.4 Сортировка почтальона
- 4.5 Сортировка в случайном порядке
5 Сравнение с другими алгоритмами сортировки
6 Ссылки
7 Внешние ссылки

Псевдокод

функция bucketSort (array, k) is buckets ← new массив из k пустых списков M ← максимальное значение ключа в массиве для i = 1 от до length (array) do вставить массив [i] в сегменты [ floor (k × array [i] / M)] для i = 1 tok donextSort (buckets [i]) return объединение сегментов [1],...., ведро s [k]

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

Анализ

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

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

Среднее -case analysis

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

E (ni 2) = E (∑ j = 1 n X ij ∑ k = 1 n X ik) = E (∑ j = 1 n ∑ k = 1 n X ij X ik) = E (∑ J знак равно 1 N Икс ij 2) + E (∑ 1 ≤ J, К ≤ N ∑ J ≠ К Икс ij X ik) {\ Displaystyle {\ begin {выровнено} 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} \ справа) \ end {align}}}

{\ displaystyle {\ begin {align} 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} \ сумма _ {j \ neq k} X_ {ij} X_ {ik} \ right) \ end {выравнивается}}}

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

Е (Икс ij 2) = 1 2 ⋅ (1 К) + 0 2 ⋅ (1–1 К) = 1 К {\ 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} ^ {2}) = 1 ^ {2} \ cdot \ left ({\ frac {1} {k}} \ right) + 0 ^ {2} \ cdot \ left (1 - {\ frac {1} {k}} \ right) = {\ frac {1} {k}}}

E (Икс ij X ik) = 1 ⋅ (1 k) (1 k) = 1 k 2 {\ displaystyle E (X_ {ij} X_ {ik}) = 1 \ cdot \ left ({\ frac {1} {k}} \ right) \ left ({\ frac {1} {k}} \ right) = {\ frac {1} {k ^ {2}}}}

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

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

E (∑ j = 1 n X ij 2) + E (∑ 1 ≤ j, k ≤ n ∑ j ≠ k X ij X ik) = n ⋅ 1 k + n (n - 1) ⋅ 1 К 2 знак равно N 2 + NK - NK 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 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 (∑ i = 1 K E (ni 2)) = O (∑ i = 1 kn 2 + nk - nk 2) = O (n 2 k + n) {\ 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 \ 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) {\ displaystyle O (k)}$ $O (k)$ времени. Следовательно, общая сложность равна $O (n + n 2 k + k) {\ displaystyle O \ left (n + {\ frac {n ^ {2}} {k}} + k \ right)}$ ${\ displaystyle O \ left (n + {\ frac {n ^ {2}} {k}} + k \ right)}$ . Обратите внимание, что если k выбрано равным $k = Θ (n) {\ displaystyle k = \ Theta (n)}$ ${\ displaystyle k = \ Theta (n)}$ , то сортировка по сегментам выполняется в $O (n) {\ displaystyle O (n)}$ $O (n)$ среднее время при равномерно распределенном вводе.

Оптимизация

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

Варианты

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

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

ProxmapSort

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

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

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

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