void quicksort (integer A[], integer p, integer r) begin
integer q;
if p < r then
q := partition(A, p, r)
quicksort(A, p, q)
quicksort(A, q+1, r)
end if
end quicksort
integer partition (integer A[], integer p, integer q) begin
integer pivot := A[p]
integer i := p-1
integer j := q+1
while (true)
repeat j := j-1 until (A[j] <= pivot)
repeat i := i+1 until (A[i] >= pivot)
if i < j then
swap(A[i], A[j])
else
return j
end if
end loop
end partition
Your job is to write the two procedures partition and quicksort, as
well as a main procedure. Your main should do the following:
Enter size of array to sort (max 10000; negative size to quit): 100 Enter the random seed: 23 Array sorted successfully. Enter size of array to sort (max 10000; negative size to quit): 320 Enter the random seed: 42 Array sorted successfully. Enter size of array to sort (max 10000; negative size to quit): -1 Bye.Notice that 0 can either be an erroneous input, or an exit condition. It is up to you.
To make your life easier, we've provided some routines for filling an array with random numbers and checking if an array is sorted. Use these routines by jumping to them. The specification for these functions is:
# initRandArray # arguments: $a0 base address of array of words # $a1 length of array (integer) # $a2 seed for random number generator (integer) # return val: none # Fill in the specified number of words starting at the memory location # given in $a0. Behavior is unspecified for non-positive size # arrays. # isSorted # arguments: $a0 base address of array of words # $a1 length of array (integer) # return val: 1 if sorted; 0 if otherwise # Check if given array is sorted in ascending order. # By default, arrays of length 1 are "sorted." The "sortedness" of # non-positive length arrays is unspecified.
We provide these routines to you by altering the trap.handler file which PCSpim uses. You must download this file, and set PCSpim to use it as the trap handler in order to use these routines. See the software page for instructions on how to do this. Note that it is not the same as loading the file into PCSpim. Once PCSpim is using this as its trap handler, you can simply jal isSorted with the arguments set up correctly, and everything should work.
Your program is responsible for allocating space for the array. It should be able to hold at least 10,000 integers. You can make the array global, local to main, or allocate it dynamically using one of the syscalls. Making it global is probably the easiest method (although not great programming practice). You will be responsible for following at least the basic calling convention we described in class. In particular, we expect you to follow the guidelines for parameter passing (first four arguments in $a0-$a3, the remainder on the stack), return value (return values are passed via $v0 and $v1), and register use (a callee may not use $s0-$s7 without saving them first, and restoring them afterwards). We'd also like you to follow the stack pointer guidelines presented in class.
You are writing everything from scratch (besides the routines we provide) this time. Of course, you'd probably be wise to start from some gutted version of your 378 machine solution. As always, clarity, simplicity and efficiency are valued, as are legible comments.
You are expected to include error checking on user inputs and corner cases, just as you would for any program. This is just good programming style and catches lots of bugs.
Quicksort and partition are not terribly complicated procedures, but because of the recursive nature of quicksort, debugging it can sometimes be a challenge. An hour of thinking about the design will be worth 10 hours of debugging! Good design and implementation techniques will make your life easier. So start small and work incrementally towards your solution (for instance, understanding, writing, and testing partition before worrying about quicksort seems a good tack to take). In all, you shouldn't find yourself writing more than a couple pages of code (excepting comments). And the usual words to the wise apply here: START NOW!
The turn-in for this assignment will be done through email here. It is very similar to assignment 3. Recall that your code will not be automatically checked in any way, so no errors will be found until we run it, after the due date. quicksort.s should include your main, quicksort, and partition procedures. Electronic submission is due before class Wednesday, March 23!