Recitation 10/29/97

* Go over old quiz
* Radix sort
* anything else students have questions on

Quiz will cover sorting (mergesort, quicksort, heapsort, radix sort),
heaps, recurrences, divide-and-conquer, hashing
============================================================================

Old quiz
--------
1A:    0  1  2  3  4  5  6
       P     G  S  R  I  N

1B: we'd get into an infinite loop when we inserted N.


2:
	A->next = merge (A->next, B);

	B->next = merge (A, B->next);

3A: The first loop takes constant time (256), the second loop takes
O(n) time, and the last loop takes time O(n).  So, the overall time is
O(n).

3B: 

	baker
	danny
	burch
	avrim
	bruce
	elvis

(note that the order of "burch" and "avrim" has switched because we
insert new strings onto the top of the bucket, and we remove from the
top downward, so  everything in the same bucket is now in the opposite
order it used to be in)


3C: 
	for(i=255, j=n-1; i >= 0; --i) {
	  temp = bucket[i];
	  while (temp != NULL) {
	    string_array[j] = temp->string;
	    temp = temp->next;
	    --j;
	  }
        }


3D:
	change the line:
		for(j=0; j < n; j++) {
	to:
		for(j=n-1; j >= 0; j--) {

	(this has the effect that the buckets now have their strings
	in the correct order)


----------------------------------------------------------------


Radix sort
----------
   Good method for sorting strings.  If n strings of length L each, takes
   O(n*L) time.

Example (all students in class with first names beginning with "E"):
(names from last year)

	eb3z eg27 ek2u ek35 ec3h ep2u ey27 ec2q ef2g ef2q ek00 el28 es58

 Most-Significant-First: Put into buckets based on most significant
	character, then recursively sort each bucket that has > 1 element,
	starting at next-most significant character.  Finally, concatenate
	buckets.

        step 1: just get 1 bucket.
 	step 2, have:
                                  ek35
                ec3h  ef2g        ek2u
         eb3z   ec2q  ef2q  eg27  ek00  el28  ep2u  es58  ey27
         ----   ----  ----  ----  ----  ----  ----  ----  ----

        now, recursively sort 2nd, 3rd, 5th buckets, then concatenate.

 Least-Significant-First: Do a STABLE sort based on least significant
	character (remember what stable means?). Then do again based on
	2nd-least significant, etc, until finally do based on most
	significant.

	(lets say that digits are less than characters)

	step 1:
	ek00 ek35 eg27 ey27 el28 es58 ef2g ec3h ec2q ef2q ek2u ep2u eb3z

	step 2:
	ek00 eg27 ey27 el28 ef2g ec2q ef2q ek2u ep2u ek35 ec3h eb3z es58

	step 3:
	eb3z ec2q ec3h ef2g ef2q eg27 ek00 ek2u ek35 el28 ep2u es58 ey27

	(Trace ef2g and ef2q.  Notice they get in correct order in 1st
	step, and then STAY in correct order since the sort is STABLE)

(ASK)
 advantages of LSF: no recursion. Just a big "for" loop
      note: "radix sort" usually refers to LSF

 advantages of MSF: sometimes you will get lucky and buckets get down
      to size 1 before you're done reading all the string (just like
      how strcmp sometimes is lucky and doesn't have to read down entire
      string to check that the two are different)


heapsort:  do an example if people want.

	There is also now a graphical heapsort demo students can run
	by typing "heap_demo".