Изменения

[[Файл: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 <- new array of n empty lists initialize buckets_minimum initialize buckets_maximum range = max_element maxElement - min_element;minElement '''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] = quicksort 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> Bucketsort '''double[]''' bucketSort('''double[]''' array) initialize buckets <minElement = Infinum maxElement = -Infinum '''for''' i = 0 '''to''' array.length - new 1 minElement = '''minimum'''(minElement, array of n empty lists[i]) maxElement = '''maximum'''(maxElement, array[i]) range = max_element maxElement - min_element;minElement '''for ''' i = 0 '''to ''' array.length - 1 index = int(array[i] * num_buckets numBuckets / range) insert добавим array[i] at end в конец buckets[index] '''for ''' i = 0 '''to num_buckets ''' numBuckets - 1 buckets[i] = insertionSortsort(buckets[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>

<tex> T(n) </tex> {{---}} время работы алгоритма карманной сортировки <tex> T(n) = \thetaTheta(n) + \sum\limits_{i = 1}^k O(n_i</tex> <tex> \log n_i) + \thetaTheta(k)</tex> , где <tex> MT(n_in) = n / k </tex> Тоесть, если <tex> n \sim k </tex> время работы алгоритма карманной сортировки.

<tex> M(T(n)) E[n_i] = \theta(dfrac {n) }{k} </tex>

ЕслиТо есть, если <tex> n \sim k \Rightarrow E[T(n)] = o\Theta(kn) </tex>

Если, <tex> Mn = o(k) \Rightarrow E[T(n)) ] = \thetaTheta(k) </tex>

==СсылкиИсточники информации==* [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 рекурсивной реализации "карманной" сортировкиязыке Java]