Блочная сортировка

Блочная сортировка

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

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

Преимущества: относится к классу быстрых алгоритмов с линейным временем исполнения O(N) (на удачных входных данных).

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

Алгоритм

Если входные элементы подчиняются равномерному закону распределения, то математическое ожидание времени работы алгоритма карманной сортировки является линейным. Это возможно благодаря определенным предположениям о входных данных. При карманной сортировке предполагается, что входные данные равномерно распределены на отрезке [0, 1).

Идея алгоритма заключается в том, чтобы разбить интервал [0, 1) на n одинаковых отрезков (карманов), и разделить по этим карманам n входных величин. Поскольку входные числа равномерно распределены, предполагается, что в каждый карман попадет небольшое количество чисел. Затем последовательно сортируются числа в карманах. Отсортированный массив получается путем последовательного перечисления элементов каждого кармана.

Наглядная реализация блочной сортировки

 

Псевдокод блочной сортировки на С++

01	//Блочная сортировка

02	function bucket-sort(A, n) is

03	buckets ← новый массив из n пустых элементов

04	for i = 0 to (length(A)-1) do

05	вставить A[i] в конец массива buckets[msbits(A[i], k)]

06	for i = 0 to n - 1 do

07	next-sort(buckets[i])

08	return Конкатенация массивов buckets[0], ..., buckets[n-1]

09

10	/** На вход функции bucket-sort подаются сортируемый массив (список, коллекция и т.п.) A и количество блоков - n.

11

12	* Массив buckets представляет собой массив массивов (массив списков, массив коллекций и т.п.), подходящих по природе к элементам A.

13

14

* Функция msbits(x,k) тесно связана с количеством блоков - n (возвращает значение от 0 до n), и, в общем случае, возвращает k наиболее значимых битов из x (floor(x/2^(size(x)-k))). В качестве msbits(x,k) может быть использованы разнообразные функции, подходящие к природе сортируемых данных и позволяющие разбить массив A на n блоков. Например, для символово A-Z это может быть сопоставление буквам чисел 0-25, или возврат кода первой буквы (0-255) для ASCII набора символов; для чисел [0, 1) это может быть функция floor(n*A[i]), а для произвольного набора чисел в интервале [a, b) - функция floor(n*(A[i]-a)/(b-a)).

15

16

* Функция next-sort также реализует алгоритм сотрировки для каждого созданного на первом этапе блока. Рекурсивное использование bucket-sort в качестве next-sort превращает данный алгоритм в поразрядную сортировку. В случае n = 2 соответствует быстрой сортировке (хотя и с потенцильно плохим выбором опорного элемента).

17

*/

18	/******************/

Вывод по блочной сортировке

Оценим сложность алгоритма блочной сортировки для случая, при котором в качестве алгоритма сортировки блоков (next-sort из псевдокода) используется сортировка вставками. Для оценки сложности алгоритма введём случайную величину ni, обозначающую количество элементов, которые попадут в карман B[i]. Время работы сортировки вставками равно O(n^2).