Гравитационная сортировка, также известная как сортировка бусинами () — алгоритм сортировки, разработанный Джошуа Аруланандхамом, Кристияном Калюдом и Майклом Диннином в 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 = * 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
Категория:Алгоритмы сортировки