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

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

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

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

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

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

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

Реализация

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

Рекурсивный 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 

Асимптотика

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

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

[math] T(n) = \theta(n) + \sum\limits_{i = 1}^k O(n_i[/math] [math] \log n_i) + \theta(k)[/math], где [math] T(n) [/math] время работы алгоритма карманной сортировки.

[math] E[n_i] = n / k [/math]

Тоесть, если [math] n \sim k \Rightarrow E[T(n)] = \theta(n) [/math]

Если, [math] n = o(k) \Rightarrow E[T(n)] = \theta(k)[/math]

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

Ссылки

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

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