CSC161 2010F, Class 41: Pause for Breath

Overview:
* About Assignment 8
* Questions on Assignment 7
* Lab.

Admin:
* We may have prospies today.  Yay!
* EC for RHPS
* Saturday 1-3, kids from town are doing art at Faulconer.  
  You may have fun coming, too.
* Assignment 8 is ready.
* For Monday, read K&R 6.1-6.5 and send questions!.
* I hear that Assignment 7 is harder than I intended.  Sorry.

Question on HW 7

* What should the specification of generic sort look like?

PREFIX(sort) (TYPE values[], int size);

* What should int-sort.h look like?

#define TYPE int
#define PREFIX(FUN) int_ ## FUN
#define MAY_PRECEDE(X,Y) (X < Y)
#include "generic-sort.h"

* What should int-merge-sort.c look like?

#include "int-sort.h"
#include "generic-merge-sort.c"

* That's it?

You could have comments, too, but that's basically all you should need.

* Should it have a main?

No.  The file you link should have a main.  E.g., int-sorter.c or
int-sort-unit-test.c or  ...

* How does Bubble Sort work?
  for (last = size-1; last >= 0; last--)
    for (i = 0; i < size-1; i++)
      if a[i] and a[i+1] are out of order, then swap them

* Quicksort does not take three inputs?

* Can you write quicksort for us?
void 
quicksort(int values[], int size)
{
  qsort(values, 0, size);
}
Copy qsort from K&R.
Reformat.
Cite.

* Should we use an in-place Quicksort
  * Of course.
* Will we see a difference between in-place and out of place Quicksort?
  Probably not.  If you do it really stupidly and have large data sets,
  your program may exceed available memory, particularly on our wimpy
  32 bit systems.