Having Trouble implementing this Radix Sort

[Campbell Ritchie]

Too difficult for “beginning” Discussion moved.

[Piet Souris]

After a 4 hour night sleep and a very busy working day ahead of me, I took some time to re-read this topic. It is a very interesting topic, I must say, both for good and for bad reasons. The good reasons being the subject that is interesting (I had never heard of the radix sorting algorithm, but all it takes is a five minute Youtube film, it is that easy. And it is a lively topic, with very quick responses.
We see also some bad reasons. I see that this topic is rather chaotic, that two people are trying to help OP in achieving his goal, but having different philosophies and different starting points, and an OP who states his problem is only in the implementing part. So, with some reflection, this is what I noted:

@Junilu:
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?

@David
I notice a lack in understanding queue’s and arraylists. Why did you think (or the person that gave you this assignment) you were up to this task, where you are being asked to show some good knowledge about these structures?

@Me
I stepped in because I thought that the implementation was a simple matter, just a few lines of code, after watching this youtube film. My strategy was based on this’ site philosophy that we’re only here to help, but we are not supposed to write ready-to-use code for other people. Since it was all about the implementation, I came with a lot of questions, like “must we use the input que when refilling, or can we create another que for this”. I hoped to get an impression about what OP knew so far. But looking back at these attempts, it looks like it is giving more confusion than that it leads to some firm answers. And I screw up at places. I noticed that I gave the code ‘pockets.get[k]’ instead of ‘pockets.get(k)’, and I didn’t know that this Que-class was non-iterable, so that you could not use the ‘enhanced for-loop. And I really struggled trying to let OP do the coding, although it became clear that that was going to be a big problem. So, I admit, this is an awkward position, and I will try one desparate attempt to save as much as I can. I’ll give the code as I would have written it, but at strategic points I put ‘??’ to indicate to David where he is supposed to fill in something useful.

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

         final int MAXNUMBER = (int) Math.pow(NUMBASE,k)
         Boolean notYetFinished = false;

	// creation of the array
	ArrayList <QueueReferenceBased<Integer>> pockets = new ArrayList <>(NUMBASE);

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

	// dequeue the pockets in the appropriate order
	// and print the elements right-aligned
 
	// int[] bucket = new int[10];  don’t know where this is good for
	
		while (!Q.isEmpty())
		{
			System.out.print(Q.peek());
                            int number = Q.dequeue();
			int pocketnumer = getKthNumber(Q.dequeue(), k, 10);
                            // put the number into the correct pocket
                            pockets.get(??).enqueue(??)
                            // see if the number is bigger than MAXNMBER; if it is, then we are
                            // not finished yet
                            if (?? >= MAXNUMBER) {
                                notYetFinished = true;  
                            }          
		}

                   // filling Q again
                   for (QueueReferenceBased<Integer> q: pockets) {
                        // dequeue q and  queue that number into the input Q
                        int number = q.??;
                        Q.enqueue(??);
                   }   
	
	
	
	/* TO COMPLETE */
        // Make recursive call if necessary
	if (notYetFinished) {
              radix(??, ??);
         }

	/* TO COMPLETE */
         // print the elements, right aligned
         while (!Q.isEmpty {
             int number = Q.??;
             // and print this number
         }
         
    } // end RadSort

If you have implemented this, do not forget to test it as much as you can!

Greetz,
Piet

PS: I see that this code is completely scrambled (I copied it from Word),
so I give it again, as text.

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

final int MAXNUMBER = (int) Math.pow(NUMBASE,k)
boolean notYetFinished = false;

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

while (!Q.isEmpty())
{
System.out.print(Q.peek());
int number = Q.dequeue();
int pocketnumer = getKthNumber(Q.dequeue(), k, 10);
// put the number into the correct pocket
pockets.get(??).enqueue(??)
// see if the number is bigger than MAXNMBER; if it is, then we are
// not finished yet
if (?? >= MAXNUMBER) {
notYetFinished = true;
}
}


/* TO COMPLETE */
// dequeue the pockets in the appropriate order

// filling Q again
for (QueueReferenceBased<Integer> q: pockets) {
// dequeue q and queue that number into the input Q
int number = q.??;
Q.enqueue(??);
}

// and print the elements right-aligned


// Make recursive call if necessary
if (notYetFinished) {
radix(??, ??);
}

/* TO COMPLETE */
// print the elements, right aligned
while (!Q.isEmpty() {
int number = Q.??;
// and print this number
}

} // end RadSort

[Junilu Lacar]

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.

[David Bilger]

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.

No worries, you have been very helpful and patient with helping me. I will be tackling this more tonight.

[David Bilger]

Ok I made some changes and have come up with the following code.

	while (!Q.isEmpty())
		{
		//	System.out.print(Q.peek());
			int number = Q.dequeue();
			int pocketnumber = getKthNumber(number, k, 10);
			// put the number into the correct pocket
			pockets.get(pocketnumber).enqueue(number);
		}

		for (QueueReferenceBased<Integer> q : pockets) {

			while (!q.isEmpty())
			{
				System.out.println(q.peek());
				int number = q.dequeue();
				// put the number into the correct pocket
				Q.enqueue(number);
			}   
		}

		/* TO COMPLETE */
		// Make recursive call if necessary

		if (k != NUMDIGITS) 
		{
			radix(Q, k+1);
		}
		
		
		/* TO COMPLETE */// print out elements right aligned
		// end RadSort

while (!Q.isEmpty())
		{
			System.out.printf("%+7d\n", Q.peek());
			Q.dequeue();
		}
		
		
		
	}

How do you like the implementation?

[Stefan Evans]

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?

[David Bilger]

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?

Ah yes thank you for noticing the comments. Do you mean the NUMBASE constant?

My results are properly sorted!

Thank you to everyone who helped me, I really appreciate it.

[Stefan Evans]

Yeah. NUMBASE constant.
And you can probably get rid of the "TO COMPLETE" comments as well :-)

[Junilu Lacar]

I plugged your code into a JUnit test I wrote for my implementation and it worked like a charm.

Here's the test output:
Unsorted:[78, 97, 88901, 50998, 63106, 7938, 4122, 310, 89, 5554, 82709, 430, 61013, 7787, 795, 31, 2843, 298, 68, 74] 310 430 88901 31 4122 61013 2843 5554 74 795 63106 97 7787 78 50998 7938 298 68 89 82709 88901 63106 82709 310 61013 4122 430 31 7938 2843 5554 68 74 78 7787 89 795 97 50998 298 61013 31 68 74 78 89 97 63106 4122 298 310 430 5554 82709 7787 795 2843 88901 7938 50998 31 68 74 78 89 97 298 310 430 795 50998 61013 82709 2843 63106 4122 5554 7787 7938 88901 31 68 74 78 89 97 298 310 430 795 2843 4122 5554 7787 7938 50998 61013 63106 82709 88901 +31 +68 +74 +78 +89 +97 +298 +310 +430 +795 +2843 +4122 +5554 +7787 +7938 +50998 +61013 +63106 +82709 +88901 Expected:[31, 68, 74, 78, 89, 97, 298, 310, 430, 795, 2843, 4122, 5554, 7787, 7938, 50998, 61013, 63106, 82709, 88901] Result:[31, 68, 74, 78, 89, 97, 298, 310, 430, 795, 2843, 4122, 5554, 7787, 7938, 50998, 61013, 63106, 82709, 88901]
In case you're curious, the JUnit test is:

	@Test
	public void check_davids_implementation() throws Exception {
		RadixSort radix = new RadixSort();
		List<Integer> unsorted = new ArrayList<>(); 
		addRandom(unsorted, 5, 99999);
		addRandom(unsorted, 5, 9999);
		addRandom(unsorted, 5, 999);
		addRandom(unsorted, 5, 99);
		
		List<Integer> sorted = new ArrayList<>(unsorted);
		Collections.sort(sorted);
		Collections.shuffle(unsorted);
		
		System.out.println("Unsorted:" + unsorted);
		
		List<Integer> result = radix.davidsSort(unsorted);
		
		System.out.println("Expected:" + sorted);
		System.out.println("Result:" + result);
		
		assertEquals(sorted, result);
	}

	private void addRandom(List<Integer> unsorted, int times, int max) {
		for (int i = 0; i < times; i++) {
			unsorted.add(generator.nextInt(max));
		}
	}

[Junilu Lacar]

A few comments about this code:
for (QueueReferenceBased<Integer> q : pockets) { while (!q.isEmpty()) { System.out.println(q.peek()); int number = q.dequeue(); // put the number into the correct pocket Q.enqueue(number); } }
I don't particularly like the variable names Q and q; it's too easy to get confused between the two. The code below makes the intent clearer, IMO. You can also get rid of the temporary number variable.
for (QueueReferenceBased<Integer> pocket : pockets) { while (!pocket.isEmpty()) { System.out.println(pocket.peek()); Q.enqueue(pocket.dequeue()); } }
I go even further:
... ... for (QueueReferenceBased<Integer> pocket : pockets) { transfer(pocket, Q); } ... } /** * Removes items from the given source queue and * puts them in the given target queue. */ private void transfer(QueueReferenceBased<Integer> source, QueueReferenceBased<Integer> target) { while (!source.isEmpty()) { System.out.println(source.peek()); target.enqueue(source.dequeue()); } }
This is what I meant by breaking your program down into very small tasks.

But you did good. Congratulations!

[Piet Souris]

Well done, David!

I think you are now up to answering a question that I put earlier:

You:
After that, I would go through, from right to left, putting those items starting with kth number 9 back into the original queue.

Me:
Agreed. In what order will you get the numbers, according to this strategy?

Greetz,
Piet