42
правки
Изменения
Нет описания правки
'''Карманная сортировка''' (Bucket sort) — {{---}} алгоритм сортировки , основанный на предположении о равномерном распределении входных данных.
== Алгоритм сортировки ==
=== Принцип работы ===
[[Файл:Bucket-sort-example.jpg|right|300px|thumb|Пример работы рекурсивного Bucketsort.]]
* элементы массива входных данных разбиваются на <tex>k</tex> блоков ("карманов","корзин").
* каждый из блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения.
* из каждого отсортированного блока данные записываются в массив в порядке разбиения на блоки.
Важно отметить, что разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были бы больше предыдущего.
=== Реализация ===
Существует несколько разных реализаций "карманной сортировки".==== Рекурсивный bucket sort ====Рассмотрим код работы алгоритмарекурсивной реализации "карманной сортировки", где на вход которой подаются строки длины <tex> p </tex> — длина каждой строки.
<wikitex>
// j - the current index in string //base = 256 Bucketsort (Aarray, j){ // A - массив данных, j - текущий разряд if (Aarray.length < 2 || j == p + 1) return Aarray; initialize buckets <- инициализируем массив длины Base, где каждая ячейка — список входных объектов (в нашем случае строк).new array of n empty lists for i = 0 to Aarray.length - 1 добавляем Ainsert array[i] в конец массива at end buckets[partition (Aarray[i], j)] // partition — функция которая по данному объекту и индексу возвращает число от 0 до Base - 1 // в случае со строками функция partition возвращает код j-ого символа строки A[i]. for i = 0 to Base base - 1
buckets[i] = Bucketsort (buckets[i],j+1)
intialize answer <- инициализируем пустой массив (в который записывается отсортированный набор данных) for i = 0 to Base base - 1
for k = 0 to buckets[i].length - 1
return answer
}
fuction partition( string s, j)
return int(s[j])
</wikitex>
==Асимптотика==
Пусть <tex>n</tex> {{- --}} количество элементов в массиве, <tex>k</tex> {{--- }} основание системы исчисления и <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>, алгоритм отработает за линейное время.
* [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 Приведен код на Jave рекурсивной реализации "карманной" сортировки]* [http://www.youtube.com/watch?v=Iiuqrns0Gwk хорошее обучающее видео по теме bucket sort]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
