Гравитационная сортировка

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

Алгоритм

Шаг 1: расположить бусины на шестах

Шаг 2: рассчитываем падение бусин.

Алгоритм гравитационной сортировки может быть сравнен с тем, как бусины падают вниз на параллельных шестах, например как в абаке, однако каждый из шестов может иметь разное количество бусин. Первым шагом для массива, символически изображенного в виде счетной доски, с четырьмя шестами и пятью рядами, например, нижний ряд изображает число 3, мы подвергаем их «гравитации» и позволяем упасть. Теперь последний ряд представляет собой самое большое число списка, а первый — наименьшее.

Механизм, лежащий в основе сортировки бусинок, аналогичен механизму сортировки подсчетом — количество бусин на каждом шесте соответствует количеству элементов со значением, равным или большим, чем индекс этого шеста.

Сложность алгоритма

Алгоритм сортировки гравитацией может быть реализован с четырьмя разными уровнями сложности:

• O(1) — падение бусин происходит одновременно, за один и тот же промежуток времени, как в примере выше. Данная реализация абстрактная и, скорее всего, не может быть реализована на практике.
• O(${\sqrt {n}}$), где 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 i in range(len(input_list)):
        # Подсчет значений больше i - это то, как мы узнаётся, сколько бусинок в
        # текущем самом нижнем ряду. Обратите внимание, что булевы значения Python могут быть
        # интерпретированны как целочисленные значения; True == 1 и False == 0.
        return_list.append(sum(n > i for n in transposed_list))
    # Возвращается список, отсортированный в убывающем порядке
    return return_list