Поразрядная сортировка со списками. Не могу придумать, как поддерживать вложенность массивов для произвольного числа разрядов

Question

Поразрядная сортировка массива со списками. Не могу придумать, как поддерживать вложенность массивов для произвольного числа разрядов. Получилось только для двух разрядов, и то с помощью условников.

реализация сортировки похожа на MSD(Most Significant Digit radix sort), только здесь используются вложенные списки(по итогу получается многомерный массив):

распределение исходного массива чисел по 10 массивам взависимости от числа старшего разряда(от 0 до 9)
следующий разряд распределяется по такому же принципу(10 массивов) но уже по найденым массивам на первом шаге. и т.д.

В итоге получаем многомерный массив, а после его объединения в один массив получаем отсортированную последовательность

#преобразование многомерного массива в один массив
 def set_mass(mass):
     arr = []
     for i in mass:
         if type(i) != list:
             arr.append(i)
         else:
             arr += set_mass(i)
     return arr

 #начало программы

 list_0 = [[] for i in range(10)] # 10 списков для сортировки чисел (корзины: 0, 1, 2 ... 9)
 mass = [1, 22, 50, 4, 66, 5, 1, 0] # исходный массив
 length = len(str(max(mass))) # максимальное число разрядов

 # преобразование массива для сортировки по разрядам
 mass_num = []
 for num in mass:
     count_zero = length - len(str(num))
     mass_num.append('0' * count_zero + str(num))

 mass_f = []

 for i in range(length):
     # сортировка по первому разряду
     if i == 0:
         for num in mass_num:
             discharge = int(num[i]) # вычисление номера массива, в который нужно вставить число
             list_0[discharge].append(num)

     # сортировка по второму разряду
     if i == 1:
         for mass in list_0:
             list_2 = [[] for j in range(10)]
             for num in mass:
                 discharge = int(num[i])
                 list_2[discharge].append(int(num))
             mass_f.append(list_2)

 #отсортированный массив
 print(set_mass(mass_f))

Если все сделать так как сказал Stanislav Volodarskiy, появится ошибка, вот например при таком массиве:

mass = [1, 22, 10123, 4, 66, 5, 1000, 0]

Получим:

mass = [0, 1000, 1, 22, 4, 5, 66, 10123]

Answer 1

Most Significant Digit radix sort рекурсивный. Значит рекурсия.

Следуя идеям из вопроса превращаем целые без знака в строки равной длины. Короткие строки дополняются слева (rjust) нулями:

# <- [1, 22, 50, 4, 66, 5, 1, 0]
# -> 2, ['01', '22', '50', '04', '66', '05', '01', '00']
def align(a):
    aa = list(map(str, a))
    max_len = max(map(len, aa))
    return max_len, [v.rjust(max_len, '0') for v in aa]

Теперь сортировка. Она рекурсивная. Сортируем старшие цифры, в получившихся корзинах сортируем следующие цифры и так далее:

# <- 0, 2, ['01', '22', '50', '04', '66', '05', '01', '00']
# -> [[['00'], ['01', '01'], ['04'], ['05']], [['22']], [['50']], [['66']]]
def sort_by_digit(i, n, a):
    if i >= n:
        return a
    bins = [[] for _ in range(10)]
    for v in a:
        bins[int(v[i])].append(v)
    return [sort_by_digit(i + 1, n, b) for b in bins if len(b) > 0]

Результат сортировки - сбалансированное дерево (все поддеревья одной высоты). Его нужно обойти:

# <- 2, [[['00'], ['01', '01'], ['04'], ['05']], [['22']], [['50']], [['66']]]
# -> ['00', '01', '01', '04', '05', '22', '50', '66']
def merge(n, bins):
    if n == 0:
        yield from bins
    else:
        for b in bins:
            yield from merge(n - 1, b)

Превращаем строки обратно в числа:

# <- ['00', '01', '01', '04', '05', '22', '50', '66']
# -> [0, 1, 1, 4, 5, 22, 50, 66]
list(map(int, ...))

Всё вместе:

# <- [1, 22, 50, 4, 66, 5, 1, 0]
# -> [0, 1, 1, 4, 5, 22, 50, 66]
def msd_radix_sort(a):
    n, aa = align(a)
    tree = sort_by_digit(0, n, aa)
    return list(map(int, merge(n, tree)))

БЛОГ НА HUSL

Поразрядная сортировка со списками. Не могу придумать, как поддерживать вложенность массивов для произвольного числа разрядов

Ответы (1 шт):