Stefan Evans wrote:My initial reactions:
A couple of your comments look like they have been copied/pasted, and don't apply where they are.
Specifically the second "put the number into the correct pocket" comment.
Yes, comments ARE important.
Rather than doing a peek to print out the number, then a dequeue, I would just do a dequeue, and then print out the result.
Your method of printing destroys the queue in the process. Not sure if you can do anything about that really, but a non-destructive print method would be useful for debugging :-)
As I think has been pointed out before, in one place you have used '10' rather than the NUMDIGITS constant. That might create a problem if you change the constant :-)
The algorithm itself looks like it should work. What are your results?
Junilu Lacar wrote:
Piet Souris wrote:
OP repeatedly stated he understood the radix algorithm, and he only needed assistance when it comes to the implementing part. Now, I wonder, what in this topic made you to spell out the algorithm again?
I'm afraid I may have crossed the line between being helpful and being overbearing. I apologize to David if he feels that way. It's just that I've been watching this thread and got a sense that David is in this way over his head. Since he said a lot of the code was already given and that he only had to complete some parts, my reckoning was that this would be a two- to three-hour exercise. Instead, it seems it dragged on significantly longer and he is obviously struggling with some of the programming language constructs, for example, using square brackets instead of parentheses with a method call. What's more, one of sections to be filled by him has the comment "make a recursive call to radix" -- that's like kicking the guy in the head when he's already got the wind knocked out of him.
As I said, from my vantage point, it seems like he was just poking around and trying one thing or another without a concrete plan of attack. I was simply trying to get him back on the right track. But again, my enthusiasm to help may have gotten the best of me, so please accept my apologies if that is the case here.
Junilu Lacar wrote:And why are you enqueue'ing the variable i? You should only enqueue the numbers you are sorting. You are not sorting the values that the variable i takes. You need to use i in a different way.
Junilu Lacar wrote:So, the section of code below is given and you can't change it?
Piet Souris wrote:Strange. The code in the 'radix' method has this piece:
So, pockets.get(i) should definitely work.
Can you show me the code you have for 'radix' so far?
Piet Souris wrote:Hmm... nice class, this QueueRefenrenceBased.
Wait, how would I move everything from the input Q to the new q (bucket) in the first place?
This is what you have in the 'radix' method:
We get an Integer from 'Q.dequeue()'. Problem is that we do not put this value
into a variable, so we cannot store it into one of the buckets. We also determine
the kth digit of this integer, but again, we do not store that value in a variable.
And all that is a pity, since we must store the integer into the bucket with index
this kth digit.
So, repair this situation: get this dequeue into a variable I, get this kth digit in a variable k,
and enque this I into Que[k]. You get this Que[k] by using pockets.get[k].
The code, therefore would be:
Implement this.
Then, enqueueing the original Que with the now filled buckets:
The routine that I gave in my previous post is still relevant. However,
this Que is not Iterable, so it seems. Therefore, we have little choice:
Piet Souris wrote:Right. How do you add something to a Queue?
First of all, I do not know this particuar 'QueueReferenceBased' class.
If you look at the description that goes with this class, you will no doubt
find methods to add and retrieve an Integer from this class.
Suppose that your Que is just a plain LinkedList, as we know it from Java.
Then to add an Integer I, you would simply say: Que.addLast(I).
And to retrieve and remove an integer, simply use Que.removeFirst.
I suggest you have a look at the LinkedList API in the Oracle documentation.
(Note: I use addLast and removeFirst, since it is a bit tricky to use
the standard get(i) and remove(i) in combination with LinkedList<Integer>).
So, I assume you can use the same commands for your Queue as well, but again,
look at you documentation.
Next: how do we get the 'buckets'? How about:
So, now we have filled our original Que again, so the question is: are
we finished sorting?
One way to find out would be to check that only one bucket was filled, while
all others are empty. Why is that? And how to check for this?
Can you think of another way to see if we're finished with the sorting?
Lastly: if we are not finished sorting, what then? How do we enter the next step?
Piet Souris wrote:With 'get the numbers' I mean: in the end, in what order are the numbers sorted?
The question about using the input Que when putting th buckets back, or creating
a new Que for this, is a detail in the implementation. To decide on this, you have
to look at how you call the radix method, I see this in your code:
Well, given this, it is necessary to use the input Que. Think about it. It is part
of the impementation.
Okay, so: how do you put those buckets back into the input Que? Do you know
how to add to this Que?
Finally: how do you know when you are finished with the sorting?
Greetz,
Piet
Piet Souris wrote:Okay.
After that, I would go through, from right to left, putting those items starting with kth number 9 back into the original queue.
Agreed. In what order will you get the numbers, according to this strategy?
Is it necessary to use the input Que for this? Or could you create a new one, and use that in the recursion?
Lastly: if you have put all the 'buckets' back into the input Que, what then? (be as detailed as you can!).
Well, I hope I'm not resembling your teacher in any way...
Greetz,
Piet
Piet Souris wrote:No, don't worry, I see what is happening in the code, and I will use that.
So, looking at the radix method, an ArrayList<Que> is created, with
initial room for NUMBASE Que's (I abbreviate the QueueReferenceBased<Integer>
to Que, for shortness' sake). NUMBASE is 10, currently.
For each Integer I in the inputQue, the kth digit is determined. What should be done now,
is to place that Integer I into one of the Que's of your ArrayList. So, in effect,
these Que's of the ArrayList are the buckets.
Which Que to put this Integer in? The array has 10 Que's.
So, suppose the kth digit = 7. In what Que would you place that number?
You can take k = 1 to start with, if you think it gets complicated.
Now, suppose you have put all the Integers of the inputQue into
the Que's of the ArrayList. Now what? Can you describe what to do next?
Greetings,
Piet
Piet Souris wrote:hi David,
I hadn't understood that part, I'm sorry.
From what I remember of your code, and what Junilu already remarked,
is that you do nothing with the k th digit. What I meant was to store
that number in the hashmap, with key being this k th digit.
Of course I want to help, but I need to give your code another, more thorough
read. Meanwhile, If anyone around already knows how to help, please step in!
Greetz,
Piet
PS: and I'm doubting about a hashmap or a treemap... well, I'll be in touch.
Piet Souris wrote:
Piet Souris wrote:(...)
The first Integer being the radix.
I meant to say: the first integer being the k-th digit of each number, k being the second
parameter of your radix function.
Sigh... harder to describe than to implement, I'm afraid...
People of name and fame, on this very site, often write that one has to describe
a problem in such small steps, that one can explain it to a 10 year old kid.
Now, either they are implying that a 10 year old kid can do their job,
or if not, then why bother...![]()
![]()
![]()
Junilu Lacar wrote:Well, if you were to use pockets, what would that look like?
And the getKthNumber() method returns an int, but when you call it, you don't assign the result of the call to anything. In essence, you're ignoring what that method is giving back and it just disappears into the ether. What is the Kth number supposed to represent anyway? Is that a pocket number? If it is, then you need to keep it around long enough to use it.
Junilu Lacar wrote:You probably should take a cue from some other code in that class. A few lines below, I see:
What do you think is happening on line 21 there?