CODEWITHSUNDEEP
pythonsortingradix-sort
user5514593
user5514593

Reputation:

Radix Sort program in python

Below is a program that is for sorting through the radix sort method, but it does not show the correct output for every input.

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))

few examples of input / output cases are given below : -

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

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

Here we get correct output but while considering the case below we get a wrong output

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'm trying to figure it out but unable to fetch the exact problem.

Upvotes: 2

Views: 5543

Answers (3)

Tyler Justinen-Teite
Tyler Justinen-Teite

Reputation: 11

I was playing around this morning and made this, it's a recursive Radix function. It works with any amount of digits so the list can be just random natural numbers.

# Get a digit from a number (right to left starting at 0)
def getDigit(number, digit):
    return number // 10**digit % 10

# Needed for the Count Sort inside the Radix
def prefixSum(toCalc=[]):
    for i in range (1, len(toCalc)):  
        toCalc[i] += toCalc[i-1]
    return toCalc

# Recursive radix sorting algorithm 
def radix(unsortedList, counter):
    # Allocate an empty list the same size as the unsorted list                    
    tempList = [None] * len(unsortedList) 
    # Used to store numbers from 0, 9
    counts = [0] * 10
    # for all the numbers, get the int[counter] and add to counts[]
    #   i.e. 231[1] = 3 
    for c in unsortedList:
        counts[getDigit(c, counter)] += 1
    prefixSum(counts)
    # Rearrange unsortedList to tempList
    for it in reversed(unsortedList):
        counts[getDigit(it, counter)] -= 1
        tempList[counts[getDigit(it, counter)]] = it

    # If the number of iterations is < the largest digit length in the list
    # Run a pass on sorting the list again
    if counter < len(str(max(unsortedList))):
        # Recursion
        return radix(tempList, counter + 1)
    # Done sorting    
    else:            
        return unsortedList

Upvotes: 1

Amit Upadhyay
Amit Upadhyay

Reputation: 7401

Well this is a good code, but you did a silly mistake while indenting this placement *= RADIX

As you are using placement *= RADIX to move to next digit, so it has to be executed out of the for loop

So, the problem was with indenting placement *= RADIX

you can change a little bit of your code to:-

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 : ")
n = int(n)
print("Enter the numbers : \n")
for i in range(0, n):
    num = int(input())
    A.append(num)
print(RadixSort(A))

Upvotes: 2

kshitij srivastava
kshitij srivastava

Reputation: 131

I have a simpler method assuming that maximum number in the list is a 3 digit number

Code:

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 = [[],[],[],[],[],[],[],[],[],[]]
    for s in range(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)

Upvotes: 0

Related Questions