42
правки
Изменения
Нет описания правки
== Алгоритм сортировки ==
=== Принцип работы алгоритма вообщем ===
[[Файл:Bucket-sort-example.jpg|right|300px|thumb|Пример работы рекурсивного Bucketsort.]]
* элементы массива входных данных разбивается на <tex>k</tex> блоков("карманов","корзин").
* затем каждый из блоков сортируется либо отдельной какой либо другой сортировкой, либо рекурсивно тем же методом разбиения.* После сортировки данных Из каждого "кармана" данные отсортированного блока записываются в массив , в порядке разбиения на карманы блоки.Важно отметить , что разбиение на "карманы" блоки производится таким образом, чтобы каждый следующий "карман" был элементы каждого следующего блока были бы больше предыдущего.
=== Реализация Алгоритма===
Рассмотрим код работы алгоритма. Сортируемыми объектами будем рассматривать строки.Длина каждой строки равна p .
<wikitex>
Bucketsort(A,j){
строк.
for i = 0 to A.length() - 1
// partion функция которая по данному объекту и индексу возвращает число от 0 до Base - 1
// в случаи со строками функция partion возвращает код 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
return answer
}
</wikitex>
Base - основание системы счисления в случаи со строками Base = 256.[[Файл:Цифровая_сортировкаПриведенный код, работает не только для строк , а в принципе для любых объектов для которых можно определить порядок, системы счисления и функцию partion.png|thumb|right|450px|
==Сложность==
