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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Принцип работы)
м (rollbackEdits.php mass rollback)
 
(не показано 28 промежуточных версий 7 участников)
Строка 1: Строка 1:
 
+
[[Файл:Bucket-sort-example1.jpg|right|400px|thumb|Пример работы рекурсивного Bucketsort.]]
'''Карманная сортировка''' (Bucket sort)  {{---}} алгоритм сортировки, основанный на предположении о равномерном распределении входных данных.
+
'''Карманная сортировка''' (англ. ''Bucket sort'')  {{---}} алгоритм [[Сортировки|сортировки]], основанный на предположении о равномерном распределении входных данных.
 
== Алгоритм сортировки ==
 
== Алгоритм сортировки ==
 
=== Принцип работы ===
 
=== Принцип работы ===
[[Файл:Bucket-sort-example1.jpg|right|300px|thumb|Пример работы рекурсивного Bucketsort.]]
+
Для карманной сортировки нужно разбить элементы массива входных данных на <tex>k</tex> блоков (карманов, корзин). Далее каждый из таких блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения. После сортировок внутри каждых блоков данные записываются в массив в порядке разбиения на блоки. При этом нужно учитывать, что данная сортировка работает только в том случае, если разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были больше предыдущего.
* элементы массива входных данных разбиваются на <tex>k</tex> блоков ("карманов", "корзин").
+
 
* каждый из блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения.
+
Карманная сортировка сильно деградирует при большом количестве мало отличных элементов (большинство элементов попадёт в одну корзину). Поэтому такой тип сортировки использовать, когда велика вероятность того, что числа редко повторяются (например, последовательность случайных чисел).
*  из каждого отсортированного блока данные записываются в массив в порядке разбиения на блоки.
 
Важно отметить, что разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были бы больше предыдущего.
 
  
 
=== Реализация ===
 
=== Реализация ===
Существует несколько разных реализаций "карманной сортировки".
+
Существует несколько разных реализаций карманной сортировки.
 +
 
 +
Рассмотрим рекурсивную и нерекурсивную реализации.
 
==== Рекурсивный bucket sort ====
 
==== Рекурсивный bucket sort ====
Рассмотрим код работы рекурсивной реализации "карманной сортировки", на вход которой подаются строки длины <tex> p </tex>.
+
Рассмотрим код работы рекурсивной реализации карманной сортировки.
<wikitex>
+
 
  // j - the current index in string
+
На вход подаются вещественные числа.
//base = 256
+
  '''double[]''' bucketSort ('''double[]''' array, '''double''' minElement, '''double''' maxElement)  
Bucketsort (array, j){
+
    '''if''' array.length < 2 '''or''' minElement == maxElement
    if (array.length < 2 || j == p + 1)
+
        '''return''' array;
        return array;
+
    range = maxElement - minElement
      initialize buckets <- new array of n empty lists
+
    '''for''' i = 0  '''to''' array.length - 1   
    for i = 0  to array.length - 1   
+
        index = int(array[i] * numBuckets / range)
      insert array[i] at end buckets[partition (array[i], j)]
+
        добавим array[i] в конец buckets[index]
    for i = 0 to base - 1
+
        minBucktes[index] = '''minimum'''(buckets[index], array[i])
         buckets[i] = Bucketsort (buckets[i],j+1)
+
        maxBuckets[index] = '''maximum'''(buckets[index], array[i])
    intialize answer
+
    '''for''' i = 0 '''to''' numBuckets - 1
    for i = 0 to base - 1
+
         buckets[i] = bucketSort(buckets[i], minBucktes[i], maxBuckets[i])
         for k = 0 to buckets[i].length - 1
+
    '''for''' i = 0 '''to''' numBuckets - 1
          insert  buckets[i][k] аt end answer
+
         '''for''' k = 0 '''to''' buckets[i].length - 1
    return answer
+
            добавим buckets[i][k] в конец answer
}
+
    '''return''' answer
fuction partition( string s, j)
+
 
    return int(s[j])
+
==== Нерекурсивная реализация ====
</wikitex>
+
  '''double[]''' bucketSort('''double[]''' array)  
base {{---}} основание системы счисления, в случае со строками base <tex> = 256</tex>.
+
    minElement = Infinum
====Не рекурсивная реализация ====
+
    maxElement = -Infinum
<wikitex>
+
    '''for''' i = 0 '''to''' array.length - 1
  function bucketSort(array, n) {
+
        minElement = '''minimum'''(minElement, array[i])
  buckets ← new array of n empty lists
+
        maxElement = '''maximum'''(maxElement, array[i])  
  for i = 0 to ( array.length - 1) do
+
    range = maxElement - minElement
    insert array[i] into buckets[partition (array[i], k)]
+
    '''for''' i = 0 '''to''' array.length - 1
  for i = 0 to n - 1 do
+
        index = int(array[i] * numBuckets / range)
    nextSort (buckets[i])
+
        добавим array[i] в конец buckets[index]
  return the concatenation of buckets[0], ..., buckets[ n - 1]
+
    '''for''' i = 0 '''to''' numBuckets - 1
  }
+
        buckets[i] = sort(buckets[i])
</wikitex>
+
    '''for''' i = 0 '''to''' numBuckets - 1
В данном псевдокоде функция partition возвращает для каждого объекта число от <tex>0</tex> до <tex>k - 1</tex>, причем partition монотонная функция.
+
        '''for''' k = 0 '''to''' buckets[i].length - 1
nextSort {{---}} функция сортирующая массив.
+
            добавим buckets[i][k] в конец answer
 +
    '''return''' answer
  
 
==Асимптотика==
 
==Асимптотика==
Пусть <tex>n</tex> {{---}} количество элементов в массиве, <tex>k</tex> {{---}} основание системы исчисления и
+
Пусть <tex>n</tex> {{---}} количество элементов в массиве, <tex>k</tex> {{---}} количество блоков для разбиения.
<tex>p</tex> {{---}} количество разрядов в объекте.
+
 
Тогда алгоритм "Bucket sort" в процессе работы сделает не более чем <Tex>O (p </Tex> <Tex>(n + k))</Tex> итераций.
+
<tex> n_i </tex> {{---}} случайная величина, обозначающая количество элементов попавших в <tex> i </tex>-ый карман.
Заметим, что в случае случайного распределения мат. ожидания количество элементов в каждом блоке <tex> n/k</tex>. Следовательно, в средним алгоритм "карманной сортировки" совершает <Tex>O (n </Tex> <Tex>\log_k n)</Tex> действий. При этом на некотором множестве наборов, где <tex> k = O(n)</tex>, алгоритм отработает за линейное время.
+
 
В худшем случае сортировка работает за <tex>O (n^2)</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} </tex>
[[Быстрая сортировка|Быстрая сортировка]] является частным случаем "карманной" сортировки, в случае разбиения всех элементов на <tex>2 </tex> "кармана". Также стоит отметить, что по принципу своей работы Bucket sort схожа с [[Цифровая сортировка|Цифровой сортировкой]].
+
 
==Ссылки==
+
То есть, если <tex> n \sim k \Rightarrow  E[T(n)] = \Theta(n) </tex>  
* http://en.wikipedia.org/wiki/Bucket_sort
+
 
 +
Если, <tex> n = o(k) \Rightarrow E[T(n)] = \Theta(k)</tex>
 +
 
 +
Из приведенных выше формул, видно, что в среднем "карманная сортировка" работает за линейное время.
 +
 
 +
==Источники информации==
 +
* [http://en.wikipedia.org/wiki/Bucket_sort Wikipedia — Bucket sort]
 +
* [http://ru.wikipedia.org/wiki/%D0%91%D0%BB%D0%BE%D1%87%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 Википедия — Блочная сортировка]
 
   
 
   
* [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 Приведен код на Jave рекурсивной реализации "карманной" сортировки]
+
* [https://www-927.ibm.com/ibm/cas/hspc/student/algorithms/BucketSort.html Описание алгоритма с реализацией рекурсивной версии на языке Java]
* [http://www.youtube.com/watch?v=Iiuqrns0Gwk хорошее обучающее видео по теме bucket sort]
 
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Сортировки]]
 
[[Категория: Сортировки]]
 +
[[Категория: Другие сортировки]]

Текущая версия на 19:15, 4 сентября 2022

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

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

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

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

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

Карманная сортировка сильно деградирует при большом количестве мало отличных элементов (большинство элементов попадёт в одну корзину). Поэтому такой тип сортировки использовать, когда велика вероятность того, что числа редко повторяются (например, последовательность случайных чисел).

Реализация

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

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

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

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

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

double[] bucketSort (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] = 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

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

double[] bucketSort(double[] array) 
   minElement = Infinum
   maxElement = -Infinum
   for i = 0 to array.length - 1
       minElement = minimum(minElement, array[i])
       maxElement = maximum(maxElement, array[i]) 
   range = maxElement - minElement
   for i = 0  to array.length - 1  
       index = int(array[i] * numBuckets / range)
       добавим array[i] в конец buckets[index]
   for i = 0 to numBuckets - 1
       buckets[i] = sort(buckets[i])
   for i = 0 to numBuckets - 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] = \dfrac {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]

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

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