Привет! Двигаясь вперед и опираясь на то, что мы узнали о Сортировке подсчетом, мы попытаемся демистифицировать сортировку по основанию.

Radix Sort использует последовательные процессы сортировки. Например, взяв массив целых чисел, мы собираемся сначала отсортировать элементы на основе значения их младшей значащей цифры (места единицы). Затем мы снова отсортируем их по значению десятого места. И так до последнего (самого) значимого места. Обратите внимание, что мы обсуждаем только LSD Radix Sort, которая реализована таким образом, чтобы начинать с наименее значащей цифры и продвигаться оттуда вверх. Существует также MSD Radix Sort, который начинает процессы сортировки с самой (самой правой) значащей цифры и перемещается оттуда вниз (влево) к младшей значащей цифре.

С точки зрения сложности, сортировка по основанию имеет сложность O(N*K), где N — количество элементов, а K — диапазон элементов. Это делает Radix Sort довольно надежным кандидатом. В настоящее время этот алгоритм чаще всего используется при сортировке коллекций двоичных строк и целых чисел, где он действительно может превзойти другие алгоритмы сортировки.

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

Пришло время глубоко погрузиться на числовом практическом примере. Рассмотрим arr=[250, 65, 86, 34, 407, 23, 2, 68, 7, 9]. Крайне важно — с единственной целью демонстрации — выбрать широкий диапазон чисел, охватывающий также многозначные числа. Если бы мы выбрали только числа меньше 10, например, мы бы снова сократили алгоритм сортировки по основанию до истории Сортировка подсчетом, поскольку мы будем сортировать массив только один раз, по первой цифре. Теперь вернемся к нашему примеру. Предположим, мы хотим отсортировать его в порядке возрастания. Алгоритм будет работать так:

  • exp=1; Элемент max равен 407. Поскольку exp › max, мы запустим алгоритм сортировки по младшей значащей цифре (1). Теперь массив становится arr=[250, 2, 23, 34, 65, 86, 407, 7, 68, 9]. Обратите внимание, как он отсортирован по первой цифре каждого числа; также обратите внимание на его стабильность, которую мы обсуждали ранее, поскольку 407 по-прежнему предшествует 7 даже после этого первого запуска сортировки, сохраняя порядок, который эти два разделяли до этого шага сортировки;
  • exp=10; Элемент max равен 407. Поскольку exp › max, мы запустим алгоритм сортировки для следующей значащей цифры (10). Теперь массив становится arr=[2, 407, 7, 9, 23, 34, 250, 65, 68, 86]. Обратите внимание, как на этот раз он отсортирован по второй цифре каждого числа; опять же, функция стабильности сортировки подсчетом и, как следствие, сортировки по основанию по-прежнему ставит 407 перед 7;
  • exp=100; Элемент max равен 407. Поскольку exp › max, мы запустим алгоритм сортировки по следующей значащей цифре (100). Теперь массив становится arr=[2, 7, 9, 23, 34, 65, 68, 86, 250, 407]. Это окончательная форма массива. Он полностью отсортирован в порядке возрастания, и мы можем безопасно вернуть его нашему вызывающему объекту, потому что exp теперь будет установлено на 1000, что превышает максимальный элемент массива — 407 — и эффективно завершает цикл. .
def counting_sort(arr, exp):
    """Counting sort method."""
    arr_length = len(arr)
    output = [0] * arr_length
    count = [0] * 10
    for i in range(arr_length):
        index = arr[i] / exp
        count[int(index % 10)] += 1
    # build prefix sums
    # this is used in ascending order sorting
    for i in range(1, 10):
        count[i] += count[i - 1]
    # if we want descending order, use this instead
    # for i in range(8, -1, -1):
    #     count[i] += count[i + 1]
    
    for i in range(arr_length - 1, -1, -1):
        index = arr[i] / exp
        output[count[int(index % 10)] - 1] = arr[i]
        count[int(index % 10)] -= 1
    arr[:] = output

def radix_sort(arr):
    """Main function."""
    # get maximum element of the array
    maximum = max(arr)
    # set exp to 1 (least significant digit)
    exp = 1
    
    # sort by digit, then move to next significant digit
    while maximum > exp:
        counting_sort(arr, exp)
        exp *= 10
    return arr

Хотя процесс Radix Sort совсем не такой сложный, должно оказаться полезным сравнить вариант алгоритма Counting Sort, использованный в этом примере, с тем, который использовался, когда мы ранее анализировали Counting Sort. Этот новый вариант использует exp в качестве аргумента и слегка измененный механизм для получения правильного позиционирования элементов.

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

Удачного кодирования, и я с нетерпением жду следующего! Ваше здоровье!