Add to Favorites    Make Home Page 2484 Online
 Language Categories
 Source Codes Home Project Ideas New! Interview Questions FAQs Home ASP Home ASP Source Codes ASP Script Directory New! ASP .Net Script Directory New! ASP Interview Questions ASP FAQs ASP How Tos C Home C Source Codes C Script Directory New! C Interview Questions C FAQs C How Tos C++ Home C++ Source Codes C++ Script Directory New! C++ Interview Questions C++ FAQs C++ How Tos Java Home Java Source Codes Java Directory New! Java Interview Questions Java FAQs Java How Tos JavaScript Home JavaScript Directory New! JavaScript Source Codes JavaScript FAQs JavaScript How Tos COBOL Home COBOL Source Codes COBOL FAQs COBOL How Tos Pascal Home Pascal Source Codes Pascal FAQs Pascal How Tos PHP Script Directory New! Python Script Directory New! Perl & CGI Script Directory New! Flash Script Directory New! CFML Script Directory New! Remotely Hosted Scripts New! Tools & Utilities Directory New! XML Script Directory New! Best Programmers Amit Mathur Vishal Bhardwaj Deepesh Jain Vyom NetWork
 Our Services

Java Data Structures - Contents

A D V E R T I S E M E N T

Search Projects & Source Codes:

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.*;

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] + " ");
}
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.

A D V E R T I S E M E N T

Subscribe to SourceCodesWorld - Techies Talk
Email:

 Free eBook - Interview Questions: Get over 1,000 Interview Questions in an eBook for free when you join JobsAssist. Just click on the button below to join JobsAssist and you will immediately receive the Free eBook with thousands of Interview Questions in an ebook when you join.