Professor Shai
Simonson - CS304 - Computer
Architecture
Assignment 4
Assembly Language Using MIPS
Procedures, Recursion, Stacks, and Activation Records
Due Monday, November 5. (30 points)
Quicksort
Write a recursive SPIM program that implements
Quicksort. You
can look up Quicksort in any
data structures or algorithms text, and we will also review it briefly
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.
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 the array A.
Make sure to
reference all local recursive variables through the frame pointer
($fp). There
are three of them: A - the base address of the array, start - the
starting
index of the sort, and finish - the finishing index of the sort.
(Actually the base address of the array never changes so it can be left
global).
http://www.stonehill.edu/compsci/shai.htm