List-Printing Subroutine

The file qsort.s already defines one subroutine, qstep, which you can ignore for this section of the lab. It defines a .data section, which loads a long list of numbers into memory. The start and the end of the list are marked by labels list and listend. Note that the .data section is at the end of the file, after the .text section. Remember that the two sections can come in either order.

For this part of the lab, you should write a subroutine that prints a list of numbers. The start address and the end address of the list must be passed to the subroutine as arguments in $a0 and $a1. The subroutine should print the numbers one per line, with a line feed after each integer. The subroutine should save and restore the value of any register that it uses. You have already printed a list of numbers for Lab 5. The point of this exercise is simply to do the same task using a subroutine.

Test your subroutine by using it to print the list of numbers at the end of qstep.s.

Quicksort Subroutine

For the second section of the lab, you should add a second subroutine, named qsort, to qsort.s. The subroutine will implement the following Java method:

    static void qsort( int low, int high ) {
        if ( high <= low ) {
            return;
        }
        else {
            int middle = qstep( low, high );
            qsort( low, middle - 1 );
            qsort( middle + 1, high );
        }
    }

Note that this method uses qstep, a subroutine that is already defined in qsort.s. You do not have to write qstep! Note also that qsort calls itself. This is called recursion. However, the fact that qsort is recursive does not really make this exercise any harder than it would be otherwise.

You should also add code to the start of the file to call qsort with the parameters, low and high, set equal to the starting and ending address of the list of numbers at the end of the file.

The completed program should print the list of numbers sorted into order from low to high. The first subroutine, qsort sorts the list, and the second subroutine prints it.

(You don't need to understand how qsort and qstep work, but here is what qstep does. It rearranges a list of numbers so that: One of the numbers, called the "pivot", is somewhere in the list; all positions before the pivot's position hold numbers that are less than or equal to the pivot; and all positions after the pivot's position are greater than or equal to the pivot. The return value of qstep is the memory address of the pivot. So, qstep does a kind of partial sorting of the list, and qsort sorts the list entirely by applying qstep over and over on shorter and shorter lists.)