Radix sort is a sorting algorithm that is used if the items we are going to sort are in a large range, for instance, from 0 to 9999. In this sorting algorithm, we sort from the least significant (rightmost) digit until the most significant digit (leftmost). We are going to involve the Queue data structure we learned in Chapter 3, Constructing Stacks and Queues since we will be putting the equal digit in the queue. This means we need ten queues to represent the digits from 0 to 9. Suppose we have an array with the following elements—{429, 3309, 65, 7439, 12, 9954, 30, 4567, 8, 882} as we can see in the following diagram:
Then, we populate each item based on the least significant digit (the last digit) and store them in their respective queue bucket. The diagram for this is as follows:
Since we put them in the queue, we can dequeue each bucket from 0 to 9. In the preceding diagram, we enqueue the bucket from the top so we dequeue it from the bottom. The diagram should be as follows...