Python Radix Sort

Question

Я пытаюсь реализовать сортировку Radix в python.

Моя текущая программа работает неправильно, так как список, подобный [41,51,2,3,123], будет правильно отсортирован до [2,3,41,51,123], но что-то вроде [52,41,51, 42,23] станет [23,41,42,52,51] (52 и 51 находятся в неправильном месте).

Я думаю, что знаю, почему это происходит, потому что, сравнивая цифры в десятках мест, я не сравниваю единицы (то же самое для более высоких степеней 10).

Как исправить эту проблему, чтобы моя программа работала максимально быстро? Благодаря!

def radixsort(aList): 
    BASEMOD = 10 
    terminateLoop = False 
    temp = 0 
    power = 0 
    newList = [] 
    while not terminateLoop: 
     terminateLoop = True 
     tempnums = [[] for x in range(BASEMOD)] 

     for x in aList: 
      temp = int(x/(BASEMOD ** power)) 
      tempnums[temp % BASEMOD].append(x) 
      if terminateLoop: 
       terminateLoop = False 


     for y in tempnums: 
      for x in range(len(y)): 
       if int(y[x]/(BASEMOD ** (power+1))) == 0: 
        newList.append(y[x]) 
        aList.remove(y[x]) 



     power += 1 

    return newList 

print(radixsort([1,4,1,5,5,6,12,52,1,5,51,2,21,415,12,51,2,51,2])) 

Answer 1

В настоящее время ваш вид не делает ничего, чтобы переупорядочить значения на основе чего-либо, кроме их наивысшей цифры. Вы получаете 41 и 42 право только случайно (так как они находятся в правильном относительном порядке в исходном списке).

Вы должны всегда создавать новый список на основе каждого цикла сортировки.

def radix_sort(nums, base=10): 
    result_list = [] 
    power = 0 
    while nums: 
     bins = [[] for _ in range(base)] 
     for x in nums: 
      bins[x // base**power % base].append(x) 
     nums = [] 
     for bin in bins: 
      for x in bin: 
       if x < base**(power+1): 
        result_list.append(x) 
       else: 
        nums.append(x) 
     power += 1 
    return result_list 

Обратите внимание, что сортировка radix не обязательно быстрее, чем сортировка на основе сравнения. Он имеет меньшую сложность, если количество отсортированных элементов больше, чем диапазон значений элемента. Его сложностью является O(len(nums) * log(max(nums))), а не O(len(nums) * log(len(nums))).