In this task you will be writing a quick sort using MIPS. We will write some code for you, but you have to finish the most important part all by yourself. You can download the src here.
Quick sort can be "partitioned" into two parts:
algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo - 1
for j := lo to hi - 1 do
if A[j] < pivot then
i := i + 1
swap A[i] with A[j]
swap A[i + 1] with A[hi]
return i + 1
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p - 1 )
quicksort(A, p + 1, hi)
Source for the code above: Wikipedia
If you are not familiar with these two process, here are some help.
The code we wrote follows these two procedures too. Mind that you must fill two functions and you MUST NOT combine them or we WILL NOT grade your homework. We enforce this for a reason. One, it's good to get things separated and keep your mind cool; besides, you also need to practice save(and load) from(to) memory before calling a function.
You will get input from stdin. The first line will be an unsigned int n
specifying the length of the array. Followed by that line are n
lines of unsigned ints with potentially equal ones
You need to output to stdout. arranging all numbers in ONE LINE, with numbers seperated by ONE SPACE.
Luckly, we have implemented I/O details for you. However, you have to read the codes we write for you so that you know where are the numbers stored in the memory so that you can "address" them.