Harvey Mudd College

Computer Science 60

Spring 2003

Assignment 12
Optional, Extra Credit

In order to qualify for credit, the program must be submitted no later than midnight, the evening of Sunday, 11 May.

Because of the late time in the semester, the grading on this assignment will be all-or-nothing. We will not check for comments or style. If your program sorts a randomly-selected file of 500 integers, you get full credit. There will be only minor partial credit given if your program doesn't work.

The ISC (Incredibly-Simple Computer) is described in the lecture slides and textbook. Program the ISC using its assembly language ISCAL to read in an array (up to end-of-file), perform quicksort on the array, and write out the array in sorted order. The program should successfully any number of up to 500 unordered 32-bit 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, in /cs/cs60/isc, should be of interest:

File Name	Purpose
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.
isc.doc	The ISC instruction set, reproduced from the notes.

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 addresses, i.e. pointers to the bottom and top locations in the array. This is the way that part is set up.

NOTE: Subroutine 'part' also outputs the pivot element as a value. This value is not needed for quicksort, so you will not want to output it.

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 500 > 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.


class quicksort
{
private float a[];

/**
* Calling quicksort constructor on array of floats sorts the array.
* 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;
}
}