Сортировка бисера

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

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

Шаг 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): Все бусины перемещаются одновременно в одну и ту же единицу времени, как и в случае с простым физическим примером, приведенным выше. Это абстрактная сложность, и ее невозможно реализовать на практике.
• О ( ${\sqrt {n}}$): В реалистичной физической модели, использующей гравитацию, время, необходимое для падения бусинок, пропорционально квадратному корню из максимальной высоты, которая пропорциональна n.
• О (н): Бисерины перемещаются по одному ряду. Именно этот случай используется в аналоговых и цифровых аппаратных решениях.
• O (S), где S — сумма целых чисел во входном наборе: каждая бусинка перемещается индивидуально. Это тот случай, когда сортировка шариков реализуется без механизма, помогающего находить пустые места под шариками, например, в программных реализациях.

Как и сортировка Pigeonhole , сортировка шариками необычна тем, что в худшем случае она может работать быстрее, чем 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 i in range(len(input_list)):
        # Counting values > i 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 > i for n in transposed_list))
    # The resulting list is sorted in descending order
    return return_list

Мы также можем реализовать алгоритм с помощью Java .

    public static void beadSort(int[] a)
    {
        // Find the maximum element
        int max = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
 
        // allocating memory
        int[][] beads = new int[a.length][max];
 
        // mark the beads
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i]; j++) {
                beads[i][j] = 1;
            }
        }
 
        // move down the beads
        for (int j = 0; j < max; j++) {
            int sum = 0;
            for (int i = 0; i < a.length; i++) {
                sum += beads[i][j];
                beads[i][j] = 0;
            }
 
            for (int i = a.length - 1; i >= a.length - sum;
                 i--) {
                a[i] = j + 1;
            }
        }
    }

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

• «Сортировка бисером: естественный алгоритм сортировки» (PDF) . Архивировано из оригинала (PDF) 9 августа 2017 г. Проверено 1 января 2005 г.   (114 КиБ )
• Bead Sort в MGS — визуализация сортировки, реализованная на MGS . языке программирования
• Сортировка по бусинкам на MathWorld
• Интерактивная визуализация Bead Sort