42
правки
Изменения
Нет описания правки
==== Рекурсивный bucket sort ====
Рассмотрим код работы рекурсивной реализации карманной сортировки, на вход которой подаются вещественные числа.
Bucketsort (array,min_element,max_element)
if (array.length < 2 || min_element == max_element )
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], array[i])
buckets_maximum[i] = maximum ( buckets[index], array[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 ''' num_buckets - 1 '''for ''' k = 0 '''to ''' buckets[i].length - 1
insert buckets[i][k] аt end answer
return answer
==== Нерекурсивная реализация ====
Bucketsort(array)
initialize buckets <- new array of n empty lists
min_element = Infinum
max_element = -Infinum
'''for''' i = 0 '''to''' array.length - 1
min_element = Min(min_element, array[i])
max_element = Max(max_element, array[i])
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] = quickSort(buckets[i])
intialize answer
'''for ''' i = 0 '''to ''' num_buckets - 1 '''for ''' k = 0 '''to ''' buckets[i].length - 1
insert buckets[i][k] аt end answer
return answer
==Асимптотика==
<tex> n_i </tex> {{---}} случайная величина, обозначающая количество элементов попавших в <tex> i </tex>-ый карман.
<tex> E[n_i] = n / k </tex>
Тоесть, если <tex> n \sim k </tex> <tex> \Rightarrow E[T(n)] = \theta(n) </tex> Если, <tex> n = o(k) </tex>
Если, <tex> n = o(k) \Rightarrow E[T(n)] = \theta(k) </tex>
Из приведенных выше формул, видно, что в среднем "карманная сортировка" работает за линейное время.
