Карманная сортировка
Карманная сортировка (англ. Bucket sort) — алгоритм сортировки, основанный на предположении о равномерном распределении входных данных.
Алгоритм сортировки
Принцип работы
Для карманной сортировки нужно разбить элементы массива входных данных на блоков (карманов, корзин). Далее каждый из таких блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения. После сортировок внутри каждых блоков данные записываются в массив в порядке разбиения на блоки. При этом нужно учитывать, что данная сортировка работает только в том случае, если разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были больше предыдущего.
Карманная сортировка сильно деградирует при большом количестве мало отличных элементов (большинство элементов попадёт в одну корзину). Поэтому такой тип сортировки использовать, когда велика вероятность того, что числа редко повторяются (например, последовательность случайных чисел).
Реализация
Существует несколько разных реализаций карманной сортировки.
Рассмотрим рекурсивную и нерекурсивную реализации.
Рекурсивный bucket sort
Рассмотрим код работы рекурсивной реализации карманной сортировки.
На вход подаются вещественные числа.
double[] bucketSort (double[] array, double minElement, double maxElement)
if array.length < 2 or minElement == maxElement
return array;
range = maxElement - minElement
for i = 0 to array.length - 1
index = int(array[i] * numBuckets / range)
добавим array[i] в конец buckets[index]
minBucktes[index] = minimum(buckets[index], array[i])
maxBuckets[index] = maximum(buckets[index], array[i])
for i = 0 to numBuckets - 1
buckets[i] = bucketSort(buckets[i], minBucktes[i], maxBuckets[i])
for i = 0 to numBuckets - 1
for k = 0 to buckets[i].length - 1
добавим buckets[i][k] в конец answer
return answer
Нерекурсивная реализация
double[] bucketSort(double[] array)
minElement = Infinum
maxElement = -Infinum
for i = 0 to array.length - 1
minElement = minimum(minElement, array[i])
maxElement = maximum(maxElement, array[i])
range = maxElement - minElement
for i = 0 to array.length - 1
index = int(array[i] * numBuckets / range)
добавим array[i] в конец buckets[index]
for i = 0 to numBuckets - 1
buckets[i] = sort(buckets[i])
for i = 0 to numBuckets - 1
for k = 0 to buckets[i].length - 1
добавим buckets[i][k] в конец answer
return answer
Асимптотика
Пусть — количество элементов в массиве, — количество блоков для разбиения.
— случайная величина, обозначающая количество элементов попавших в -ый карман.
, где время работы алгоритма карманной сортировки.
То есть, если
Если,
Из приведенных выше формул, видно, что в среднем "карманная сортировка" работает за линейное время.
