aspose file tools*
The moose likes Beginning Java and the fly likes Radix Sort Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Radix Sort" Watch "Radix Sort" New topic
Author

Radix Sort

Ronald Spina
Greenhorn

Joined: Jan 23, 2012
Posts: 26
Hi, currently I am trying to implement a Radix Sort. I will be using an array with linked lists. I have already implemented the linked list however I am having trouble in creating the array with the linked lists. If I have used the linked list of the java API I would have to do something like the below:-


In my Radix Sort class I have created an instance of the linked list(which is actually a queue based on a linked list) as "queue". Any one can help me out please.

Thanks in advance.
Tony Docherty
Bartender

Joined: Aug 07, 2007
Posts: 2317
    
  49
Sorry but I'm struggling to understand your problem, can you explain in more detail what you are trying to achieve and how it differs from the code you have shown.

BTW As an aside when looping over an array rather than hard coding the end value it's better to use the length field of the array ie
Ronald Spina
Greenhorn

Joined: Jan 23, 2012
Posts: 26
Actually i want to create and array with linked lists and i've done the below.

QueueLinkedList queue = new QueueLinkedList(); //created an instance of my linked list.

queue[ ] bucket = new bucket[10]; //created an array of queues.
for (int i = 0; i < bucket.length; i++) //looped through the array and inserted the list into each index of the array.
{
bucket[i] = new QueueLinkedList()
}

Problem is that compiler is giving that it cannot find queue[]. I know I am messing out with this but hope you understand what I need to do.
Thanks
Tony Docherty
Bartender

Joined: Aug 07, 2007
Posts: 2317
    
  49
Please remember to UseCodeTags when posting code.

Are you sure you have the right letter case, Java is case sensitive and by convention Java classes start with an upper case letter so I would expect your code to be:

And are you sure you want to create an array of Buckets and assign it to a variable of type array of Queue ie should the first line be:
Joanne Neal
Rancher

Joined: Aug 05, 2005
Posts: 3682
    
  16
Ronald Spina wrote:

Problem is that compiler is giving that it cannot find queue[]. I know I am messing out with this but hope you understand what I need to do.
Thanks

queue and bucket are the names of variables. You have to use the type when declaring arrays. i.e.


Joanne
Ronald Spina
Greenhorn

Joined: Jan 23, 2012
Posts: 26
Ok now I iunderstood it.. and it is compiling. However when running the program I am getting a Null Pointer Exception error. Please see exact error message below.
Please enter the size of the array. 3
Exception in thread "main" java.lang.NullPointerException
at MainProgram.main(MainProgram.java:15)



Any one can help please...
Tony Docherty
Bartender

Joined: Aug 07, 2007
Posts: 2317
    
  49
When posting code please make sure it is the code you are running - this code won't compile.
Sorry ignore this my browser doesn't show the underscores.

The problem is because you have created the array but haven't filled it with any QueueLinkedList objects yet and so the array element at index 2 is null.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39436
    
  28
Very common error. What has happened is that you created an array, but an array is filled with nulls at first. You need to go through it with queue[i] = new Queue_Linked_List();

By the way: it is considered poor style to use the underscore in identifiers or class names like that.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39436
    
  28
You’re on a roll, TD! even RS has difficulty getting there 10 seconds earlier
Tony Docherty
Bartender

Joined: Aug 07, 2007
Posts: 2317
    
  49
I may have got there sooner than you but your answer was more accurate - I got caught by the missing underscores problem again
Ronald Spina
Greenhorn

Joined: Jan 23, 2012
Posts: 26
I have removed the underscore for more stylish code and for all of you to get less confused!
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 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!
Here is the code:-


Anyone can explain what is that's not going fine! Thank You
Ronald Spina
Greenhorn

Joined: Jan 23, 2012
Posts: 26
This is the output of the above code:

Please enter the size of the array. 7
0 766
1 137
2 263
3 212
4 550
5 263
6 983
6
7
3
2
0
3
3
6
137
263
212
550
263
983
Queue is empty!
Queue is empty!
Queue is empty!
Tony Docherty
Bartender

Joined: Aug 07, 2007
Posts: 2317
    
  49
Why are you using "r" as the index into the arrays when "r" is always 0?
And can you explain why you have an array of 10 QueueLinkedLists?

You are right about your sorting routine not working. I suggest you write out in your native language how you would sort the numbers into order and then turn your words into code. Alternatively you could always use the Arrays.sort() method passing in a Comparator to handle the ordering you require.
Ronald Spina
Greenhorn

Joined: Jan 23, 2012
Posts: 26
Hi, I made 10 queue (which represent 10 buckets from 0 to 1). Then I want to pass through the first array of integers which I created in the beginning. The pass will put the integers in the buckets according to their LSD. Example the integer 4567 will be placed into the queue with index 7.. an so on. Then I need to dequeue all the integers beginning fro queue 0 to queue 9 into one array. Like this the first array of integers will be sorted according to the LSD.
Ronald Spina
Greenhorn

Joined: Jan 23, 2012
Posts: 26
Sorry 10 bucket (from 0 to 9) i mean.
Tony Docherty
Bartender

Joined: Aug 07, 2007
Posts: 2317
    
  49
ok so the LSD value is the 0-9 index into the appropriate bucket. So you need to get the LSD and use that value as the index into your queue array and then add the integer value to the list at that index.
Ronald Spina
Greenhorn

Joined: Jan 23, 2012
Posts: 26
Yes I agree. And then if I enqueue all the queuues from 0 to 9 that will be sorted by the LSD. E.g. 123,544,678,12,431. Will become 431,12,123,544,678.
So please do you have any idea of what I am doing wrong in my code? Obviously the mistake is in that for loop I menioned erlier and precislely in the enquee. (line 29-35)
Thanks in advance for your help!
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8012
    
  22

Ronald Spina wrote:Yes I agree. And then if I enqueue all the queuues from 0 to 9 that will be sorted by the LSD. E.g. 123,544,678,12,431. Will become 431,12,123,544,678.
So please do you have any idea of what I am doing wrong in my code? Obviously the mistake is in that for loop I menioned erlier and precislely in the enquee. (line 29-35)
Thanks in advance for your help!

I hate to say, but the best advice I can give you is StopCoding (←click). You seem to be bogged down in procedure at the moment, when what you need to be concentrating on WhatNotHow.

For example, I'm pretty sure that if I was writing this, one of my first methods would be a
public int[] digits(int value) {...
method that splits my value into its component digits, but you still seem to be stuck in "I do this...then I do this..." mode.

Winston


Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
 
Don't get me started about those stupid light bulbs.
 
subject: Radix Sort