Изменения

Рассмотрим рекурсивную и нерекурсивную реализации.==== Рекурсивный bucket sort ====Рассмотрим код работы рекурсивной реализации карманной сортировки. На вход подаются вещественные числа. '''Карманная сортировкаdouble[]'''bucketSort (Bucket sort'''double[]''' array, '''double''' minElement, '''double''' maxElement) — алгоритм сортировки , основанный на предположение о равномерном распределении входных данных '''if''' array.length < 2 '''or''' minElement == Алгоритм сортировки maxElement '''return''' array; range =maxElement - minElement '''for''' i =0 '''to''' array.length - 1 index === Принцип работы алгоритма вообщем ===int(array[i] * numBuckets / range) добавим array[i] в конец buckets[Файл:Bucket-sort-example.jpg|right|300px|thumb|Пример работы рекурсивного Bucketsort.index] minBucktes[index]* элементы массива входных данных разбивается на <tex>k</tex> блоков= '''minimum'''("карманов"buckets[index],"корзин"array[i]).* каждый из блоков сортируется либо отдельной какой либо другой сортировкой maxBuckets[index] = '''maximum'''(buckets[index], либо рекурсивно тем же методом разбиения.array[i])* Из каждого отсортированного блока записываются в массив , в порядке разбиения на блоки. '''for''' i = 0 '''to''' numBuckets - 1Важно отметить buckets[i] = bucketSort(buckets[i], что разбиение на блоки производится таким образомminBucktes[i], чтобы элементы каждого следующего блока были бы больше предыдущего.maxBuckets[i]) '''for''' i =0 '''to''' numBuckets - 1 '''for''' k == Реализация Алгоритма===0 '''to''' buckets[i].length - 1 добавим buckets[i][k] в конец answerРассмотрим код работы алгоритма. '''return''' answer

<wikitex>==== Нерекурсивная реализация ==== Bucketsort'''double[]''' bucketSort(A,j'''double[]''' array){ if (A.length() < 2 || i minElement =Infinum maxElement = p + 1) return A; buckets <- инициализируем массив длины Base , где каждая ячейка список входных объектов (в нашем случаи Infinum строк. '''for ''' i = 0 '''to A''' array.length() - 1 добавляем A minElement = '''minimum'''(minElement, array[i] в конец массива buckets[partion) maxElement = '''maximum'''(AmaxElement, array[i],j)] // partion функция которая по данному объекту и индексу возвращает число от range = maxElement - minElement '''for''' i = 0 до Base '''to''' array.length - 1 / index = int(array[i] * numBuckets / range) добавим array[i] в случаи со строками функция partion возвращает код j-ого символа строки Aконец buckets[iindex]. '''for ''' i = 0 '''to Base ''' numBuckets - 1 buckets[i] = Bucketsortsort(buckets[i],j+1) answer <- инициализируем пустой массив(в который записывается отсортированный набор данных) '''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]