This assignment consists of a single program, and must be turned in on paper at the beginning of class, 19 October 2006.

Quicksort

You must write a MIPS assembly language program that implements a quicksort algorithm on an array of integers.

The quicksort algorithm sorts elements of an array in place. It does this by choosing a value in the array as a 'pivot' value, moving values either to the left or right of the array depending on whether the values are less than or greater than the pivot value, respectively, and placing the pivot value in the space in between these two sections of the array. It then recursively calls quicksort on each of the two sections.

The following is some code in C/Java which shows the algorithm:

void quicksort( int[] array, int p, int r) {
  if( p < r) {
    int q = partition( array, p, r);
    quicksort( array, p, q - 1);
    quicksort( array, q + 1, r);
  }
}

int partition( int[] array, int p, int r) {
  int pivot = array[ r];
  int i = p -1;
  for( int j = p, j < r; j++) {
    if( array[ j] <= pivot) {
      i = i + 1;
      swap( array, i, j);
    }
  }
  swap( array, i + 1, r);
  return( i + 1);
}

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

As shown in class, the swap procedure doesn't need to store anything on the stack because it is a leaf procedure.

For this assignment, please turn in a copy of your source code plus the output of a successful run. A successful run will have moved the values in a declared array into their sorted order. Print or screen capture the .data section of memory as shown by the simulator before and after your program has run.