CptS 260 Assignment 4

Assigned: Sept. 24, 2007
Due: Oct. 5, 2007, 11:59:59 PM

Turning in your assignment

When finished, submit your file named four.asm using the the Project turn-in link at the left side of the CptS 260 web pages. (Click the link and follow the directions.) You may turn in the assignment as many times as you like before the deadline. Only the last will be graded.

The problem: recursive quicksort of a list of numbers

For this problem you will write two functions plus a main routine to test them. The two functions are readnums and sort.

Function readnums takes two arguments: in $a0 the maximum number of numbers to read and in $a1 the address of a buffer to hold the numbers. readnums should assume that the buffer address is a multiple of 4. readnums repeatledly uses the sys instruction to read a number from the keyboard, stopping when either the buffer is full (the maximum number of items specified in $a0 have been placed in it), OR the number 0 is entered. When the number 0 is entered it is NOT placed in the buffer. readnums returns the number of entries it placed in the buffer in $v0. Be sure that readnums can handle the cases that $a0 is initially 0 and that the user enters 0 as the first number. In both cases it must return 0 in $v0. Properly designed code will NOT need to treat these two cases specially.

Function sort takes two arguments as well. For this function $a0 is the number entries (4-byte, two's complement numbers) in the buffer pointed to by $a1. sort rearranges the entries in the buffer so that they appear in increasing order. You are to implement sort using the recursive quicksort algorithm with in-place partitioning. If you don't remember this from CptS 122, look it up! You should test your code, at a minimum, on the following cases: $a0==0, $a0==1, input buffer already sorted in increasing order, input buffer sorted in decreasing order. (To save time in testing you may want to set up some buffers in the .data segment that contain your test cases so you don't have to repeatedly type in a lot of numbers.)

Your main function should contain calls to readnums and sort to thoroughly test them. We will look at your tests and also apply tests of our own to your readnums and sort functions. Make sure that you preserve all callee-save registers and that your functions do not write anything in the data segment outside the buffer provided as a parameter.

Design your code by writing high-level pseudo-code first. Include the pseudo-code as comments at the heads of the functions in your program file. Of course, also include comments on the assembler code itself. The hardest part of this assignment is the in-place partioning step (and even that is not too bad). Don't try to be fancy in your choice of pivot elements -- using the first array element is perfectly acceptable in this assignment even though it is not ideal in practice.