Homework 9 Computer Organization Due April 22 2011 F by 3 PM Translate the following quick sort algorithm to MIPS assembly language YOU ARE TO USE THE MIPS CALLING CONVENTIONS WHEN IMPLEMENTING THE QUICK SORT PARTITION AND SWAP SUBPROGRAMS Use the data below when you run your program array length data word 20 30 10 40 50 60 30 25 10 5 word 10 text globl start start li v0 10 syscall system code for exit main start label above begin quickSort array 0 length 1 end main quickSort start address of integer array integer low high local variable integer pivotPosition begin if low high then pivotPosition partition array low high quickSort array low pivotPosition 1 quickSort array pivotPosition 1 high end if end quickSort swap should exchange the values at the addresses passed it swap address of integer operand1 address of integer operand2 local variable integer temp begin temp operand1 operand1 operand2 operand2 temp end swap function partition start address of integer array integer start end returns an integer local variables integer pivotValue pivotPosition mid scan mid start end 2 swap array start array mid pivotPosition start pivotValue array start for scan start 1 to end do if array scan pivotValue then pivotPosition pivotPosition 1 swap array pivotPosition array scan end if end for swap array start array pivotPosition return pivotPosition end partition EXTRA CREDIT 1 Use the PCSpin I O system calls described on page 7 of the MIPS Guide to allow the user to interactively enter the elements to be sorted and then display the sorted results 2 Rewrite your bubble sort program using the technique of walking pointers to reduce the amount of array address calculations i e use the regular access pattern in the array to update the register containing the address of numbers test to the correct spot in memory NOTE You can download the MIPS simulator at http sourceforge net projects spimsimulator files TURN IN a print out of the program e g hw9 s This file is generated in any text editor e g WordPad or MARS editor a window capture of the PCSpim or MARS simulator after running your assembly language program so it shows the above array values sorted You can capture this window by 1 right clicking anywhere in the window to make it the currently active window 2 while holding down the Alt key press the PrtScn key to capture the window the Window s clipboard and 3 open some word processor Word Open Office etc and paste the image into the document Add your name to this document before printing it