Java Data Structures - Contents
A D V E R T I S E M E N T
Radix sort is one of the nastiest sorts that I know.
This sort can be quite fast when used in appropriate context, however, to me, it seems
that the context is never appropriate for radix sort.
The idea behind the sort is that we sort numbers
according to their base (sort of). For example, lets say we had a number 1024, and we
break it down into it's basic components. The 1 is in the thousands, the 0 is in the
hundreds, the 2 is in the tens, and 4 is in some units. Anyway, given two numbers, we can
sort them according to these bases (i.e.: 100 is greater than 10 because first one has
more 'hundreds').
In our example, we will start by sorting numbers
according to their least significant bits, and then move onto more significant ones, until
we reach the end (at which point, the array will be sorted). This can work the other way
as well, and in some cases, it's even more preferable to do it 'backwards'.
Sort consists of several passes though the data,
with each pass, making it more and more sorted. In our example, we won't be overly
concerned with the actual decimal digits; we will be using base 256! The workings of the
sort are shown below:
Numbers to sort: 23 45 21 56 94 75 52
we create ten queues (one queue for each digit): queue[0 .. 9]
We start going thought the passes of sorting it,
starting with least significant digits.
queue[0] = { }
queue[1] = {21}
queue[2] = {52}
queue[3] = {23}
queue[4] = {94}
queue[5] = {45,75}
queue[6] = {56}
queue[7] = { }
queue[8] = { }
queue[9] = { }
Notice that the queue number corresponds to the
least significant digit (i.e.: queue 1 holding 21, and queue 6
holding 56). We copy this queue into our array (top to bottom, left to
right) Now, numbers to be sorted: 21 52 23 94 45 75 56 We now continue
with another pass:
queue[0] = { }
queue[1] = { }
queue[2] = {21,23}
queue[3] = { }
queue[4] = {45}
queue[5] = {52,56}
queue[6] = { }
queue[7] = {75}
queue[8] = { }
queue[9] = {94}
Notice that the queue number corresponds to the most
significant digit (i.e.: queue 4 holding 45, and queue 7
holding 75). We copy this queue into our array (top to bottom, left to
right) and the numbers are sorted: 21 23 45 52 56 75 94
Hmm... Isn't that interesting? Anyway, you're
probably wondering how it will all work within a program (or more precisely, how much book
keeping we will have to do to make it work). Well, we won't be working with 10
queues in our little program, we'll be working with 256 queues! We won't just
have least significant and most significant bits, we'll have a whole range (from 0xFF
to 0xFF000000).
Now, using arrays to represent Queues is definitely
out of the question (most of the times) since that would be wasting tons of space (think
about it if it's not obvious). Using dynamic allocation is also out of the question, since
that would be extremely slow (since we will be releasing and allocating nodes throughout
the entire sort). This leaves us with little choice but to use node pools. The node pools
we will be working with will be really slim, without much code to them. All we need are
nodes with two integers (one for the data, the other for the link to next node). We will
represent the entire node pool as a two dimensional array, where the height of the array
is the number of elements to sort, and the width is two.
Anyway, enough talk, here's the program:
import java.lang.*;
import java.io.*;
public class RadixSort{
public static void radixSort(int[] arr){
if(arr.length == 0)
return;
int[][] np = new int[arr.length][2];
int[] q = new int[0x100];
int i,j,k,l,f = 0;
for(k=0;k<4;k++){
for(i=0;i<(np.length-1);i++)
np[i][1] = i+1;
np[i][1] = -1;
for(i=0;i<q.length;i++)
q[i] = -1;
for(f=i=0;i<arr.length;i++){
j = ((0xFF<<(k<<3))&arr[i])>>(k<<3);
if(q[j] == -1)
l = q[j] = f;
else{
l = q[j];
while(np[l][1] != -1)
l = np[l][1];
np[l][1] = f;
l = np[l][1];
}
f = np[f][1];
np[l][0] = arr[i];
np[l][1] = -1;
}
for(l=q[i=j=0];i<0x100;i++)
for(l=q[i];l!=-1;l=np[l][1])
arr[j++] = np[l][0];
}
}
public static void main(String[] args){
int i;
int[] arr = new int[15];
System.out.print("original: ");
for(i=0;i<arr.length;i++){
arr[i] = (int)(Math.random() * 1024);
System.out.print(arr[i] + " ");
}
radixSort(arr);
System.out.print("\nsorted: ");
for(i=0;i<arr.length;i++)
System.out.print(arr[i] + " ");
System.out.println("\nDone ;-)");
}
}
Yeah, not exactly the most friendliest code I've
written. A few things to mention about the code. One: it's NOT fast (far from it!). Two:
It only works with positive integers. Sample output:
original: 1023 1007 583 154 518 671 83 98 213 564 572 989 241 150 64
sorted: 64 83 98 150 154 213 241 518 564 572 583 671 989 1007 1023
Done ;-)
I don't like this sort much, so, I won't talk much
about it. However, a few words before we go on. This sort can be rather efficient in
conjunction with other sorts. For example, you can use this sort to pre-sort the most
significant bits, and then use insertion sort for the rest. Another very crucial thing to
do to speed it up is to make the node pool and queues statically allocated (don't allocate
them every time you call the function). And if you're sorting small numbers (i.e.: 1-256),
you can make it 4 times as fast by simply removing the outer loop.
This sort is not very expandable. You'd have
problems making it work with anything other than numbers. Even adding negative number
support isn't very straight forward. Anyway, I'm going to go and think up more reasons not
to use this sort... and use something like quick-sort instead.
Back to Table of Contents
A D V E R T I S E M E N T
|
Subscribe to SourceCodesWorld - Techies Talk |
| 
Add to Favorites
Make Home Page
