Radix Sort

[Ronald Spina]

Hi guys,

I have just finished implementing my radix sort. Seems to be working fine within the first and second pass, but not in the third and fourth pass. Anyone could please find what i am doing wrong!
Please help me cause i really want to make this Radix Sort work!! I think I have some bugs in my program but I cant find where!!

import java.util.Scanner;
public class RadixSort 
{

	    public static void main(String[] args)
		{
			Scanner userinput = new Scanner(System.in);
			System.out.print("Please enter the size of the array. ");
			//User is prompted to enter the size of the array.
			int count = userinput.nextInt();

			int[] numbers = new int[count];
			QueueLinkedList[] queue = new QueueLinkedList[10];
	
			for(int i=0; i<queue.length; i++)
			{
          		queue[i] = new QueueLinkedList();
        	}
			
			//Generates random integers.
			for(int i=0; i<numbers.length; i++)
			{
				numbers[i] = (int)(Math.random()*1001);
				System.out.print(numbers[i]+", ");
			}
  			System.out.println();
  			     	
			for(int j=1; j<=4; j++)
			{
				for(int i=0; i<numbers.length; i++)
				{
					int  temp = 0;
					queue[getRadix(numbers[i],j)].enqueue(numbers[i]);
				}

				for(int i=0; i<queue.length; i++)
				{
					int index=0;
					while(!queue[i].isEmpty())
						{					
							numbers[index] = queue[i].dequeueInt();
							System.out.print(numbers[index]+", ");
							index++;
						}
				}System.out.println();
			}
					
		}
    	public static int getRadix(int number, int radix)
    	{
			int result = (int)(number / Math.pow(10,radix-1)) % 10;
			return result;
		}

	
}

[Ronald Spina]

Here is the output of the program.
Please enter the size of the array. 5
306, 392, 374, 493, 31,
31, 392, 493, 374, 306,
306, 31, 374, 392, 493,
31, 392, 374, 493, 493,
493, 493, 374, 493, 31,

Process completed.

I notice that numbers are also being duplicated in very pass!

[Paul Clapham]

I'd suggest that at line 42 you also output the value of index for debugging purposes.

[Ronald Spina]

I did and hmm there is something strange in the output!

145, 960, 490, 681, 257, 862, 377, 386, 943, 517,
0 960, 1 490, 0 681, 0 862, 0 943, 0 145, 0 386, 0 257, 1 377, 2 517,
0 517, 1 517, 0 943, 0 257, 1 257, 0 862, 0 377, 1 377, 0 681, 1 386,
0 257, 0 386, 1 377, 2 386, 0 517, 1 517, 0 681, 1 681, 0 862, 0 943,
0 943, 1 681, 2 386, 3 681, 4 257, 5 862, 6 377, 7 386, 8 943, 9 517,

Any suggestions of what happeing!

[Darryl Burke]

Ronald, please BeForthrightWhenCrossPostingToOtherSites
http://www.java-forums.org/new-java/66538-radix-sort.html

edit: http://www.javaprogrammingforums.com/whats-wrong-my-code/20587-radix-sort.html

[Paul Clapham]

Ronald Spina wrote:Any suggestions of what happeing!

Let's ask that differently: Why does index keep getting set back to zero?

[Steve Fahlbusch]

and as an extension of what Paul suggested.

you may want to add a print at say line 51 (print out the number, radix and result) just to verify everything is working as you expect.

[Ronald Spina]

Ok sorry for posting the same treath to other forums.
I have added some print statements and added some comments.

import java.util.Scanner;
public class RadixSort 
{

	    public static void main(String[] args)
		{
			Scanner userinput = new Scanner(System.in);
			System.out.print("Please enter the size of the array. ");
			//User is prompted to enter the size of the array.
			int count = userinput.nextInt();
			//Created and array named numbers which is going to hold the integers.
			int[] numbers = new int[count];
			/*Instanciated an array filled with 10 queue (buckets) which  will hold
			the temporarily sorted integeres after each pass. Then I will put back the 
			integers in the array(numbers).*/
			QueueLinkedList[] queue = new QueueLinkedList[10];
			//Initializing the queues.
			for(int i=0; i<queue.length; i++)
			{
          		queue[i] = new QueueLinkedList();
        	}
			
			//Generates random integers.
			for(int i=0; i<numbers.length; i++)
			{
				numbers[i] = (int)(Math.random()*1001);
				System.out.print(numbers[i]+", ");
			}
  			System.out.println();
  			/*I will loop for 4 times because the maximum number will always 
  			have 4 digits.*/
			for(int j=1; j<=1; j++)
			{
				/*Loop through the array and finding the LSD (first pass). The LCD will be j and is the index in 
				 *the queue. Enqueuing the integers into buckets 0-9 according to the radix.*/
				for(int i=0; i<numbers.length; i++)
				{
					queue[getRadix(numbers[i],j)].enqueue(numbers[i]);
					System.out.print(numbers[i]+" "+getRadix(numbers[i],j)+", ");
				}
				System.out.println();
				
				/*Here I am deuqueueing the queues from 0 - 9 and put back the integers in the array(numbers).*/
				for(int i=0; i<queue.length; i++)
				{
					int index=0;
					while(!queue[i].isEmpty())
						{					
							numbers[index] = queue[i].dequeueInt();
							System.out.print(index +" "+numbers[index]+", ");
							index++;
							/*I HAVE NOTICED THAT HERE THE INDEX IS RESETTING TO 0 WHEN GOING TO THE NEXT QUEUE!!!*/
						}
				}System.out.println();
			}
					
		}
    	public static int getRadix(int number, int radix)
    	{
			int result = (int)(number / Math.pow(10,radix-1)) % 10;
			return result;
		}

	
}

I have noticed that the index in while loop (47-52) is resetting when passing from a queue to another.
This is the result of my program.
Bdw I made the outer loop to loop I time so I can tackle problem at a time.

Please enter the size of the array. 9
807, 463, 609, 979, 88, 684, 905, 475, 667, 9 ramdom integers stored in numbers. Fine!
807 7, 463 3, 609 9, 979 9, 88 8, 684 4, 905 5, 475 5, 667 7, Finding the LSD and storing them in the queues. Fine!
0 463, 0 684, 0 905, 1 475, 0 807, 1 667, 0 88, 0 609, 1 979, Dequeue the queues on after each other and store int back to numbers. Here is the problem.

Process completed.

[Ronald Spina]

Of course! int index=0; has to be outside the for loop!