Изменения

Перейти к: навигация, поиск

Карманная сортировка

56 байт добавлено, 23:29, 3 июня 2015
Нет описания правки
[[Файл:Bucket-sort-example1.jpg|right|400px|thumb|Пример работы рекурсивного Bucketsort.]]
'''Карманная сортировка''' (англ. ''Bucket sort'') {{---}} алгоритм сортировки, основанный на предположении о равномерном распределении входных данных.
== Алгоритм сортировки ==
[[Файл:Bucket-sort-example1.jpg|right|300px|thumb|Пример работы рекурсивного Bucketsort.]]
=== Принцип работы ===
Для карманной сортировки нужно разбить элементы массива входных данных на <tex>k</tex> блоков (карманов, корзин). Далее каждый из таких блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения. После сортировок внутри каждых блоков данные записываются в массив в порядке разбиения на блоки. При этом нужно учитывать, что данная сортировка работает только в том случае, если разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были больше предыдущего.
На вход подаются вещественные числа.
array '''double[]''' bucketSort ('''double[]''' array, min_element'''double''' minElement, max_element'''double''' maxElement) '''if''' array.length < 2 '''or''' min_element minElement == max_elementmaxElement
'''return''' array;
range = max_element maxElement - min_elementminElement;
'''for''' i = 0 '''to''' array.length - 1
index = int(array[i] * num_buckets numBuckets / range)
добавим array[i] в конец buckets[index]
buckets_minimumbucketsMinimum[i] = minimum(buckets[index], array[i]) buckets_maximumbucketsMaximum[i] = maximum(buckets[index], array[i]) '''for''' i = 0 '''to''' num_buckets numBuckets - 1 buckets[i] = bucketSort(buckets[i], min_bucktesminBucktes[i], max_bucketsmaxBuckets[i]) '''for''' i = 0 '''to''' num_buckets numBuckets - 1
'''for''' k = 0 '''to''' buckets[i].length - 1
добавим buckets[i][k] в конец answer
'''return''' answer
==== Нерекурсивная реализация ====
array '''double[]''' bucketSort('''double[]''' array) min_element minElement = Infinum max_element maxElement = -Infinum
'''for''' i = 0 '''to''' array.length - 1
min_element minElement = '''minimum'''(min_elementminElement, array[i]) max_element maxElement = '''maximum'''(max_elementmaxElement, array[i]) range = max_element maxElement - min_elementminElement;
'''for''' i = 0 '''to''' array.length - 1
index = int(array[i] * num_buckets numBuckets / range)
добавим array[i] в конец buckets[index]
'''for''' i = 0 '''to''' num_buckets numBuckets - 1
buckets[i] = quickSort(buckets[i])
'''for''' i = 0 '''to''' num_buckets numBuckets - 1
'''for''' k = 0 '''to''' buckets[i].length - 1
добавим buckets[i][k] в конец answer
<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] = \frac {n / }{k } </tex>
То есть, если <tex> n \sim k \Rightarrow E[T(n)] = \Theta(n) </tex>
146
правок

Навигация