ROBLEM 2: Typically, Radix Sort designed/implemented using two two arrays of lists (or queues): a "from" array and a "to" array (the dimension of each array is the radix being used).

At the start of each pass, the elements are distributed among the lists in the from array; as they are processed they are moved to the to array.

In the sample implementation discussed in class (and posted under the Week-07 lab), a single pass is performed by the code segment below.

Code for 1-pass of RadixSort using conventional 2-array approach
1 2 3 4 5 6 7	for(i=0; i while(!lst_is_empty(from[i])){ // dequeue elements in from[i] x = lst_pop_front(from[i]); digit = (x/divisor)%radix; lst_push_back(to[digit], x); } }

Professor Periwinkle thinks that just one array of dimension radix is sufficient and proposes the following code instead to perform a single pass with just one array called buckets of dimension radix:

Prof. Periwinkle's code for 1-pass of RadixSort using just one array
1 2 3 4 5 6 7 8 9	int n; for(i=0; i len = lst_length(buckets[i]); // list length before processing elems for(j=0; j x = lst_pop_front(buckets[i]); digit = (x/divisor)%radix; lst_push_back(buckets[digit], x); // same array } }

The first thing you notice is that the condition for the innermost loop has changed (lines 4-8). You figure out that this change prevents infinite loops, because buckets[i] might never become empty (like from[i] does in the 2-array approach). Consider for example x=33 and radix=10. During the 2nd pass, buckets[3] will never become empty! This explains why variable len set on line 3 is used to determine the number of iterations through the innermost loop.

So far so good. It doesn't loop for ever. Big deal.

You are still having trouble getting your head around Periwinkle's 1-array approach and whether or not it is really correct. So, you go to Periwinkle's office hours where you have the following conversation based on the assumption that radix==10:

You: It seems like an element can be processed twice during a single pass.

Periwinkle: Explain.

You: For example, consider x=52. At the beginning of the 2nd pass (for the 10s place), 52 should be in buckets[2]. When i==2, it will be removed from buckets[2] and assigned to buckets[5].. Later in the same pass, when i==5, it will be processed again won't it?

Periwinkle: True. However, it will simply be reassigned to the same bucket -- buckets[5] right? So, it still ends up in the correct bucket doesn't it?

You: Yes, but doesn't it seem weird and redundant to reassign it to the list it is already correctly in?

Periwinkle: Redundant, yes. Weird, maybe. My claim is simply that we still correctly sort the elements in my one-array approach. Let me show you an example. Let's say we want to sort 58, 53, 52.

[Periwinkle goes to chalkboard and draws the diagrams below]

	0
	1
	2	52
	3	53
	4
	5
	6
	7
	8	58
	9

	0
	1
	2
	3
	4
i	5	52 53
	6
	7
	8	58
	9

	0
	1
	2
	3
	4
i	5	53 52
	6
	7
	8	58
	9

	0
	1
	2
	3
	4
	5	52 53
i	6
	7
	8	58
	9

	0
	1
	2
	3
	4
	5	52 53 58
	6
	7
	8
	9

(A): after 1st pass

(B) during 2nd pass when i==5; before j-loop starts.

Note: len==2

(C) still 2nd pass and

i==5. But after 1st iteration of j-loop:

52 popped from buckets[5], then pushed onto back of same list

(D) After bucket[5]

has been processed: 2nd iteration of j-loop pops 53 and then pushes it.

Fig (B) restored!

(E) after 2nd pass completes (when i reaches 8, we pop 58 from buckets[8] and push it onto the back of buckets[5].

Yay!

Periwinkle continues: After the first pass, we should have configuration (A) correct?

You: Yeah.

Periwinkle: Great. Ok, let's look at the 2nd pass - the 10s place. By the time i==5, 52 and 53 have been assigned to bucket[5] and we should have figure (B) right?

You: Wait! i==5, but what about the inner-most loop, the "j-loop"? Has it started yet?.

Periwinkle: Good question! No! The code has just determined that len==2, but the "j-loop" has not yet started.

You: Ok, I agree with diagram (B). But now we're going to mess around with 52 and 53 again. Won't that mess things up?

Periwinkle: Let's see! When j==0, 52 will be popped from the front of buckets[5] and immediately pushed onto the back of buckets[5] resulting in figure (C).

You: Yes, but now the list is out of order! Wait... I see. The j-loop will do one more iteration which will pop the 53 and push it on the back of the same list. That produces your figure (D) which is the same as (B) right?

Periwinkle: Yes! You are very clever! We just kind of "rotated" the list len-times back to its initial configuration which was sorted to begin with! No harm done!

You: Yeah. Still seems weird to do all that work just to get back where we started in figure (B).

Periwinkle: I like weird.

You: Whatever. I see that we have the sorted sequence. If we did one more pass, they would end up in buckets[0] in the same order.

Periwinkle: Ta-Dah!! It works!

You: Wait! Did you just say "it works"? If there is anything I know about programming it is that one test case doesn't prove anything about correctness in general! Professor Pollywog taught me that!

Periwinkle: Pollywog's a dope! This is good enough to convince me!

Of course, Periwinkle is wrong! His 1-array approach does not work in general.

Your job: Find and clearly explain a counter-example -- i.e., an input that that Periwinkle's approach does not sort correctly. Use a radix of 10 for simplicity and explain what happens using drawings like above.

Hint: Two 2-digit numbers are all you need for a counter-example!