Карманная сортировка

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Пример работы рекурсивного 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]

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

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

• Wikipedia — Bucket sort
• Википедия — Блочная сортировка

• Презентация о линейных сортировках
• Описание алгоритма с реализацией рекурсивной версии на языке Java