Гравитационная сортировка
Гравитационная сортировка, также известная как сортировка бусинами (англ. Bead Sort) — алгоритм сортировки, разработанный Джошуа Аруланандхамом, Кристияном Калюдом и Майклом Диннином в 2002 году. Теоретически, сложность алгоритма может достигать O(n), хотя практические реализации зачастую показывают худший результат. Также, данный алгоритм может быть применён только к массиву натуральных чисел.
Алгоритм


Алгоритм гравитационной сортировки может быть сравнен с тем, как бусины падают вниз на параллельных шестах, например как в абаке, однако каждый из шестов может иметь разное количество бусин. Первым шагом для массива, символически изображенного в виде счетной доски, с четырьмя шестами и пятью рядами, например, нижний ряд изображает число 3, мы подвергаем их «гравитации» и позволяем упасть. Теперь первый ряд представляет собой самое большое число списка, а первый — наименьшее.
Механизм, лежащий в основе сортировки бусинок, аналогичен механизму сортировки подсчетом — количество бусин на каждом шесте соответствует количеству элементов со значением, равным или большим, чем индекс этого шеста.
Сложность алгоритма
Алгоритм сортировки гравитацией может быть реализован с четырьмя разными уровнями сложности:
- O(1) — падение бусин происходит одновременно, за один и тот же промежуток времени, как в примере выше. Данная реализация абстрактная, и скорее всего не может быть реализована на практике.
- O(), где n — количество рядов — В реалистичной симуляции гравитации, время затрачиваемое на расчет падения бусин прямо пропорционален квадратному корню из количества рядов.
- O(n) — Бусины просчитываются по одному ряду за раз. Это тот случай, когда используются аналоговые и цифровые аппаратные решения.
- O(S), где S — сумма всех чисел в изначальном массиве — Каждая бусина просчитывается индивидуально.
Также как и со сортировкой подсчетом со списком, гравитационная сортировка ведет себя неожиданно в худшем случае — расчет будет проведен быстрее чем O(n log n).
Имплементация
Имплементация на языке программирования Python:
def beadsort(input_list):
"""Гравитационная сортировка."""
return_list = []
# Создаем список с упавшими бусинами. Его максимальная длина
# такая же как и максимальное значение входного списка.
transposed_list = [0] * max(input_list)
for num in input_list:
# Для каждого элемента входного списка,
# опустить бусину, с помощью инкрементирования кол-ва элементов
# списка transposed list равного высоте шеста.
# Бусины будут накапливаться поверх предыдущих.
transposed_list[:num] = [n + 1 for n in transposed_list[:num]]
# Для отмены транспонирования мы считаем
# самый нижний ряд выпавших бусинок, затем имитируем удаление этой
# строки путем вычитания 1 из каждого столбца транспонированного списка.
# Когда столбец не достигает высоты текущей строки,
# его значение в transposed_list будет <= 0.
for _ in input_list:
# Подсчет значений больше 0 - это то, как мы узнаем, сколько бусинок в
# текущем самом нижнем ряду. Обратите внимание, что булевы значения Python могут быть
# интерпретированны как целочисленные значения; True == 1 и False == 0.
return_list.append(sum(n > 0 for n in transposed_list))
# Убираем нижний ряд.
transposed_list = [n - 1 for n in transposed_list]
# Возвращаем отсортированный список.
# Список отсортирован в убывающем порядке.
return return_list