Radix Sort program in python

Question

The following is a program that is for figuring out the radix sort technique, yet it doesn't show the right yield for each info. 

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

Not many instances of input/output cases are given underneath: - 

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 the right yield yet while considering the case underneath we misunderstand a 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 giving my best to figure it out. But still, I can't extract the exact issue.

Answer 1

The given program implements the radix sort technique, but it appears to have a logical error that leads to incorrect output in some cases. The issue lies in the line where the temporary variable tmp is calculated as tmp = i / placement. This division operation produces a floating-point number, which can lead to incorrect bucket placement.

To fix this issue, you need to ensure that tmp is calculated as an integer division by using the // operator instead of /. Modify the line to tmp = i // placement to perform integer division. This will ensure that the correct bucket is selected based on the digits at the current placement.

Here's the corrected code:

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 = int(input("Enter the number of elements you want to sort: "))

print("Enter the numbers:\n")

for i in range(n):

    num = int(input())

    A.append(num)

print(RadixSort(A))

With this correction, the radix sort algorithm should produce the correct output for the given input cases. Let me know if you have any further questions!

Answer 2

Well this is a decent code, however, you did a senseless mistake while indenting this placement *= RADIX 

As you are utilizing placement *= RADIX to move to the next digit, so it must be executed outside of the for loop 

In this way, the issue was with indenting placement *= RADIX

Kindly check the below code:

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

Are you pretty much interested to learn python in detail? Come and join the python training course to gain more knowledge.

To know more about this you can have a look at the following video tutorial:-

Answer 3

The provided program attempts to implement the radix sort technique but produces incorrect output in certain cases. The problem lies in the calculation of the temporary variable tmp using the division operator / instead of integer division operator //. To resolve this issue, replace the line tmp = i / placement with tmp = i // placement to ensure integer division is performed. This modification will correctly assign elements to their respective buckets based on the digits at the current placement. By making this adjustment, the program should produce the expected output.

Answer 4

The given program aims to implement the radix sort technique but exhibits an error leading to inaccurate output in specific scenarios. The issue arises from the computation of the temporary variable tmp using the division operator / instead of the integer division operator //. To rectify this, it is necessary to replace the line tmp = i / placement with tmp = i // placement to ensure integer division is performed. This adjustment guarantees that elements are appropriately assigned to their respective buckets based on the digits at the current placement. By implementing this modification, the program will generate the expected output.