Карманная сортировка — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Отмена правки 47312 участника Конспектор (обсуждение))
Строка 63: Строка 63:
  
 
==Источники информации==
 
==Источники информации==
* [http://en.wikipedia.org/wiki/Bucket_sort Wikipedia - Bucket_sort]
+
* [http://en.wikipedia.org/wiki/Bucket_sort Wikipedia - Bucket sort]
 
   
 
   
 
* [http://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=10&ved=0CI0BEBYwCQ&url=http%3A%2F%2Fcs.iupui.edu%2F~xkzou%2Fteaching%2FCS580%2FSortinginlineartime.ppt&ei=d7fUT8WWIs3S4QSkkPT-Ag&usg=AFQjCNEUbmlVNhSgrJKV9-QjPBwU6U0obQ&sig2=3yaysrpuwVjmyhjBCpyBeQ Презентация о линейных сортировках].
 
* [http://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=10&ved=0CI0BEBYwCQ&url=http%3A%2F%2Fcs.iupui.edu%2F~xkzou%2Fteaching%2FCS580%2FSortinginlineartime.ppt&ei=d7fUT8WWIs3S4QSkkPT-Ag&usg=AFQjCNEUbmlVNhSgrJKV9-QjPBwU6U0obQ&sig2=3yaysrpuwVjmyhjBCpyBeQ Презентация о линейных сортировках].
 
* [https://www-927.ibm.com/ibm/cas/hspc/student/algorithms/BucketSort.html Описание алгоритма с реализацией рекурсивной версии на языке Java]
 
* [https://www-927.ibm.com/ibm/cas/hspc/student/algorithms/BucketSort.html Описание алгоритма с реализацией рекурсивной версии на языке Java]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
+
[[Категория: Сортировка]]
 +
[[Категория: Другие сортировки]]

Версия 23:05, 3 июня 2015

Карманная сортировка (англ. Bucket sort) — алгоритм сортировки, основанный на предположении о равномерном распределении входных данных.

Алгоритм сортировки

Пример работы рекурсивного Bucketsort.

Принцип работы

Для карманной сортировки нужно разбить элементы массива входных данных на [math]k[/math] блоков (карманов, корзин). Далее каждый из таких блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения. После сортировок внутри каждых блоков данные записываются в массив в порядке разбиения на блоки. При этом нужно учитывать, что данная сортировка работает только в том случае, если разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были больше предыдущего.

Реализация

Существует несколько разных реализаций карманной сортировки.

Рассмотрим рекурсивную и нерекурсивную реализации.

Рекурсивный bucket sort

Рассмотрим код работы рекурсивной реализации карманной сортировки.

На вход подаются вещественные числа.

array bucketSort (array, min_element, max_element) 
   if array.length < 2 or min_element == max_element
       return array;
   range = max_element - min_element;
   for i = 0  to array.length - 1  
       index = int(array[i] * num_buckets / range)
       добавим array[i] в конец 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])
   for i = 0 to num_buckets - 1
       for k = 0 to buckets[i].length - 1
           добавим buckets[i][k] в конец answer
   return answer 

Нерекурсивная реализация

array bucketSort(array) 
   min_element = Infinum
   max_element = -Infinum
   for i = 0 to array.length - 1
       min_element = minimum(min_element, array[i])
       max_element = maximum(max_element, array[i]) 
   range = max_element - min_element;
   for i = 0  to array.length - 1  
       index = int(array[i] * num_buckets / range)
       добавим array[i] в конец buckets[index]
   for i = 0 to num_buckets - 1
       buckets[i] = quickSort(buckets[i])
   for i = 0 to num_buckets - 1
       for k = 0 to buckets[i].length - 1
           добавим buckets[i][k] в конец answer
   return answer 

Асимптотика

Пусть [math]n[/math] — количество элементов в массиве, [math]k[/math] — количество блоков для разбиения.

[math] n_i [/math] — случайная величина, обозначающая количество элементов попавших в [math] i [/math]-ый карман.

[math] T(n) = \Theta(n) + \sum\limits_{i = 1}^k O(n_i[/math] [math] \log n_i) + \Theta(k)[/math], где [math] T(n) [/math] время работы алгоритма карманной сортировки.

[math] E[n_i] = n / k [/math]

То есть, если [math] n \sim k \Rightarrow E[T(n)] = \Theta(n) [/math]

Если, [math] n = o(k) \Rightarrow E[T(n)] = \Theta(k)[/math]

Из приведенных выше формул, видно, что в среднем "карманная сортировка" работает за линейное время.

Источники информации