Карманная сортировка
| НЕТ ВОЙНЕ |
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
| Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
| meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Карманная сортировка (англ. Bucket sort) — алгоритм сортировки, основанный на предположении о равномерном распределении входных данных.
Содержание
Алгоритм сортировки
Принцип работы
Для карманной сортировки нужно разбить элементы массива входных данных на блоков (карманов, корзин). Далее каждый из таких блоков сортируется либо другой сортировкой, либо рекурсивно тем же методом разбиения. После сортировок внутри каждых блоков данные записываются в массив в порядке разбиения на блоки. При этом нужно учитывать, что данная сортировка работает только в том случае, если разбиение на блоки производится таким образом, чтобы элементы каждого следующего блока были больше предыдущего.
Карманная сортировка сильно деградирует при большом количестве мало отличных элементов (большинство элементов попадёт в одну корзину). Поэтому такой тип сортировки использовать, когда велика вероятность того, что числа редко повторяются (например, последовательность случайных чисел).
Реализация
Существует несколько разных реализаций карманной сортировки.
Рассмотрим рекурсивную и нерекурсивную реализации.
Рекурсивный 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
Асимптотика
Пусть — количество элементов в массиве, — количество блоков для разбиения.
— случайная величина, обозначающая количество элементов попавших в -ый карман.
, где время работы алгоритма карманной сортировки.
То есть, если
Если,
Из приведенных выше формул, видно, что в среднем "карманная сортировка" работает за линейное время.
