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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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> блоков (карманов, корзин). Далее каждый из таких блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения. После сортировок внутри каждых блоков данные записываются в массив в порядке разбиения на блоки. При этом нужно учитывать, что данная сортировка работает только в том случае, если разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были больше предыдущего.
Строка 14: Строка 13:
  
 
На вход подаются вещественные числа.
 
На вход подаются вещественные числа.
−
  array bucketSort (array, min_element, max_element)  
+
  '''double[]''' bucketSort ('''double[]''' array, '''double''' minElement, '''double''' maxElement)  
−
     '''if''' array.length < 2 '''or''' min_element == max_element
+
     '''if''' array.length < 2 '''or''' minElement == maxElement
 
         '''return''' array;
 
         '''return''' array;
−
     range = max_element - min_element;
+
     range = maxElement - minElement;
 
     '''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] * numBuckets / range)
 
         добавим array[i] в конец buckets[index]
 
         добавим array[i] в конец buckets[index]
−
         buckets_minimum[i] = minimum(buckets[index], array[i])
+
         bucketsMinimum[i] = minimum(buckets[index], array[i])
−
         buckets_maximum[i] = maximum(buckets[index], array[i])
+
         bucketsMaximum[i] = maximum(buckets[index], array[i])
−
     '''for''' i = 0 '''to''' num_buckets - 1
+
     '''for''' i = 0 '''to''' numBuckets - 1
−
         buckets[i] = bucketSort(buckets[i], min_bucktes[i], max_buckets[i])
+
         buckets[i] = bucketSort(buckets[i], minBucktes[i], maxBuckets[i])
−
     '''for''' i = 0 '''to''' num_buckets - 1
+
     '''for''' i = 0 '''to''' numBuckets - 1
 
         '''for''' k = 0 '''to''' buckets[i].length - 1
 
         '''for''' k = 0 '''to''' buckets[i].length - 1
 
             добавим buckets[i][k] в конец answer
 
             добавим buckets[i][k] в конец answer
 
     '''return''' answer  
 
     '''return''' answer  
 
==== Нерекурсивная реализация ====
 
==== Нерекурсивная реализация ====
−
  array bucketSort(array)  
+
  '''double[]''' bucketSort('''double[]''' array)  
−
     min_element = Infinum
+
     minElement = Infinum
−
     max_element = -Infinum
+
     maxElement = -Infinum
 
     '''for''' i = 0 '''to''' array.length - 1
 
     '''for''' i = 0 '''to''' array.length - 1
−
         min_element = '''minimum'''(min_element, array[i])
+
         minElement = '''minimum'''(minElement, array[i])
−
         max_element = '''maximum'''(max_element, array[i])  
+
         maxElement = '''maximum'''(maxElement, array[i])  
−
     range = max_element - min_element;
+
     range = maxElement - minElement;
 
     '''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] * numBuckets / range)
 
         добавим array[i] в конец buckets[index]
 
         добавим array[i] в конец buckets[index]
−
     '''for''' i = 0 '''to''' num_buckets - 1
+
     '''for''' i = 0 '''to''' numBuckets - 1
 
         buckets[i] = quickSort(buckets[i])
 
         buckets[i] = quickSort(buckets[i])
−
     '''for''' i = 0 '''to''' num_buckets - 1
+
     '''for''' i = 0 '''to''' numBuckets - 1
 
         '''for''' k = 0 '''to''' buckets[i].length - 1
 
         '''for''' k = 0 '''to''' buckets[i].length - 1
 
             добавим buckets[i][k] в конец answer
 
             добавим buckets[i][k] в конец answer
Строка 54: Строка 53:
 
<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> 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] = n / k </tex>
+
<tex> E[n_i] = \frac {n}{k} </tex>
  
 
То есть, если <tex> n \sim k \Rightarrow  E[T(n)] = \Theta(n) </tex>  
 
То есть, если <tex> n \sim k \Rightarrow  E[T(n)] = \Theta(n) </tex>  

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

Пример работы рекурсивного 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]
       bucketsMinimum[i] = minimum(buckets[index], array[i])
       bucketsMaximum[i] = 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] = quickSort(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] = \frac {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]

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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Карманная_сортировка&oldid=47363»