Professor
Shai Simonson - CSC 304 - Computer Architecture
Assignment 4
Assembly Language Using MIPS
Procedures, Recursion, Stacks, and Activation Records
Due Wednesday, March 27 (Total: 30 points)
Chapters 2 and 3: (4 points) 2.14, 2.15, 2.24, 3.21
Quicksort
Program (26 points) Write a
recursive SPIM program that implements Quicksort on
integers. You can look up Quicksort in any data
structures or algorithms text. Here is a nice
video that reviews the algorithm using Java code.
The Partition part of the algorithm should be implemented as a
procedure call. The input should 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.
http://www.stonehill.edu/compsci/shai.htm