42
правки
Изменения
Нет описания правки
</wikitex>
Base - основание системы счисления в случаи со строками Base = 256.
Приведенный код, работает не только для строк , а в принципе для любых объектов для которых можно определить порядок, систему счисления и функцию partion.
==Асимптотика==
Пусть <tex>n</tex> количество элементов в массиве, <tex>k</tex> основание системы исчисления и
<tex>p</tex> количество разрядов в объекте.
Тогда алгоритм "Bucket sort" в процессе работы, сделает не более чем <Tex>O(p * (n + k))</Tex> итераций.
Заметим ,что в случаи случайного распределения мат. ожидания количество элементов в каждом блоке <tex> n/k</tex>. Следовательно в средним алгоритм "карманной сортировки" совершает <Tex>O(n * 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
* [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 Презентация о линейных сортировках].
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
