Изменения

[[Файл:Bucket-sort-example1.jpg|right|400px|thumb|Пример работы рекурсивного Bucketsort.]]'''Карманная сортировка''' (англ. ''Bucket sort'') {{---}} алгоритм [[Сортировки|сортировки]], основанный на предположении о равномерном распределении входных данных.

[[Файл:Bucket-sort-example1.jpg|right|300px|thumb|Пример работы рекурсивного Bucketsort.]]* Для карманной сортировки нужно разбить элементы массива входных данных разбиваются на <tex>k</tex> блоков (карманов, корзин).* Далее каждый из таких блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения.* из каждого отсортированного блока После сортировок внутри каждых блоков данные записываются в массив в порядке разбиения на блоки.Важно отметитьПри этом нужно учитывать, что данная сортировка работает только в том случае, если разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были бы больше предыдущего. Карманная сортировка сильно деградирует при большом количестве мало отличных элементов (большинство элементов попадёт в одну корзину). Поэтому такой тип сортировки использовать, когда велика вероятность того, что числа редко повторяются (например, последовательность случайных чисел). 

Рассмотрим код работы рекурсивной реализации карманной сортировки, на . На вход которой подаются вещественные числа.<wikitex> Bucketsort '''double[]''' bucketSort ('''double[]''' array,min_element'''double''' minElement,max_element'''double''' maxElement) '''if (''' array.length < 2 || min_element '''or''' minElement == max_element )maxElement '''return ''' array; initialize buckets <range = maxElement - new array of n empty lists initialize buckets_minimum initialize buckets_maximumminElement '''for ''' i = 0 '''to ''' array.length - 1 index = int(array[i] * num_buckets numBuckets / range) insert добавим array[i] at end в конец buckets[index] buckets_minimum minBucktes[iindex] = '''minimum '''( buckets[index], arraarray[i]) buckets_maximum maxBuckets[iindex] = '''maximum '''( buckets[index], arraarray[i]) '''for ''' i = 0 '''to num_buckets ''' numBuckets - 1 buckets[i] = Bucketsort bucketSort(buckets[i],min_bucktesminBucktes[i],max_bucketsmaxBuckets[i]) intialize answer '''for ''' i = 0 '''to buckets_num ''' numBuckets - 1 '''for ''' k = 0 '''to ''' buckets[i].length - 1 insert добавим buckets[i][k] аt end в конец answer '''return ''' answer </wikitex>

<wikitex> function '''double[]''' bucketSort('''double[]''' array, n) { buckets ← new array of n empty lists minElement = Infinum maxElement = -Infinum '''for ''' i = 0 '''to ( ''' array.length - 1) do insert minElement = '''minimum'''(minElement, array[i] into buckets[partition ) maxElement = '''maximum'''(maxElement, array[i], k)] range = maxElement - minElement '''for ''' i = 0 '''to n ''' array.length - 1 do nextSort index = int(bucketsarray[i]* numBuckets / range) return the concatenation of добавим array[i] в конец buckets[index] '''for''' i = 0'''to''' numBuckets - 1 buckets[i], ..., = sort(buckets[ n i]) '''for''' i = 0 '''to''' numBuckets - 1] }</wikitex>В данном псевдокоде функция partition возвращает для каждого объекта число от <tex> '''for''' k = 0</tex> до <tex>k '''to''' buckets[i].length - 1</tex>, причем partition монотонная функция.nextSort {{---}} функция сортирующая массив. добавим buckets[i][k] в конец answer '''return''' answer

Пусть <tex>n</tex> {{---}} количество элементов в массиве, <tex>k</tex> {{---}} основание системы исчисления и количество блоков для разбиения. <tex>pn_i </tex> {{---}} случайная величина, обозначающая количество разрядов в объекте.Тогда алгоритм "Bucket sort" элементов попавших в процессе работы сделает не более чем <Textex>O (p i </Textex> -ый карман. <Textex>T(n) = \Theta(n ) + \sum\limits_{i = 1}^k))O(n_i</Textex> итераций.Заметим, что в случае случайного распределения мат. ожидания количество элементов в каждом блоке <tex> n/\log n_i) + \Theta(k)</tex>. Следовательно, в средним алгоритм карманной сортировки совершает где <Textex>O T(n ) </Textex> время работы алгоритма карманной сортировки. <Textex>E[n_i] = \log_k dfrac {n)}{k} </Textex> действий. При этом на некотором множестве наборов То есть, где если <tex> n \sim k \Rightarrow E[T(n)] = O\Theta(n)</tex> Если, алгоритм отработает за линейное время.В худшем случае сортировка работает за <tex>O n = o(k) \Rightarrow E[T(n^2)] = \Theta(k)</tex>.==Примечания==Сортировка быстро работает для равновероятного распределения значений разрядов объектов в заданной для них системе счисления.[[Быстрая сортировка|Быстрая сортировка]] является частным случаем карманной сортировкиИз приведенных выше формул, в случае разбиения всех элементов на <tex>2 </tex> кармана. Также стоит отметитьвидно, что по принципу своей работы Bucket sort схожа с [[Цифровая в среднем "карманная сортировка|Цифровой сортировкой]]" работает за линейное время. ==СсылкиИсточники информации==* [http://en.wikipedia.org/wiki/Bucket_sortWikipedia — Bucket sort]* [http://ru.wikipedia.org/wiki/%D0%91%D0%BB%D0%BE%D1%87%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 Википедия — Блочная сортировка]

* [http://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=10&ved=0CI0BEBYwCQ&url=http%3A%2F%2Fcs.iupui.edu%2F~xkzou%2Fteaching%2FCS580%2FSortinginlineartime.ppt&ei=d7fUT8WWIs3S4QSkkPT-Ag&usg=AFQjCNEUbmlVNhSgrJKV9-QjPBwU6U0obQ&sig2=3yaysrpuwVjmyhjBCpyBeQ Презентация о линейных сортировках].* [https://www-927.ibm.com/ibm/cas/hspc/student/algorithms/BucketSort.html Приведен код Описание алгоритма с реализацией рекурсивной версии на Jave рекурсивной реализации "карманной" сортировки]* [http://www.youtube.com/watch?v=Iiuqrns0Gwk хорошее обучающее видео по теме bucket sortязыке Java]