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. 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.
# 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 non-decreasing order. # By default, arrays of length 1 are "sorted." The "sortedness" of # non-positive length arrays is unspecified.These routines are automatically loaded in by spim. DO NOT load another file that has these routines. If, for your own edification, you would like to look at the code for these routines, they can be found in /cse/courses/cse378/CurrentQtr/lib/hw4lib.spim. DO NOT load this file into spim.
For those of you using PCSpim at home, what we have done is insert the code of hw4lib.spim into trap.handler, which is spim loads automatically. This is located in the course lib/ directory, i.e. /cse/courses/cse378/CurrentQtr/lib/. You can take a copy of trap.handler home with you, put that in the appropriate place in your PCSpim install, and everything should work. Note that if we update trap.handler (with bug fixes for example), you are responsible for updating any home copy you have. trap.handler will be more up-to-date than hw4lib.spim. Talk to the instructor or the TA if you have any questions or problems.
You are writing everything from scratch (besides the routines we provide) this time. Of course, you'd have to be nuts not to start from some gutted version of you HW2 or HW3 solution. As always, clarity, simplicity, efficiency (i.e., code beauty) is valued, as are legible comments.
Quicksort and partition are not terribly complicated procedures, but because of the recursive nature of quicksort, debugging it can be a real pain. An hour of thinking about the design will be worth 10 hours of debugging! In all, you shouldn't find yourself writing more than a couple pages of code (excepting comments). As always, good design/implementation technique will make your life easier. Start small and work incrementally towards solution (for instance, understanding, writing, testing partition before worrying about quicksort seems logical, but you knew that already). We won't have much pity on the folks who use the "It's the day before the assignment is due and I just wrote 3 pages of assembly code and nothing works and I don't know what's wrong and I don't know where to start debbugging and will you please help me please please ..." approach.