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