Карманная сортировка
Карманная сортировка (Bucket sort) — алгоритм сортировки, основанный на предположении о равномерном распределении входных данных.
Алгоритм сортировки
Принцип работы
- элементы массива входных данных разбиваются на блоков (карманов, корзин).
- каждый из блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения.
- из каждого отсортированного блока данные записываются в массив в порядке разбиения на блоки.
Важно отметить, что разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были больше предыдущего.
Реализация
Существует несколько разных реализаций карманной сортировки.
Рекурсивный bucket sort
Рассмотрим код работы рекурсивной реализации карманной сортировки, на вход которой подаются вещественные числа.
Bucketsort (array,min_element,max_element)
if (array.length < 2 || min_element == max_element )
return array;
initialize buckets <- new array of n empty lists
initialize buckets_minimum
initialize buckets_maximum
range = max_element - min_element;
for i = 0 to array.length - 1
index = int(array[i] * num_buckets / range)
insert array[i] at end buckets[index]
buckets_minimum[i] = minimum ( buckets[index], array[i])
buckets_maximum[i] = maximum ( buckets[index], array[i])
for i = 0 to num_buckets - 1
buckets[i] = Bucketsort (buckets[i],min_bucktes[i],max_buckets[i])
intialize answer
for i = 0 to num_buckets - 1
for k = 0 to buckets[i].length - 1
insert buckets[i][k] аt end answer
return answer
Нерекурсивная реализация
Bucketsort(array)
initialize buckets <- new array of n empty lists
min_element = Infinum
max_element = -Infinum
for i = 0 to array.length - 1
min_element = Min(min_element, array[i])
max_element = Max(max_element, array[i])
range = max_element - min_element;
for i = 0 to array.length - 1
index = int(array[i] * num_buckets / range)
insert array[i] at end buckets[index]
for i = 0 to num_buckets - 1
buckets[i] = quickSort(buckets[i])
intialize answer
for i = 0 to num_buckets - 1
for k = 0 to buckets[i].length - 1
insert buckets[i][k] аt end answer
return answer
Асимптотика
Пусть — количество элементов в массиве, — количество блоков для разбиения.
— случайная величина, обозначающая количество элементов попавших в -ый карман.
, где время работы алгоритма карманной сортировки.
Тоесть, если
Если,
Из приведенных выше формул, видно, что в среднем "карманная сортировка" работает за линейное время.
