This assignment consists of a program, and a bit of written work which must be turned in on paper at the beginning of class, 16 February 2007.

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.

Assembling

Write a very simple C program, compile it on a PC, compile it on a Mac, and compile it on Linux (and others, if you want). Do the compilation with gcc -S to get only the assembly code. Compare the different assembly codes, and see if you can identify any commands.

What to turn in

For this assignment, please turn in a copy of your source code plus the output of a successful run of the quicksort program. 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. Additionally, turn in the assembly and C source that you compiled on various platforms, along with any guesses as to the assembly language instructions found there.