42
правки
Изменения
Нет описания правки
'''Карманная сортировка'''(Bucket sort) — алгоритм сортировки , основанный на предположении о равномерном распределении входных данных.
== Алгоритм сортировки ==
=== Принцип работы ===
* каждый из блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения.
* из каждого отсортированного блока данные записываются в массив в порядке разбиения на блоки.
Важно отметить ,что разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были бы больше предыдущего.
=== Реализация ===
Рассмотрим код работы алгоритма, где <tex> p </tex> — длина каждой строки.
<wikitex>
Bucketsort(A, j){ // A - массив данных, j - текущий разряд if (A.length() < 2 || j == p + 1)
return A;
buckets <- инициализируем массив длины Base, где каждая ячейка — список входных объектов (в нашем случае
строк).
for i = 0 to A.length() - 1 добавляем A[i] в конец массива buckets[partition(A[i],j)]
// partition — функция которая по данному объекту и индексу возвращает число от 0 до Base - 1
// в случае со строками функция partition возвращает код j-ого символа строки A[i].
for i = 0 to Base - 1
buckets[i] = Bucketsort(buckets[i],j+1)
answer <- инициализируем пустой массив (в который записывается отсортированный набор данных)
for i = 0 to Base - 1
for k = 0 to buckets[i].length() - 1
добавляем buckets[i][k] в конец массива answer
return answer
Приведенный код работает не только для строк, а для любых объектов для которых можно определить порядок, систему счисления и функцию partition.
==Асимптотика==
Пусть <tex>n</tex> — - количество элементов в массиве, <tex>k</tex> — - основание системы исчисления и <tex>p</tex> — - количество разрядов в объекте.Тогда алгоритм "Bucket sort" в процессе работы сделает не более чем <Tex>O(p * \cdot (n + k))</Tex> итераций.Заметим ,что в случае случайного распределения мат. ожидания количество элементов в каждом блоке <tex> n/k</tex>. Следовательно, в средним алгоритм "карманной сортировки" совершает <Tex>O(n \cdot log_k n)</Tex> действий. При этом на некотором множестве наборов, где <tex> k = O(n)</tex>, алгоритм отработает за линейное время.В худшем случае сортировка работает за <tex>O(n^2)</tex>.
==Примечания==
Сортировка быстро работает для равновероятного распределения значений разрядов объектов в заданной для них системе счисления.
