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

Карманная сортировка (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], 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 

</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] = 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 

</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] E[n_i] = n / k [/math]

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

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

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

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

Из приведенных выше формул, видно, что в среднем "карманная сортировка" работает за линейное время.

Ссылки

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

• Презентация о линейных сортировках.
• Описание алгоритма с реализацией рекурсивной версии на языке Java