Карманная сортировка

Карманная сортировка (Bucket sort) — алгоритм сортировки, основанный на предположении о равномерном распределении входных данных.

Алгоритм сортировки

Принцип работы

Пример работы рекурсивного Bucketsort.

• элементы массива входных данных разбиваются на [math]k[/math] блоков (карманов, корзин).
• каждый из блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения.
• из каждого отсортированного блока данные записываются в массив в порядке разбиения на блоки.

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

Реализация

Существует несколько разных реализаций карманной сортировки.

Рекурсивный bucket sort

Рассмотрим код работы рекурсивной реализации карманной сортировки, на вход которой подаются вещественные числа. <wikitex>

 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], arra[i])
     buckets_maximum[i] = maximum ( buckets[index], arra[i])
   for i = 0 to num_buckets - 1
     buckets[i] = quicksort (buckets[i],min_bucktes[i],max_buckets[i])
   intialize answer
   for i = 0 to buckets_num - 1
     for k = 0 to buckets[i].length - 1
       insert  buckets[i][k] аt end answer
   return answer 

</wikitex>

Нерекурсивная реализация

<wikitex>

 Bucketsort(array) 
   initialize buckets <- new array of n empty lists
   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] = insertionSort(buckets[i])
   intialize answer
   for i = 0 to buckets_num - 1
     for k = 0 to buckets[i].length - 1
       insert  buckets[i][k] аt end answer
   return answer 

</wikitex>

Асимптотика

Пусть [math]n[/math] — количество элементов в массиве, [math]k[/math] — количество блоков для разбиения.

[math] n_i [/math] — случайная величина, обозначающая количество элементов попавших в [math] i [/math]-ый карман.

[math] T(n) [/math] — время работы алгоритма карманной сортировки

[math] T(n) = \theta(n) + \sum\limits_{i = 1}^k O(n_i[/math] [math] \log n_i) + \theta(k)[/math]

[math] M(n_i) = n / k [/math]

Тоесть, если [math] n \sim k [/math]

[math] T(n) = \theta(n) [/math]

Если, [math] n = o(k) [/math]

[math] T(n) = \theta(k) [/math]

Примечания

Сортировка быстро работает для равновероятного распределения значений разрядов объектов в заданной для них системе счисления. Быстрая сортировка является частным случаем карманной сортировки, в случае разбиения всех элементов на [math]2 [/math] кармана. Также стоит отметить, что по принципу своей работы Bucket sort схожа с Цифровой сортировкой.

Ссылки

• http://en.wikipedia.org/wiki/Bucket_sort

• Презентация о линейных сортировках.
• Приведен код на Jave рекурсивной реализации "карманной" сортировки
• хорошее обучающее видео по теме bucket sort