Карманная сортировка — различия между версиями
Daniel (обсуждение | вклад) |
Daniel (обсуждение | вклад) |
||
| Строка 19: | Строка 19: | ||
initialize buckets_minimum | initialize buckets_minimum | ||
initialize buckets_maximum | initialize buckets_maximum | ||
| + | range = max_element - min_element; | ||
for i = 0 to array.length - 1 | for i = 0 to array.length - 1 | ||
index = int(array[i] * num_buckets / range) | index = int(array[i] * num_buckets / range) | ||
| Строка 34: | Строка 35: | ||
==== Нерекурсивная реализация ==== | ==== Нерекурсивная реализация ==== | ||
<wikitex> | <wikitex> | ||
| − | + | Bucketsort(array) | |
| − | + | initialize buckets <- new array of n empty lists | |
| − | + | range = max_element - min_element; | |
| − | + | for i = 0 to array.length - 1 | |
| − | + | index = int(array[i] * num_buckets / range) | |
| − | + | insert array[i] at end buckets[index] | |
| − | + | for i = 0 to num_buckets - 1 | |
| − | + | buckets[i] = insertionSort(buckets[i]) | |
| + | intialize answer | ||
| + | for i = 0 to buckets_num - 1 | ||
| + | for k = 0 to buckets[i].length - 1 | ||
| + | insert buckets[i][k] аt end answer | ||
| + | return answer | ||
</wikitex> | </wikitex> | ||
| − | |||
| − | |||
| − | |||
==Асимптотика== | ==Асимптотика== | ||
Пусть <tex>n</tex> {{---}} количество элементов в массиве, <tex>k</tex> {{---}} основание системы исчисления и | Пусть <tex>n</tex> {{---}} количество элементов в массиве, <tex>k</tex> {{---}} основание системы исчисления и | ||
Версия 13:52, 12 июня 2012
Карманная сортировка (Bucket sort) — алгоритм сортировки, основанный на предположении о равномерном распределении входных данных.
Содержание
Алгоритм сортировки
Принцип работы
- элементы массива входных данных разбиваются на блоков (карманов, корзин).
- каждый из блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения.
- из каждого отсортированного блока данные записываются в массив в порядке разбиения на блоки.
Важно отметить, что разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были бы больше предыдущего.
Реализация
Существует несколько разных реализаций карманной сортировки.
Рекурсивный bucket sort
Рассмотрим код работы рекурсивной реализации карманной сортировки, на вход которой подаются вещественные числа. <wikitex>
Bucketsort (array,min_element,max_element)
if (array.length < 2 || min_element == max_element )
return array;
initialize buckets <- new array of n empty lists
initialize buckets_minimum
initialize buckets_maximum
range = max_element - min_element;
for i = 0 to array.length - 1
index = int(array[i] * num_buckets / range)
insert array[i] at end buckets[index]
buckets_minimum[i] = minimum ( buckets[index], arra[i])
buckets_maximum[i] = maximum ( buckets[index], arra[i])
for i = 0 to num_buckets - 1
buckets[i] = Bucketsort (buckets[i],min_bucktes[i],max_buckets[i])
intialize answer
for i = 0 to buckets_num - 1
for k = 0 to buckets[i].length - 1
insert buckets[i][k] аt end answer
return answer
</wikitex>
Нерекурсивная реализация
<wikitex>
Bucketsort(array)
initialize buckets <- new array of n empty lists
range = max_element - min_element;
for i = 0 to array.length - 1
index = int(array[i] * num_buckets / range)
insert array[i] at end buckets[index]
for i = 0 to num_buckets - 1
buckets[i] = insertionSort(buckets[i])
intialize answer
for i = 0 to buckets_num - 1
for k = 0 to buckets[i].length - 1
insert buckets[i][k] аt end answer
return answer
</wikitex>
Асимптотика
Пусть — количество элементов в массиве, — основание системы исчисления и — количество разрядов в объекте. Тогда алгоритм "Bucket sort" в процессе работы сделает не более чем итераций. Заметим, что в случае случайного распределения мат. ожидания количество элементов в каждом блоке . Следовательно, в средним алгоритм карманной сортировки совершает действий. При этом на некотором множестве наборов, где , алгоритм отработает за линейное время. В худшем случае сортировка работает за .
Примечания
Сортировка быстро работает для равновероятного распределения значений разрядов объектов в заданной для них системе счисления. Быстрая сортировка является частным случаем карманной сортировки, в случае разбиения всех элементов на кармана. Также стоит отметить, что по принципу своей работы Bucket sort схожа с Цифровой сортировкой.
