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

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

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

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

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

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

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

Реализация

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

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

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

// j - the current index in string
//base = 256
Bucketsort (array, j){ 
    if (array.length < 2 || j == p + 1)
        return array;
     initialize buckets <- new array of n empty lists
    for i = 0  to array.length - 1  
      insert array[i] at end buckets[partition (array[i], j)] 
    for i = 0 to base - 1
       buckets[i] = Bucketsort (buckets[i],j+1)
    intialize answer
    for i = 0 to base - 1
       for k = 0 to buckets[i].length - 1
          insert  buckets[i][k] аt end answer
    return answer
}
fuction partition( string s, j)
    return int(s[j])

</wikitex> base — основание системы счисления, в случае со строками base [math] = 256[/math].

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

<wikitex>

function bucketSort(array, n) {
  buckets ← new array of n empty lists
  for i = 0 to ( array.length - 1) do
    insert array[i] into buckets[partition (array[i], k)]
  for i = 0 to n - 1 do
    nextSort (buckets[i])
  return the concatenation of buckets[0], ..., buckets[ n - 1]
 }

</wikitex> В данном псевдокоде функция partition возвращает для каждого объекта число от [math]0[/math] до [math]k - 1[/math], причем partition монотонная функция. nextSort — функция сортирующая массив.

Асимптотика

Пусть [math]n[/math] — количество элементов в массиве, [math]k[/math] — основание системы исчисления и [math]p[/math] — количество разрядов в объекте. Тогда алгоритм "Bucket sort" в процессе работы сделает не более чем [math]O (p [/math] [math](n + k))[/math] итераций. Заметим, что в случае случайного распределения мат. ожидания количество элементов в каждом блоке [math] n/k[/math]. Следовательно, в средним алгоритм карманной сортировки совершает [math]O (n [/math] [math]\log_k n)[/math] действий. При этом на некотором множестве наборов, где [math] k = O(n)[/math], алгоритм отработает за линейное время. В худшем случае сортировка работает за [math]O (n^2)[/math].

Примечания

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

Ссылки

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

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