Изменения

На вход подаются вещественные числа. '''Карманная сортировкаdouble[]'''bucketSort (Bucket sort'''double[]''' array, '''double''' minElement, '''double''' maxElement) — алгоритм сортировки , основанный на предположение о равномерном распределении входных данных '''if''' array.length < 2 '''or''' minElement == Алгоритм сортировки maxElement '''return''' array; range =maxElement - minElement '''for''' i =0 '''to''' array.length - 1 index =int(array[i] * numBuckets / range) добавим array[i] в конец buckets[index] minBucktes[index] ='''minimum'''(buckets[index], array[i]) maxBuckets[index] = Принцип работы алгоритма вообщем '''maximum'''(buckets[index], array[i]) '''for''' i =0 '''to''' numBuckets - 1 buckets[i] ==* элементы массива входных данных разбивается на <tex>k</tex> блоковbucketSort("карманов"buckets[i],"корзин"minBucktes[i], maxBuckets[i]).* затем каждый из блоков сортируется либо отдельной какой либо другой сортировкой, либо рекурсивно тем же методом разбиения '''for''' i = 0 '''to''' numBuckets - 1 '''for''' k = 0 '''to''' buckets[i].length - 1* После сортировки данных каждого "кармана" данные записываются добавим buckets[i][k] в массив в порядке разбиения на карманы .конец answer '''return''' answerВажно отметить , что разбиение на "карманы" производится таким образом, чтобы каждый следующий "карман" был больше предыдущего.=== Реализация Алгоритма= Нерекурсивная реализация ====Рассмотрим код работы алгоритма. Сортируемыми объектами будем рассматривать строки.Длина каждой строки равна p .<wikitex> Bucketsort'''double[]''' bucketSort(A,j'''double[]''' array){ if (A.length() < 2 || i minElement =Infinum maxElement = p + 1) return A; buckets <- инициализируем массив длины Base , где каждая ячейка список входных объектов (в нашем случаи Infinum строк. '''for ''' i = 0 '''to A''' array.length() - 1 push_back A minElement = '''minimum'''(minElement, array[i] to buckets[partion) maxElement = '''maximum'''(AmaxElement, array[i],j)] // partion функция которая по данному объекту и индексу возвращает число от range = maxElement - minElement '''for''' i = 0 до Base '''to''' array.length - 1 / index = int(array[i] * numBuckets / range) добавим array[i] в случаи со строками функция partion возвращает код j-ого символа строки Aконец buckets[iindex]. '''for ''' i = 0 '''to Base ''' numBuckets - 1 buckets[i] = Bucketsortsort(buckets[i],j+1) answer <- инициализируем пустой массив '''for ''' i = 0 '''to Base ''' numBuckets - 1 '''for ''' k = 0 '''to ''' buckets[i].length() - 1 push_back добавим buckets[i][k] to в конец answer '''return ''' answer ==Асимптотика==Пусть <tex>n</tex> {{---}} количество элементов в массиве, <tex>k</tex> {{---}} количество блоков для разбиения. <tex> n_i </tex> {{---}} случайная величина, обозначающая количество элементов попавших в <tex> i </tex>-ый карман. <tex> T(n) = \Theta(n) + \sum\limits_{i = 1}^k O(n_i</tex> <tex> \log n_i) + \Theta(k)</tex>, где <tex> T(n) </tex> время работы алгоритма карманной сортировки.

<tex> E[n_i] = \dfrac {n}{k} </wikitextex>Base - основание системы счисления в случаи со строками 256.[[Файл:Цифровая_сортировка.png|thumb|right|450px|

Если, <tex> n =o(k) \Rightarrow E[T(n)] =Сложность==\Theta(k)</tex>