Question

IN PYTHON 3:

In this version of Radix Sort we use Queues very naturally. Let us consider the following set of positive integers:

311, 96, 495, 137, 158, 84, 145, 63

We will sort these numbers with three passes. The number of passes is dependent on the number of digits of the largest number - in this case it is 495.

In the first pass we will go through and sort the numbers according to the digits in the units place (or the right most digit) and place the numbers in 10 queues for each of the digits 0 through 9. After this has been done we will dequeue the numbers in all the queues and enqueue them in an eleventh queue.

In the second pass, we will go through and sort the numbers according to the digits in the tens place and enqueue the numbers in the 10 queues. After this has been done, we will dequeue the numbers in all the queues and enqueue them in the eleventh queue - and so on.

Here are what the passes will look like:

Pass 0:
Q10: 311, 96, 495, 137, 158, 84, 145, 63

Pass 1:
Q0: 
Q1: 311
Q2:
Q3: 63
Q4: 84
Q5: 495, 145
Q6: 96
Q7: 137
Q8: 158
Q9:

Q10: 311, 63, 84, 495, 145, 96, 137, 158

Pass 2:
Q0:
Q1: 311
Q2: 
Q3: 137
Q4: 145
Q5: 158
Q6: 63
Q7:
Q8: 84
Q9: 495, 96

Q10: 311, 137, 145, 158, 63, 84, 495, 96

Pass 3: Assume that the 2-digit numbers have a leading zero
Q0: 63, 84, 96
Q1: 137, 145, 158
Q2:
Q3: 311
Q4: 495
Q5:
Q6:
Q7:
Q8:
Q9:

Q10: 63, 84, 96, 137, 145, 158, 311, 495

Now dequeue Q10 and the numbers are sorted.

For this assignment you will modify this algorithm so that it will take strings as input that have lower case letters and digits. Assume that the input is correct. Remember that according to the ASCII table digits come before letters.

Here are some recommendations that we would like to make. You do not have to follow our recommendations.

• Instead of naming the queues Q0, Q1, and so on. Create a list and keep your Queue objects there.
• Maintain a dictionary where the key is a character (either a digit or a lower case letter) and the value is an index in the above list.

Input:
You will be given an input of the following format. The first line in the input will be a single integer n that states the number of strings to follow. This will be followed by n lines where there will be a single string per line. Each string will have between 1 and 10 characters inclusive. The characters will be either the digits 0 through 9 or the letters 'a' through 'z'.

Output:
You will output a list having the strings in sorted order.

Answer 1

Radix Sort Algorithm:

def countingSort(array, place):

    size = len(array)

    output = [0] * size

    count = [0] * 10

    for i in range(0, size):

        index = array[i] // place

        count[index % 10] += 1

    for i in range(1, 10):

        count[i] += count[i - 1]

    i = size - 1

    while i >= 0:

        index = array[i] // place

        output[count[index % 10] - 1] = array[i]

        count[index % 10] -= 1

        i -= 1

    for i in range(0, size):

        array[i] = output[i]

def radixSort(array):

    max_element = max(array)

    place = 1

    while max_element // place > 0:

        countingSort(array, place)

        place *= 10

data = [311, 96, 495, 137, 158, 84, 145, 63]

radixSort(data)

print(data)

Hope this is helpful.