Программа Radix Sort в python

Question

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

def RadixSort(A): 
    RADIX = 10 
    maxLength = False 
    tmp , placement = -1, 1 

    while not maxLength: 
     maxLength = True 
     buckets = [list() for _ in range(RADIX)] 
     for i in A: 
      tmp = i/placement 
      buckets[tmp % RADIX].append(i) 
      if maxLength and tmp > 0: 
       maxLength = False 

     a = 0 
     for b in range(RADIX): 
      buck = buckets[b] 
      for i in buck: 
       A[a] = i 
       a += 1 
     placement *= RADIX 
    return A 
A = [] 
n = input("Enter the numebr of elements you want to sort : ") 
n = int(n) 
print("Enter the numbers : \n") 
for i in range(0, n): 
    num = int(input()) 
    A.append(num) 
print(RadixSort(A)) 

несколько примеров ввода-вывода случаев/приведены ниже: -

Enter the numebr of elements you want to sort : 5 
Enter the numbers : 

5 
4 
3 
2 
1 
[1, 2, 3, 4, 5] 

Здесь мы получаем правильный вывод, но при рассмотрении дела ниже мы получим неверные результаты

Enter the numebr of elements you want to sort : 9 
Enter the numbers : 

50 
41 
700 
96 
4 
00 
4 
6 
852 
[50, 700, 0, 41, 852, 4, 4, 96, 6] 

I Я пытаюсь понять это, но не могу найти точную проблему.

Answer 1

Ну это хороший код, но вы сделали глупую ошибку при отступах этого placement *= RADIX

Как вы используете placement *= RADIX, чтобы перейти к следующей цифре, поэтому он должен быть выполнен из для цикла

Таким образом, проблема была с отступом placement *= RADIX

вы можете изменить немного кода, чтобы: -

def RadixSort(A): 
    RADIX = 10 
    maxLength = False 
    tmp , placement = -1, 1 

    while not maxLength: 
     maxLength = True 
     buckets = [list() for _ in range(RADIX)] 
     for i in A: 
      tmp = i/placement 
      buckets[tmp % RADIX].append(i) 
      if maxLength and tmp > 0: 
       maxLength = False 

     a = 0 
     for b in range(RADIX): 
      buck = buckets[b] 
      for i in buck: 
       A[a] = i 
       a += 1 
    # move to next digit 
    placement *= RADIX 
    return A 
A = [] 
n = input("Enter the numebr of elements you want to sort : ") 
print("Enter the numbers : \n") 
for i in range(0, n): 
    num = int(input()) 
    A.append(num) 
print(RadixSort(A)) 

Answer 2

У меня есть более простой метод, предполагающий, что максимальное число в списке 3-значное число

a = [432, 123, 900, 457, 792, 831, 528,320, 1, 2, 3, 45, 56, 65 , 96, 32, 0,0,0, 3, 4, 900, 999] def radix_sort (a): list1 = [] list2 = [] final = [] plist = [[], [] , [], [], [], [], [], [], [], []] plist1 = [[], [], [], [], [], [], [], [], [], []] plist2 = [[], [], [], [], [], [], [], [], [], []] для s в диапазоне (len (a)): x = a [s]% 10 plist [x] .append (a [s])

for i in range(len(plist)): 
    for s in range(len(plist[i])): 
     list1.append(plist[i][s]) 

for s in range(len(list1)): 
    x=(list1[s] % 100)/10 
    plist1[x].append(list1[s]) 

for i in range(len(plist1)): 
    for s in range(len(plist1[i])): 
     list2.append(plist1[i][s]) 

for s in range(len(list2)): 
    x=(list2[s]/100) 
    plist2[x].append(list2[s]) 

for i in range(len(plist2)): 
    for s in range(len(plist2[i])): 
     final.append(plist2[i][s]) 
print (" input list " , a) 
print (" sorted list : " , final)