• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Radix Sort

 
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Bartender
Posts: 3323
86
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 26
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 3323
86
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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:
 
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Ronald Spina
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 3323
86
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You’re on a roll, TD! even RS has difficulty getting there 10 seconds earlier
 
Tony Docherty
Bartender
Posts: 3323
86
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 26
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 26
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 3323
86
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 26
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 26
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sorry 10 bucket (from 0 to 9) i mean.
 
Tony Docherty
Bartender
Posts: 3323
86
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 26
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
reply
    Bookmark Topic Watch Topic
  • New Topic