Изменения

'''Карманная сортировка''' (англ. ''Bucket sort'') {{---}} алгоритм сортировки, основанный на предположении о равномерном распределении входных данных.

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

Рассмотрим код работы рекурсивной реализации карманной сортировки, на . На вход которой подаются вещественные числа. Bucketsort array bucketSort (array,min_element,max_element) '''if (''' array.length < 2 || '''or''' min_element == max_element ) '''return ''' array; initialize buckets <- new array of n empty lists initialize buckets_minimum initialize buckets_maximum

index = int(array[i] * num_buckets / range) insert добавим array[i] at end в конец buckets[index] buckets_minimum[i] = minimum ( buckets[index], array[i]) buckets_maximum[i] = maximum ( buckets[index], array[i])

buckets[i] = Bucketsort bucketSort(buckets[i],min_bucktes[i],max_buckets[i]) intialize answer

'''for''' k = 0 '''to''' buckets[i].length - 1 insert добавим buckets[i][k] аt end в конец answer '''return ''' answer

Bucketsort array bucketSort(array) initialize buckets <- new array of n empty lists

min_element = Min'''minimum'''(min_element, array[i]) max_element = Max'''maximum'''(max_element, array[i])

index = int(array[i] * num_buckets / range) insert добавим array[i] at end в конец buckets[index]

buckets[i] = quickSort(buckets[i]) intialize answer

'''for''' k = 0 '''to''' buckets[i].length - 1 insert добавим buckets[i][k] аt end в конец answer '''return ''' answer

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

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

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

==СсылкиИсточники информации==* [http://en.wikipedia.org/wiki/Bucket_sortWikipedia - Bucket_sort]