Radix Sort — самая быстрая сортировка для чисел и строк

Сортировки нужны для ускорения работы программ: когда у нас много данных, нам нужно как-то их организовать, чтобы по ним было легко искать и быстро обрабатывать. На небольших наборах данных это незаметно, но когда нужно работать с сотнями тысяч единиц данных, сортировка может либо ускорить работу программы, либо намертво её повесить. 

Люди изобрели много сортировок для разных данных и под разные задачи. Сегодня расскажем про поразрядную сортировку — это почти как сортировка по алфавиту, но для данных. В английском языке это называется Radix sort — сортировка по основанию системы счисления.

Чтобы оценить скорость работы этого алгоритма, посмотрите видео — там собраны 24 популярных алгоритма, которые обрабатывают один массив данных. Поразрядная сортировка — вторая слева в нижнем ряду. Вы узнаете её по тому, что она закончит работу в числе первых: 

Сегодняшняя статья будет полезна для расширения компьютерного кругозора и погружения в мир информатики. Она не особо нужна для прикладной разработки, потому что там все эти сортировки уже реализованы и работают автоматически. Но чем круче вы в мире ИТ, тем больше вы будете ценить гениальность поразрядной сортировки.

Что такое основание и разряд

Принцип работы поразрядной сортировки

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

Например, чтобы понять, как отсортировать числа [137137105157, 24395739293, 474290561035, 5, 276, 42], алгоритм сделает так:

Пишем алгоритм

Чтобы написать алгоритм поразрядной сортировки, используем Python — с ним код будет понятнее. Ещё мы будем в одном месте использовать нижнее подчёркивание в качестве имени переменной — с точки зрения синтаксиса так можно, это такое же имя переменной, как x или max_count. Смысл в том, что разработчики договорились использовать нижнее подчёркивание как переменную там, где переменная нужна только один раз, например при организации цикла через range(). Проще говоря, нижнее подчёркивание говорит нам, что эта переменная больше нигде не используется, только в этом месте.

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

# поразрядная сортировка
def radix_sort(arr):
    
    # находим размер самого длинного числа
    max_digits = max([len(str(x)) for x in arr])

    # основание системы счисления
    base = 10

    # создаём промежуточный пустой массив из 10 элементов
    bins = [[] for _ in range(base)]

    # перебираем все разряды, начиная с нулевого
    for i in range(0, max_digits):
        # для удобства выводим текущий номер разряда, с которым будем работать
        print('✅ Номер разряда → ' + str(i))
        # перебираем все элементы в массиве
        for x in arr:
            # получаем цифру, стоящую на текущем разряде в каждом числе массива
            digit = (x // base ** i) % base
            # отправляем число в промежуточный массив в ячейку, которая совпадает со значением этой цифры 
            bins[digit].append(x)
        # собираем в исходный массив все ненулевые значения из промежуточного массива
        arr = [x for queue in bins for x in queue]
        # текущее состояние массива
        print(arr)
        # текущее состояние промежуточного массива
        print(bins)

        # очищаем промежуточный массив
        bins = [[] for _ in range(base)]

    # возвращаем отсортированный массив
    return arr


# запускаем сортировку
print(radix_sort([137137105157, 24395739293, 474290561035, 5, 276, 42]))

Любите математику? Это для вас

Попробуйте бесплатный тренажер «Основы математики для цифровых профессий». Это все необходимые знания, чтобы закрыть пробелы в математике для айтишника.

Попробовать бесплатно