Изменения

[[Файл: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], array[i]) buckets_maximum maxBuckets[iindex] = '''maximum '''( buckets[index], array[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 = - new Infinum '''for''' i = 0 '''to''' array of n empty lists.length - 1 minElement = '''minimum'''(minElement, array[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] = quickSortsort(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> E[n_i] = n / k </tex> Тоесть, если где <tex> T(n \sim k ) </tex> время работы алгоритма карманной сортировки.

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

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

Если, <tex> n = 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 Презентация о линейных сортировках].