Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 7 of 7

Thread: Radix Sort

  1. #1
    Junior Member
    Join Date
    Dec 2012
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Radix Sort

    Hello guys, I am implementing a Radix Sort using an array of queues.
    So far I have created the array and print it and is working fine.
    I have also extracted the LSD from each integer.
    No my target is to store the integers it the queues according to the LSD. (This would be the first pass).
    This is supposed to be processed in the for looped between line 29 and 35.
    -- problem is that when I deque the integers are being displayed in the same way as at the beginning!
    I know my problem is in my enqueue but I don't know how to do it.
    Here is the code:-
    import java.util.*;
     
    public class MainProgram
    {
     
        public static void main(String[] args)
        {
     
    	Scanner userinput = new Scanner(System.in);
    	System.out.print("Please enter the size of the array. ");
    	int count = userinput.nextInt(); //user enters the size of the array.
     
    	int[] numbers = new int[count];  //array containing hte integers.
    	int r=0;
     
       	QueueLinkedList[] queue = new QueueLinkedList[10]; //created an instance of the queue. 10 bins needed for the Radix Sort.
    	for(int i=0; i<queue.length; i++)
    		{
              	queue[i] = new QueueLinkedList();
            }
     
    	for(int index = 0; index < numbers.length; index++) //generating random integers.
    		{
    			numbers[index] = (int)(Math.random()*1001);
    			System.out.print(index+"    ");
    			System.out.println(numbers[index]);
    		}	
     
    		for(int i=0; i<numbers.length; i++) //identifying the LSD and store the integers in queues accoring to the LSD.
    		{									//the mistake is in this loop!				
    			numbers[r] = (numbers[i] % 10)/1;
    		//	System.out.println(numbers[r]);
    		    queue[r].enqueue(numbers[i]);
    		    //queue[r].dequeue();
     
    		}
    		for(int i=0;i<queue.length;i++){  //deque and printing the integers. Here the integers should be sorted by the LSD. 1st PASS.
    			queue[r].dequeue();				//however output is noot good!
    		}
        }    
    }
    Thanks in advance for your help.


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Radix Sort

    The posted code does not compile because of missing class.

    Also at http://forums.devshed.com/java-help-...ml#post2841315
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Dec 2012
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Radix Sort

    What class? If you are refering to the QueueLinkedList... I have a class for that which is working fine as a queue. Tks.

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Radix Sort

    There is no way to test the code since it does not compile.
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Dec 2012
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Radix Sort

    Ok so shall I post also the other class so it can be compiled?

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Radix Sort

    If you are looking for others to test your code they'll need all the class definitions.
    If you don't understand my answer, don't ignore it, ask a question.

  7. #7
    Junior Member
    Join Date
    Dec 2012
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Radix Sort

    Ok so here is my code.
    import java.util.*;
     
    public class MainProgram
    {
     
        public static void main(String[] args)
        {
     
    	Scanner userinput = new Scanner(System.in);
    	System.out.print("Please enter the size of the array. ");
    	int count = userinput.nextInt(); //user enters the size of the array.
     
    	int[] numbers = new int[count];  //array containing hte integers.
    	int r=0;
     
       	QueueLinkedList[] queue = new QueueLinkedList[10]; //created an instance of the queue. 10 bins needed for the Radix Sort.
    	for(int i=0; i<queue.length; i++)
    		{
              	queue[i] = new QueueLinkedList();
            }
     
    	for(int index = 0; index < numbers.length; index++) //generating random integers.
    		{
    			numbers[index] = (int)(Math.random()*1001);
    			System.out.print(index+"    ");
    			System.out.println(numbers[index]);
    		}	
     
    		for(int i=0; i<numbers.length; i++) //identifying the LSD and store the integers in queues accoring to the LSD.
    		{									//the mistake is in this loop! In the enqueue I believe.				
    			numbers[i] = (numbers[i] % 10)/1;
    		//	System.out.println(numbers[r]);
    		    queue[i].enqueue(numbers[i]);
    		    //queue[r].dequeue();
     
    		}
    		for(int i=0;i<queue.length;i++){  //deque and printing the integers. Here the integers should be sorted by the LSD. 1st PASS.
    			queue[i].dequeue();				//however output is noot good!
    		}
        }    
    }
    class QueueLinkedList {
        private Node head;
     
        //LinkedList constructor
        public QueueLinkedList()
        	{
    	    	head = null;
        	}
     
        //Inserts a new Link at the head of the list                
        public void enqueue(int d1)
        	{
    	    	Node node = new Node(d1);
    			Node temp = head;
     
    			if (head == null)
    				{
    					head = node;
    				}
    		  	else
    				{
    					while (temp.nextNode != null)
    		    		temp = temp.nextNode;
     
    	  	  			temp.nextNode = node;
      				}	   
        	}
     
             public Node dequeue() 
             	{  
             		Node temp = null;
              		if(head==null)  
                    	{  
                        	  System.out.println("Queue is empty!");
                    	}  
                	else  
                    	{  
                    		  temp = head;  
                       	 	  head = head.nextNode;  
                              temp.printList();    
                    	}  
                    return temp;
                }    
     
        //Prints list data
        public void printList()
        	{
    	    	Node temp = head;
    	    System.out.println("List: ");
    	    while(temp != null)
    	    	{
    		    	temp.printList();
    		    temp = temp.nextNode;
     
    	    }
    	    System.out.println("");
     
        }
        	 public void printLastItem()
    	 {
    	 	Node temp = head;
    	 	while(temp.nextNode !=null)
    	 		{
    	 			temp = temp.nextNode;
    	 		}
    	 		temp.printList();
     
    	 }
    	 	public void peek()
    	 	{
    	 		Node temp = head;
    	 		temp.printList();
    	 	}
     
     
    	 	public void isEmpty()
    	 	{
    	 		if(head == null)
    	 			{
    	 				System.out.println("Queue is empty!");
    	 			}
    	 		else
    	 			{
    	 				System.out.println("Queue is not empty!");
    	 			}
    	 	}
     
    	 	public void length()
    	 	{
    	 	Node temp = head;
    	    int count = 0;
    	    while(temp != null)
    	    	{
     
    		    temp = temp.nextNode;
    		    count = count + 1;
     
    	 	}
    	 	System.out.println(count);
    	 	}
     
     
    }
    class Node{
        public int data1;
        public Node nextNode;
     
        //Link constructor
        public Node(int d1)
        	{
    	    	data1 = d1;
       		}
     
        //Print Link data
        public void printList() {
    	    System.out.println(data1);
        }
    }
    Ok so here is my program. Im trying to implement a radix sort but Im stuck. Can anyone take a look at my code and tell my how to proceed please. Im having trouble enqueueing the integers according to their LSD.
    Thanks in advance for ypur help!

Similar Threads

  1. heap sort vs merge sort
    By IHeartProgramming in forum Algorithms & Recursion
    Replies: 1
    Last Post: December 3rd, 2012, 04:37 AM
  2. How to call a C sort function to sort a Java Array.
    By Dwere13 in forum Java Native Interface
    Replies: 22
    Last Post: July 12th, 2012, 04:44 PM
  3. How do I sort strings without using the sort method?
    By mjballa in forum What's Wrong With My Code?
    Replies: 2
    Last Post: December 4th, 2011, 03:27 PM
  4. Radix sort Issues??? Help
    By dadof3 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: May 13th, 2011, 01:08 PM
  5. bubble sort and selection sort on strings
    By Sir Saula in forum What's Wrong With My Code?
    Replies: 5
    Last Post: July 3rd, 2010, 09:44 AM