CS 42
Assignment 8
Due Wed. 28 November 2012 (11:59 pm)

Assembly Language Programming 
and 
Recursion Implementation

The ISC (Incredibly-Simple Computer) has been described in the lecture and on the following web page:

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

In this document, we refer to certain files. Some of those files are on the CS server, e.g. at 
knuth.cs.hmc.edu
in directory
/cs/cs60/isc

A subset of the files may also be found on the web page above. To get on the server, use a terminal window on your computer and execute

ssh -l <your login> knuth.cs.hmc.edu

then enter your password. To connect to the directory

cd /cs/cs60/isc

Program the ISC using its assembly language ISCAL to read in an array
(up to end-of-file), perform a recursive quicksort on the array, and write out the array in sorted order.  The program should successfully any number of up to 2000 unordered integers, such as the contents of the file /cs/cs60/isc/unordered.in.

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 should be of interest:

    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 and how it can be used for recursion.

    isc.doc      The ISC instruction set, although the web page is more current.

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.

Here is how we will test it:

    /cs/cs60/bin/random 2000 > unsorted.in
    java -classpath /cs/cs60/isc/ quicksort < unsorted.in > sorted.out
    isc qsort.isc < unsorted.in | diff - sorted.out

The first line creates a file with random numbers.  The second line sorts
the file according the Java program.  The third line sorts it with your
ISCAL program and compares the result to that of the java program.

There should be no output from the last line, indicating that your program's
(qsort.isc) output is identical to sorted.out.

To run the above commands, you will need to be connected to your own directory. Simply execute the command
	cd
to get there.

------------------------------------------------------------------------------
Java quicksort program for guidance. The array is sorted when the constructor is called.

class quicksort
  {
  private float a[];

  /*
   * Calling quicksort constructor on array of floats sorts the array
   * in place.
   * Parameter N is the number of elements to be sorted.
   */

  quicksort(float array[], int N)
    {
    a = 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;
    }
  }