Сорт бисера - Bead sort

Бусина рода , также называемый гравитационный рода , является естественным алгоритм сортировки , разработанный Джошуа Дж Arulanandham , Кристиан S Калуд и Майкл Дж Dinneen в 2002 году и опубликованы в Бюллетене Европейской ассоциации по теоретической информатике . Как цифровые, так и аналоговые аппаратные реализации сортировки шариков могут достичь времени сортировки O ( n ); однако реализация этого алгоритма обычно значительно медленнее в программном обеспечении и может использоваться только для сортировки списков положительных целых чисел . Кроме того, казалось бы, что даже в лучшем случае алгоритм требует O ( n 2 ) пространства.

Обзор алгоритма

Шаг 1: Подвешиваем бусинки на вертикальные столбы.
Шаг 2: Бусинки упали.

Операцию сортировки бусинок можно сравнить с тем, как бусинки скользят по параллельным полюсам, например, на счетах . Однако на каждом полюсе может быть разное количество бусинок. Вначале может быть полезно представить бусины, подвешенные на вертикальных столбах. На шаге 1 такое расположение отображается с использованием n = 5 рядов бусинок на m = 4 вертикальных полюсах. Цифры справа от каждой строки указывают номер, который представляет данная строка; строки 1 и 2 представляют положительное целое число 3 (потому что каждая из них содержит три бусинки), а верхняя строка представляет положительное целое число 2 (поскольку она содержит только две бусинки).

Если затем мы позволим бусинам упасть, строки теперь будут представлять одни и те же целые числа в отсортированном порядке. Строка 1 содержит наибольшее число в наборе, а строка n - наименьшее. Если было выполнено вышеупомянутое соглашение о рядах, содержащих ряд бусинок на полюсах 1 .. k и оставляющих полюса k +1 .. m пустыми, то это будет продолжаться и здесь.

Действие, позволяющее бусинам «падать» в нашем физическом примере, позволило большим значениям из верхних рядов распространиться на нижние ряды. Если значение, представленное строкой a , меньше, чем значение, содержащееся в строке a + 1 , некоторые из бусинок из строки a + 1 попадут в строку a ; это обязательно произойдет, поскольку ряд a не содержит бусинок в этих положениях, чтобы предотвратить падение бусинок ряда a + 1 .

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

Сложность

Сортировка бусинок может быть реализована с четырьмя общими уровнями сложности, среди прочего:

  • O (1): все шарики перемещаются одновременно в одной и той же единице времени, как в случае с простым физическим примером выше. Это абстрактная сложность, и ее невозможно реализовать на практике.
  • O ( ): в реалистичной физической модели, использующей гравитацию, время, необходимое для того, чтобы шарики упали, пропорционально квадратному корню из максимальной высоты, который пропорционален n.
  • O (n): бусинки перемещаются по одному ряду за раз. Это тот случай, когда используются аналоговые и цифровые аппаратные решения.
  • O (S), где S - сумма целых чисел во входном наборе: каждая бусина перемещается индивидуально. Это тот случай, когда сортировка шариков реализована без механизма, помогающего находить пустые места под шариками, например, в программных реализациях.

Подобно сортировке в голубятне, сортировка по граням необычна тем, что в худшем случае она может работать быстрее, чем O ( n log n ), что является максимальной производительностью, возможной для сортировки сравнения в худшем случае. Это возможно, потому что ключ для сортировки шариков всегда является положительным целым числом, и сортировка шариков использует его структуру.

Выполнение

Эта реализация написана на Python; предполагается, что это input_list будет последовательность целых чисел. Функция возвращает новый список, а не изменяет переданный, но ее можно тривиально изменить для эффективной работы на месте. 

def beadsort(input_list):
    """Bead sort."""
    return_list = []
    # Initialize a 'transposed list' to contain as many elements as
    # the maximum value of the input -- in effect, taking the 'tallest'
    # column of input beads and laying it out flat
    transposed_list = [0] * max(input_list)
    for num in input_list:
        # For each element (each 'column of beads') of the input list,
        # 'lay the beads flat' by incrementing as many elements of the
        # transposed list as the column is tall.
        # These will accumulate atop previous additions.
        transposed_list[:num] = [n + 1 for n in transposed_list[:num]]
    # We've now dropped the beads. To de-transpose, we count the
    # 'bottommost row' of dropped beads, then mimic removing this
    # row by subtracting 1 from each 'column' of the transposed list.
    # When a column does not reach high enough for the current row,
    # its value in transposed_list will be <= 0.
    for _ in input_list:
        # Counting values > 0 is how we tell how many beads are in the
        # current 'bottommost row'. Note that Python's bools can be
        # evaluated as integers; True == 1 and False == 0.
        return_list.append(sum(n > 0 for n in transposed_list))
        # Remove the 'bottommost row' by subtracting 1 from each element.
        transposed_list = [n - 1 for n in transposed_list]
    # The resulting list is sorted in descending order
    return return_list

Ссылки и примечания

  1. ^ Аруланандхам, Джошуа Дж .; Calude, Cristian S .; Диннин, Майкл Дж. (Январь 2002 г.). "Bead-Sort: естественный алгоритм сортировки" (PDF) . Департамент компьютерных наук Оклендского университета . Проверено 14 мая 2021 .
  2. ^ По соглашению, строка, представляющая положительное целое число k, должна иметь бусинки на полюсах 1 .. k, а полюса k +1 .. m должны быть пустыми. Это не строгое требование, но, скорее всего, упростит реализацию.

Внешние ссылки