Having Trouble implementing this Radix Sort

[David Bilger]

I understand radix sort, but I am having trouble turning it into code. I need help in the radix method, specifically, how to dequeue for the first time and sort by the first digit. The rest should make sense.
Here is the code
Thank you

[Junilu Lacar]

Hi David,

That's quite a bit of code to go through there. It will help if you narrow it down to fewer lines of code to look at. Where do you think the problem is, what do you think that code is doing, and what exactly does it look like it's doing that it shouldn't? A bug in a program is really a "failure to communicate" properly. You think you're telling the computer to do something but the instructions you gave are interpreted different by the computer, which is happy to go ahead with its own interpretation of the instructions you wrote. The way to fix the bug is to figure out where that disconnect is.

[Junilu Lacar]

And Welcome to the Ranch!

[David Bilger]

Junilu Lacar wrote:Hi David,

That's quite a bit of code to go through there. It will help if you narrow it down to fewer lines of code to look at. Where do you think the problem is, what do you think that code is doing, and what exactly does it look like it's doing that it shouldn't? A bug in a program is really a "failure to communicate" properly. You think you're telling the computer to do something but the instructions you gave are interpreted different by the computer, which is happy to go ahead with its own interpretation of the instructions you wrote. The way to fix the bug is to figure out where that disconnect is.

Ok I narrowed it down to this method:

public static void radix(QueueReferenceBased<Integer> Q, int k){
	System.out.println("~~  sorting column "+k +" ~~");
	final int NUMDIGITS = 5; // maximum number of digits in data
	final int NUMBASE = 10; // decimal numbers, base 10
	// creation of the array
	ArrayList <QueueReferenceBased<Integer>> pockets = 
	    new ArrayList <QueueReferenceBased<Integer>>(NUMBASE);
	//instantiation of the array
	for (int i=0; i<NUMBASE; i++)
	    pockets.add(i,new QueueReferenceBased><Integer>());
	//enqueue the appropriate pockets
	
	/* TO COMPLETE */
	// dequeue the pockets in the appropriate order
	// and print the elements right-aligned

	ArrayList <QueueReferenceBased<Integer>> bucket = 
		    new ArrayList <QueueReferenceBased<Integer>>(NUMBASE);
	
	for (int i = 0; i < NUMBASE; i++)
	{
		
	}
	
		
	
	
	
	/* TO COMPLETE */
        // Make recursive call if necessary
	
	/* TO COMPLETE */
    } // end RadSort

The parts I commented are what I know am supposed to do, but I am having problems converting that to code. The empty for loop I made is just a guess of where I should start. I was given one other method to use to assist this one. I am pretty confused.

/** find the kth digit of a number num writen in base numbase
     * @param num is the number considered
     * @param k is the position of the digit we want to know (from the right)
     * @param numbase is the base used to write <code>num</code> (ex base 10).
     */
    public static int getKthNumber(Integer num, int k, int numbase){
	return (num/(int)Math.pow(numbase,k-1))%numbase;
    } 

[Junilu Lacar]

Break it down into smaller problems. Also, try to describe how you would do this manually, like say with pencil and paper. If you can break it down to simple step-by-step instructions for yourself to follow, writing it down as a computer program is usually a more or less direct translation.

How do you dequeue objects from a QueueReferenceBased?

What do you do with each object as you dequeue it?

How do you print something?

[David Bilger]

Junilu Lacar wrote:Break it down into smaller problems. Also, try to describe how you would do this manually, like say with pencil and paper. If you can break it down to simple step-by-step instructions for yourself to follow, writing it down as a computer program is usually a more or less direct translation.

How do you dequeue objects from a QueueReferenceBased?

What do you do with each object as you dequeue it?

How do you print something?

Question 1 I am really struggling with coding how to dequeue the objects. I know I have to copy it to the bucket. This is the part I need with help the most!

2. I would send it to the getKthNumber method along with k that was passed and NUMBASE.

3. Use a for loop to print out each item in the bucket.

[Junilu Lacar]

You probably should take a cue from some other code in that class. A few lines below, I see:
while (!Q.isEmpty()) { System.out.print(Q.peek()); getKthNumber(Q.dequeue(), k, 10); }
What do you think is happening on line 21 there?

[David Bilger]

Junilu Lacar wrote:You probably should take a cue from some other code in that class. A few lines below, I see:
while (!Q.isEmpty()) { System.out.print(Q.peek()); getKthNumber(Q.dequeue(), k, 10); }
What do you think is happening on line 21 there?

I ended up getting rid of that code because I didn't think it worked since it didn't use pockets. Can it be fixed to work?

[Junilu Lacar]

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.

[David Bilger]

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.

This is what I have been working on:

	ArrayList <QueueReferenceBased<Integer>> bucket = 
		    new ArrayList <QueueReferenceBased<Integer>>(NUMBASE);
	
	for (int i = 0; i < NUMBASE; i++)
	{
		Integer tmp = Q.dequeue();
		
		
		 
		
		if()
	}

in the empty space I want to be able to compare tmp to other values after using getKthNumber, but I do not know how to iterate through and compare.

[Junilu Lacar]

Like I said before, David, programming is really about figuring out what you want to say to the computer. When you figure that out and can lay the steps out in a logical manner such that you can give those manual instructions to your grandmother and even she will be able to do it, then you can start figuring out the "how" part, which is telling the computer using the Java language how to carry out your wishes.

In short, go back to the drawing board and lay out the procedure as if YOU or some other person is going to do it manually. If you can't do that, then it's going to be a hit or miss proposition to do it in the Java Language with the computer as your minion.

[Piet Souris]

There are some really instructive video's at youtube, demonstrating the
algorithm. Have a look, I bet you'll find the implementation much less
difficult.

Greetz,
Piet

[Piet Souris]

On second thoughts... you may have already looked at these video's.

The biggest problem as I see it, is getting the numbers into these buckets.
You define an int[10] for these, but the problem is that in one bucket
more than one number may go. So, you would need to have a structure
like YourQue[] buckets = new YourQue[10]. Problem with that is that it is
based on a base of 10. Making it general, YourQue[n], with n a parameter,
is impossible, unfortunately.
(one of the consequences of the way generics are implemented in Java).

My suggestion would be to use a HashMap<Integer, List<Integer>>, in your radix
method, or instead of a List<Integer>, you could of course use your own Que.
The first Integer being the radix.

Think about how you could transform this HashMap back into a Que again,
at the end of the method, and before going into recursion, and what the stopping condition
should be.

Well, I hope my advice wil make it easier to make the description that Junilu
suggested.

Greetz,
Piet

[Piet Souris]

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...

[David Bilger]

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...

Except for the parts marked TO COMPLETE, the code was given to me, so I cannot use the way you described. I have to work within the tools given. My problem is that I am struggling to code for the snippet that I mentioned earlier. Can you help me with that?

Thanks

[Piet Souris]

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.

[David Bilger]

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.

I am a beginner still and do not know what a hashmap or treemap is, so I don't think I should use those to complete it.

[Piet Souris]

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

[Junilu Lacar]

David Bilger wrote:I am a beginner still

All the more reason to be really clear on exactly what it is you want to do before you jump into the nitty gritty details of how you think you can do it. Did you give it a try, writing the procedure out as plain English, step-by-step instructions that any non-computer literate person can do? That's probably the best way you can get some clarity on how to proceed.

[David Bilger]

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

I would put it in the Que for 7. Since there are 10 spots, 0-9.
After that, I would go through, from right to left, putting those items starting with kth number 9 back into the original queue.

[Piet Souris]

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

[David Bilger]

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

What do you mean by 'get' the numbers? It is not necessary to use the input Que, but why not? After putting all of the buckets back into the input que, you advance to the next kth digit and repeat the same process, sorting by the next kth digit using the two queues.
Like I have previously mentioned, I have a decent grasp on radix sort conceptually, but I am lost on how to code for it.
Also, thank you so much for helping me! I really appreciate it.

[Piet Souris]

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:

public static void radixSort(QueueReferenceBased<Integer> Q){
	radix(Q, 1);

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

[David Bilger]

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:

public static void radixSort(QueueReferenceBased<Integer> Q){
	radix(Q, 1);

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

In the end of the first pass, the numbers are sorted based on the first digit. Each number that has the same first digit goes into the same bucket.

I do not know how to add them back to the input Que, nor do I know how to pull the numbers out and sort them in the first place.
I am finished with the sorting when a pass does not need to switch any numbers around anymore.

[Piet Souris]

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:

for (int i = NUMBASE - 1; i <= 0; i--) {
      Que q = pockets.get(i);
     for (Integer int : q) {
          // add int to the original Que
     }
}

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?

[Junilu Lacar]

Piet Souris wrote:
First of all, I do not know this particuar 'QueueReferenceBased' class.

Most likely, it's one of the things that turns up when you Google for QueueReferenceBased

[David Bilger]

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:

for (int i = NUMBASE - 1; i <= 0; i--) {
      Que q = pockets.get(i);
     for (Integer int : q) {
          // add int to the original Que
     }
}

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?

QueueReferencedBased allows me to use isEmpty, dequeueAll, enqueue, dequeue, and peek.

Wait, how would I move everything from the input Q to the new q (bucket) in the first place?
When I try to get the buckets, I get and error in the advanced for loop that q can only iterate over an array or an instance of java.lang.iterable.

We are not finished sorting, we have not even begun to. We must use the getKthNumber method at this point correct?

[Piet Souris]

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:

while (!Q.isEmpty())
		{
			System.out.print(Q.peek());
			getKthNumber(Q.dequeue(), k, 10);
		}

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:

pocket.get[k].enqueue(I);

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:

for (int i = NUMBASE -1; i >= 0; i--) {
    Que q = pockets.get(i);
    while(!q.isEmpty()) {
        originalQue.enqueue(q.dequeue());
    }
}

[David Bilger]

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:

while (!Q.isEmpty())
		{
			System.out.print(Q.peek());
			getKthNumber(Q.dequeue(), k, 10);
		}

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:

pocket.get[k].enqueue(I);

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:

for (int i = NUMBASE -1; i >= 0; i--) {
    Que q = pockets.get(i);
    while(!q.isEmpty()) {
        originalQue.enqueue(q.dequeue());
    }
}

When coding the for loop

for (int i =NUMBASE - 1; i <= 0; i--)
	{		
		pockets.get[k].enqueue(i);
        }

"get" cannot be resolved or is not a field.

[Piet Souris]

Strange. The code in the 'radix' method has this piece:

ArrayList <QueueReferenceBased<Integer>> pockets = 
	    new ArrayList <QueueReferenceBased<Integer>>(NUMBASE);
	//instantiation of the array
	for (int i=0; i<NUMBASE; i++)
	    pockets.add(i,new QueueReferenceBased<Integer>());

So, pockets.get(i) should definitely work.

Can you show me the code you have for 'radix' so far?

[Junilu Lacar]

I see you fighting with the code. I doubt you're ever going to consider any other base besides base 10, right? If you are, then why have this line:

final int NUMBASE = 10; // decimal numbers, base 10

Assuming I'm right, then you'll only ever need that many "pockets". So a fixed number of elements can be more easily represented with an array of that size. That is, if you declare your pockets variable as array of 10 QueueReferenceBased objects, you won't have to write pockets.get(i) but instead a simpler pockets[i] will do.

[Piet Souris]

Correct, but this code is given. The code given is however a bit unclear about this point.
In one method, NUMBASE is a parameter, but in the other method (radix) it is not and it is fixed
at 10.

Besides, the array would have to be of the type QueueReferenceBased<Integer>
or ArrayList<Integer>, and try
to create an array ArrayList<Integer>[10].
See if you can manage that! I couldn't, and in my first post you can see me make a
note of this.

[Junilu Lacar]

So, the section of code below is given and you can't change it?

public static void radix(QueueReferenceBased<Integer> Q, int k){
	System.out.println("~~  sorting column "+k +" ~~");
	final int NUMDIGITS = 5; // maximum number of digits in data
	final int NUMBASE = 10; // decimal numbers, base 10
	// creation of the array
	ArrayList <QueueReferenceBased<Integer>> pockets = 
	    new ArrayList <QueueReferenceBased<Integer>>(NUMBASE);
	//instantiation of the array
	for (int i=0; i<NUMBASE; i++)
	    pockets.add(i,new QueueReferenceBased><Integer>());
	//enqueue the appropriate pockets

Because Line 6 is not a good practice. If you really had to use a List, it would be better as:
List<QueueReferenceBased><Integer>> pockets = new ArrayList<>(NUMBASE);
But the fact that you're passing NUMBASE as an argument to the constructor just reinforces my assertion that it would be better and simpler to just use a simple array:
QueueReferenceBased<Integer>[] pockets = new ...[NUMBASE];
Ah well, you guys keep going. I'll just watch how this plays out.

[David Bilger]

Piet Souris wrote:Strange. The code in the 'radix' method has this piece:

ArrayList <QueueReferenceBased<Integer>> pockets = 
	    new ArrayList <QueueReferenceBased<Integer>>(NUMBASE);
	//instantiation of the array
	for (int i=0; i<NUMBASE; i++)
	    pockets.add(i,new QueueReferenceBased<Integer>());

So, pockets.get(i) should definitely work.

Can you show me the code you have for 'radix' so far?

    public static void radix(QueueReferenceBased<Integer> Q, int k){
	System.out.println("~~  sorting column "+k +" ~~");
	final int NUMDIGITS = 5; // maximum number of digits in data
	final int NUMBASE = 10; // decimal numbers, base 10
	// creation of the array
	ArrayList <QueueReferenceBased<Integer>> pockets = 
	    new ArrayList <QueueReferenceBased<Integer>>(NUMBASE);
	//instantiation of the array
	for (int i=0; i<NUMBASE; i++)
	    pockets.add(i,new QueueReferenceBased<Integer>());
	//enqueue the appropriate pockets
	
	/* TO COMPLETE */
	// dequeue the pockets in the appropriate order
	// and print the elements right-aligned

	ArrayList <QueueReferenceBased<Integer>> bucket = 
		    new ArrayList <QueueReferenceBased<Integer>>(NUMBASE);
	
	
	
	for (int i = NUMBASE - 1; i <= 0; i--)
	{		
		pockets.get[i].enqueue(i);
	}
	
	for (int i = NUMBASE -1; i >= 0; i--) {
	    QueueReferenceBased<Integer> q = pockets.get(i);
	    while(!q.isEmpty()) {
	        Q.enqueue(q.dequeue());
	    }
	}
	
}

[David Bilger]

Junilu Lacar wrote:So, the section of code below is given and you can't change it?

public static void radix(QueueReferenceBased<Integer> Q, int k){
	System.out.println("~~  sorting column "+k +" ~~");
	final int NUMDIGITS = 5; // maximum number of digits in data
	final int NUMBASE = 10; // decimal numbers, base 10
	// creation of the array
	ArrayList <QueueReferenceBased<Integer>> pockets = 
	    new ArrayList <QueueReferenceBased<Integer>>(NUMBASE);
	//instantiation of the array
	for (int i=0; i<NUMBASE; i++)
	    pockets.add(i,new QueueReferenceBased><Integer>());
	//enqueue the appropriate pockets

That is correct. I cannot change it.

[Junilu Lacar]

Look very carefully at the difference between the pockets.get on line 24 and the pockets.get on line 28.

for (int i = NUMBASE - 1; i <= 0; i--) { pockets.get[i].enqueue(i); } for (int i = NUMBASE -1; i >= 0; i--) { QueueReferenceBased<Integer> q = pockets.get(i); while(!q.isEmpty()) { Q.enqueue(q.dequeue()); } }

[Junilu Lacar]

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.

[David Bilger]

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.

Then I am pretty confused. What would you suggest?

In regards to looking at the different implementations of get, one is assigned to q, of type QueueReferencedBased.

[Junilu Lacar]

On line 24 you are using square brackets with get. Square brackets are used with arrays. That is why you are seeing that message you are seeing. get is a method and needs to be followed by parentheses.

That is why I suggested that you lay out the procedure in English. When we do solutions in math, we lay out the problem like this:
Let x and y be the sides of a triangle Let a be the angle formed by sides x and y
Likewise, you need to remember what variable i is for. It might be easier to remember if you rename it to something more meaningful, say pocketNumber. That way, when you write

    pockets.get(pocketNumber).enqueue(pocketNumber);

you can immediately see that it doesn't make sense.

[Junilu Lacar]

I have to be honest with you, David. It's been pretty hard for me to watch this thread because I can imagine the frustration/helplessness/confusion you must be feeling trying to work through this problem.

From my vantage point, however, it's like I'm watching you try to fix a car by randomly poking around and trying different things without really understanding what it is you're doing. This approach will not work very well for fixing a car much less for programming a computer. You have to understand how the different parts work and how they are going to come together. I understand you are a beginner and you are naturally floundering about. That's fine. But you have to try to attack this problem in a systematic way.

Let me try one more time to show you one such way:
Prepare 10 pockets, numbered 0 to 9 Given a list of unsorted numbers Take each number from the unsorted list and get its least significant digit (the digit in the 1s place) If the digit is 0, put the number in pocket 0 If the digit is 1, put the number in pocket 1 ... and so on If the digit is 9, put the number in pocket 9 put all the numbers in pocket 0 back in the original list put all the numbers in pocket 1 back in the original list ... put all the numbers in pocket 9 back in the original list Repeat the procedure, only this time, use the digit in the 10s place to sort Repeat the procedure, only this time, use the digit in the 100s place to sort ... Repeat the procedure ... until there are no numbers that have a digit in the Ns place When all this is done, the numbers in the list will be sorted.
You see how it's all in plain English? Now you have to look at each instruction and see if you can break it down further into smaller steps. When you can't break an instruction down any more, then you can translate it to code.

For example, the instruction on line 1 has already been translated to Java for you. That's in the code that you were given, the code you said can't be changed. Don't take the instruction too literally though - it's the general idea that's important here. Can you identify that section of code?

The group of similar instructions that start at line 7 can actually be translated into a single line of code in Java that uses that pocketNumber variable that I suggested before, for example. The instruction on Line 5 can be translated into a Java statement that calls the getKthNumber method and the value it calculates should be used in that one Java statement that accomplishes the work to carry out the instructions for lines 7 to 10.

The instructions on lines 12 to 15 can be translated to a Java statement that uses enqueue and dequeue.

Lines 17 to 20 hint at some kind of loop with an exit condition.

So you see, if you decompose the problem into smaller problems, it's easier to attack each small problem in turn and string up all these small solutions together to solve the bigger problem.

I hope you start to see now why I've been pushing for you to lay out the procedure in plain English.

Good luck.