Professor Shai Simonson - CSC 304 - Computer Architecture

Assignment 4

Assembly Language Using MIPS
Procedures, Recursion, Stacks, and Activation Records


Due  Friday, March 23  (Total:  20 points)

Chapter 2:  (5 points)  2.14, 2.15, 2.24, 3.21


Program  (15 points)  Write a recursive SPIM program that implements Quicksort on integers.  You can look up Quicksort in any data structures or algorithms text.  The Partition part of the algorithm should be implemented as a procedure call.  The input can be accomplished using positive numbers and -1 to signify the end of input. Make sure to test your program with multiple duplicate values.

Carefully create all frames (activation records) and keep track of all appropriate registers on the stack. Quicksort expects only two parameters -- start and finish. The base address of the array A never changes so it can be left global. You should have a main program that reads in a list of integers into an array A, and then calls a recursive procedure QSort (1, A.length) to sort and print the array A.

Make sure to reference all local variables in the recursive method  through the frame pointer ($fp). There are three local variables: 

start - the starting index of the sort, 
finish - the finishing index of the sort, and
mid - the return value from partition.

Quicksort will accept start and finish from registers $4 and $5. The first things that Quicksort does after it creates its stack frame is to move $4 (start) to 0$fp) and $5 (finish) to -4($fp). After it finishes partitioning the array, it moves mid into -8($fp).

You can look here to review the general guidelines for MIPS procedures and stack frames.