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

Гравитационная сортировка, также известная как сортировка бусинами (англ. 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 _ 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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.