Изменения

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

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

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

Рассмотрим код работы рекурсивной реализации "карманной сортировки", на . На вход которой подаются строки длины <tex> p </tex>вещественные числа.<wikitex> // j - the current index in string //base = 256 Bucketsort '''double[]''' bucketSort ('''double[]''' array, j'''double''' minElement, '''double''' maxElement){ '''if (''' array.length < 2 || j '''or''' minElement == p + 1)maxElement '''return ''' array; initialize buckets < range = maxElement - new array of n empty listsminElement '''for ''' i = 0 '''to ''' array.length - 1 insert index = int(array[i] * numBuckets / range) добавим array[i] at end в конец buckets[partition index] minBucktes[index] = '''minimum'''(buckets[index], array[i]) maxBuckets[index] = '''maximum'''(buckets[index], jarray[i])] '''for ''' i = 0 '''to base ''' numBuckets - 1 buckets[i] = Bucketsort bucketSort(buckets[i],j+1minBucktes[i], maxBuckets[i]) intialize answer '''for ''' i = 0 '''to base ''' numBuckets - 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 <tex> = 256</tex>.====Не рекурсивная Нерекурсивная реализация ====<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]