Radix Sort -Part II

In our previous post we looked at the fundamentals of Radix sorting .
we also ran few examples to see the algorithm at work.On today's post we will be looking at the low level implementation of this sorting mechanism.

Click here for PART -I  Fundamentals

What we need to do is to single out a digit from every number (could be a single digit) and then decide which bucket it belongs. The Algorithm makes an assumption that the bucket number cannot exceed number 9 (0<= buketNumber < 10). The most important player in the scheme of things is the modulo operator (%).

Before we dig in we need to look at what lsd's and msd's are.Could be trivial for most but is crucial.

What is an LSD and MSD?

They are least significant digit and most significant digit. In our example

LSD OF 435 is 5

MSD OF 435 is 4.

My algorithm starts from LSD although you can start from MSD and move towards right.

For a number 435 how do we move from left to right?

We do 435 % 10 = 5 so we place the number in bucket 5.

Now to move left on the next iteration you multiply the divider by 10.

435 %( 10* 10) = 435%100= 35

What we have got here is a 2 digit number (35) with one digit (5) already processed so we need to get rid 5 from it. To get rid you do below.

(35 – (35 %10))/10

35 -5 /10

30/10

3 (so you know you need to place the number in bucket 3)

Now in the next iteration,the divider is again multiplied with 10 to get below

435 % (10*10*10) =435%1000=435.

What we need is the leftmost digit 4 from 435.so we keep repeating the steps that we did earlier 

(435 – (435%10))/10 = 430/10= 43

(43-(43%10))/10=40/10 = 4

Finally we know we need to place the number in Bucket 4.

C# Implementation

       

       The sort method does all the hard work.

       Output

     Here is the complete working code :)

Cheers

POLYBIUS

Click here for other Topics