Изменения

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

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

Существует несколько разных реализаций карманной сортировки. Рассмотрим рекурсивную и нерекурсивную реализации.==== Рекурсивный bucket sort ====Рассмотрим код работы алгоритма, где <tex> p </tex> — длина каждой строкирекурсивной реализации карманной сортировки.<wikitex>На вход подаются вещественные числа. Bucketsort'''double[]''' bucketSort (A'''double[]''' array, j'''double''' minElement, '''double''' maxElement){ // A - массив данных, j - текущий разряд '''if (A''' array.length() < 2 || j '''or''' minElement == p + 1)maxElement '''return A''' array; buckets < range = maxElement - инициализируем массив длины Base, где каждая ячейка — список входных объектов (в нашем случае minElement строк). '''for ''' i = 0 '''to A''' array.length() - 1 добавляем A index = int(array[i] * numBuckets / range) добавим array[i] в конец массива buckets[partitionindex] minBucktes[index] = '''minimum'''(Abuckets[index], array[i]) maxBuckets[index] = '''maximum'''(buckets[index],jarray[i]) '''for''' i = 0 '''to''' numBuckets - 1 buckets[i] = bucketSort(buckets[i], minBucktes[i] , maxBuckets[i]) // partition — функция которая по данному объекту и индексу возвращает число от '''for''' i = 0 до Base '''to''' numBuckets - 1 // в случае со строками функция partition возвращает код j '''for''' k = 0 '''to''' buckets[i].length -ого символа строки A1 добавим buckets[i]. [k] в конец answer '''return''' answer ==== Нерекурсивная реализация ==== '''double[]''' bucketSort('''double[]''' array) minElement = Infinum maxElement = -Infinum '''for ''' i = 0 '''to Base ''' array.length - 1 bucketsminElement = '''minimum'''(minElement, array[i] ) maxElement = Bucketsort'''maximum'''(bucketsmaxElement, array[i],j+) range = maxElement - minElement '''for''' i = 0 '''to''' array.length - 1 index = int(array[i] * numBuckets / range) answer < добавим array[i] в конец buckets[index] '''for''' i = 0 '''to''' numBuckets - инициализируем пустой массив1 buckets[i] = sort(в который записывается отсортированный набор данныхbuckets[i]) '''for ''' i = 0 '''to Base ''' numBuckets - 1 '''for ''' k = 0 '''to ''' buckets[i].length() - 1 добавляем добавим buckets[i][k] в конец массива answer '''return ''' answer }</wikitex>Base - основание системы счисления в случае со строками Base = 256.

Пусть <tex>n</tex> {{---}} количество элементов в массиве, <tex>k</tex> основание системы исчисления и {{---}} количество блоков для разбиения. <tex>pn_i </tex> {{---}} случайная величина, обозначающая количество разрядов элементов попавших в объекте<tex> i </tex>-ый карман.Тогда алгоритм "Bucket sort" в процессе работы, сделает не более чем <Textex>OT(p * n) = \Theta(n ) + \sum\limits_{i = 1}^k))O(n_i</Textex> итераций.Заметим ,что в случае случайного распределения мат. ожидания количество элементов в каждом блоке <tex> n/\log n_i) + \Theta(k)</tex>. Следовательно в средним алгоритм "карманной сортировки" совершает , где <Textex>OT(n * log_k n)</Textex> действийвремя работы алгоритма карманной сортировки.При этом на некотором множестве наборов, где  <tex> k E[n_i] = O(\dfrac {n)}{k} </tex> , алгоритм отработает за линейное время.В худшем случаи То есть, сортировка работает за если <tex>On \sim k \Rightarrow E[T(n)] = \Theta(n^2)</tex>.==Примечания==Сортировка быстро работает для равновероятного распределения значений разрядов объектов в заданной для них системы счисления. [[Быстрая сортировка|быстрая сортировка]] является частным случаем "карманной" сортировкойЕсли, в случаи разбиения всех элементов на <tex>2 n = o(k) \Rightarrow E[T(n)] = \Theta(k)</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 Описание алгоритма с реализацией рекурсивной версии на языке Java]