Question

Implement Radix Sort using PYTHON programming language. Use one of the two options for the algorithm to sort

the digits: Use Counting Sort or Bucket Sort.

• Assume the numbers are maximum 4-digit numbers.

• If using Counting Sort, you can see that your digit range is between 0 and 9 ([0…9]).

• If using Bucket Sort, you will have ten buckets labeled from 0 to 9.

Please add comments and explain every step carefully.

Answer 1

def countsort(ar,ee):
n = len(ar)
out = [0] * (n)
cnt = [0] * (10)
for i in range(0, n):
index = (ar[i]/ee)
cnt[int((index)%10)]+=1
for i in range(1,10):
cnt[i] += cnt[i-1]
i = n-1
while i>=0:
index = (ar[i]/ee)
out[ cnt[ int((index)%10) ] - 1] = ar[i]
cnt[int((index)%10) ] -= 1
i -= 1
for i in range(0,len(ar)):
ar[i] = out[i]
return ar

def radixSort(ar):
mx = max(ar)
exp = 1
while mx/exp > 0:
ar=countsort(ar,exp)
exp *= 10
return ar

ar = [ 170, 45, 75, 90, 802, 24, 2, 66]
ar=radixSort(ar)

for i in range(len(ar)):
print(ar[i],end=" ")