Simonson - CS304 - Computer Architecture
Assembly Language Using MIPS
Procedures, Recursion, Stacks, and Activation Records
Due Tuesday, March 22 (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. I may review the details in
class. 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
Carefully create all frames (activation
records) and keep track of all appropriate registers on the
stack. You should have a main program that reads in a list of
integers into an array A, and then calls a recursive procedure
QSort (A, 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.
The base address of the array never changes so
it can be left global.