Radix Sort - I
How it Works
Radix sort is one of the various sorting algorithms which is prevalently used to sort data.The algorithm is fairly simple and can be implemented on any language quite easily.In this post we will look at how to sort a set of numerical data and the program to achieve that would be in C#.
Lets say you want to sort the following numbers in sequential order using Radix
23 12 45 67 34
Radix sort employs a very simple way of looking at the unit of every element and then subsequently placing the element in a bucket that corresponds to the unit.What i mean is
for a given number 43 i am suggesting here 4 and 3 are the 2 units that make up the whole number.so when you are looking at unit 4 the number 43 would belong to bucket 4 and for 3 it would be bucket 3.All this would be clear with a following example.
we will always start with the least significant digit(of every numeric element in this case) and gradually move towards left on every iteration.The numbers marked below are the least significant digits.we also maintain a bucket for every digit 0 - 9.
23 12 45 13 67 34
After pass one our buckets and its containing elements will look like below.
if we read out elements in the buckets 0 -9 we get the new sequence(may or may not be sorted).
12 23 13 34 45 67
Now we need to sort this list again based on the next unit (move towards left).
12 23 13 34 45 67
After this second pass our Buckets will look like below.
Now if we read out the elements we can see the elements are sorted
12 13 23 34 45 67
so to sort this list we needed two pass.But this may not be the case when you have mix of elements whose number of digits are different.we will see how we are handling this in second part where i also show the program written in C#.
More details on this algorithm can be found on this page
No comments:
Post a Comment