CS65 Fall 2008            Assignment 10      Optional, Extra Credit Bonus

                  Quicksort in ISCAL Assembly Language

In order to qualify for credit, the program must be submitted no later than
Fri. Dec. 5.

The ISC (Incredibly-Simple Computer) has been described in the class and in the
notes.  Program the ISC using its assembly language ISCAL to read in an array
(up to end-of-file), perform recursive quicksort on the array, and write out the array
in sorted order.  The program should successfully any number of up to 1000
unordered integers.

Java code for quicksort is listed below.  However, you are given in ISCAL
everything but the part involving the recursive calls, so "all" you have to do
is implement these calls.

The following ISC files, found at

    http://www.cs.hmc.edu/~keller/isc/

should be of interest:

    array_io.isc Code to read in an array and print it out

    part.isc     Like array_io.isc, but with an added to call
                 to subroutine 'part' which performs the 
                 partition phase of quicksort.

    rfac.isc     A recursive factorial program, using a stack.
                 This shows how a stack can be implemented
                 on the ISC.

Your quicksort can be built by modifying subroutine 'part' in part.isc.  
After partitioning the array, quicksort makes two recursive calls to itself.
What you have to do is add the code for making these recursive calls.

Note that quicksort does not need to return a value; rather it modifies
its argument array in place.  It is recommended that the array be represented
by pointers to the bottom and top locations in the array.  This is the
way that 'part' is set up.  Subroutine 'part' also returns the pivot
element as a value.  This value is not needed for quicksort.

It is probably easiest to replace the indexing typically used in quicksort by
pointers to the corresponding array elements.  This will avoid adding the index
to the array base every time an array element is accessed.

Submit your ISCAL file for the complete program: qsort.isc.

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

class Quicksort
  {
  private float a[];

  Quicksort(float array[], int N) // Setup, using constructor
    {
    a = array;
    }

  void sort()                     // Sort the array
    {
    divideAndConquer(0, N-1);
    }

  void divideAndConquer(int low, int high)
    {
    if( low >= high )
      return;                           // basis case, <= 1 element

    float pivot = a[(low + high)/2];    // select pivot

    // shift elements <= pivot to bottom
    // shift elements >= pivot to top

    int i = low-1;
    int j = high+1;

    for( ; ; )
      {                             // find two elements to exchange
      do { i++; } while( a[i] < pivot );  // slide i up
      do { j--; } while( a[j] > pivot );  // slide j down

      if( i >= j ) break;           // break if sliders meet or cross

      swap(i, j);                   // swap elements and continue
      }

    divideAndConquer(low, i-1);     // sort lower half
    divideAndConquer(j+1, high);    // sort upper half
    }


  /**
    *  swap(i, j) interchanges the values in a[i] and a[j]
   **/

  void swap(int i, int j)
    {
    float temp = a[i];
    a[i] = a[j];
    a[j] = temp;
    }
  }