42
правки
Изменения
Нет описания правки
=== Принцип работы ===
[[Файл:Bucket-sort-example1.jpg|right|300px|thumb|Пример работы рекурсивного Bucketsort.]]
* элементы массива входных данных разбиваются на <tex>k</tex> блоков ("карманов", "корзин").
* каждый из блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения.
* из каждого отсортированного блока данные записываются в массив в порядке разбиения на блоки.
Важно отметить, что разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были бы больше предыдущего.
=== Реализация ===
Существует несколько разных реализаций "карманной сортировки".
==== Рекурсивный bucket sort ====
Рассмотрим код работы рекурсивной реализации "карманной сортировки", на вход которой подаются строки длины <tex> p </tex>.
<wikitex>
// j - the current index in string
</wikitex>
base {{---}} основание системы счисления, в случае со строками base <tex> = 256</tex>.
====Не рекурсивная Нерекурсивная реализация ====
<wikitex>
function bucketSort(array, n) {
<tex>p</tex> {{---}} количество разрядов в объекте.
Тогда алгоритм "Bucket sort" в процессе работы сделает не более чем <Tex>O (p </Tex> <Tex>(n + k))</Tex> итераций.
Заметим, что в случае случайного распределения мат. ожидания количество элементов в каждом блоке <tex> n/k</tex>. Следовательно, в средним алгоритм "карманной сортировки" совершает <Tex>O (n </Tex> <Tex>\log_k n)</Tex> действий. При этом на некотором множестве наборов, где <tex> k = O(n)</tex>, алгоритм отработает за линейное время.
В худшем случае сортировка работает за <tex>O (n^2)</tex>.
==Примечания==
Сортировка быстро работает для равновероятного распределения значений разрядов объектов в заданной для них системе счисления.
[[Быстрая сортировка|Быстрая сортировка]] является частным случаем "карманной" сортировки, в случае разбиения всех элементов на <tex>2 </tex> "кармана". Также стоит отметить, что по принципу своей работы Bucket sort схожа с [[Цифровая сортировка|Цифровой сортировкой]].
==Ссылки==
* http://en.wikipedia.org/wiki/Bucket_sort
