Quick Sort

Instructions

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:

• Partition. Each time you get hand on an array, try to partition them based on a pivot at your disposal.

  
  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 

• Quick sort. With an array partitioned into two parts, apply quick sort on each one of them.

  
  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.

Consider Learning Before You Start

• Recursive functions
• Save and Load from Memory using MIPS
• Patience!
• Usually it is quite helpful to write the according C code first and then translate it into MIPS.
• Use the comments to note what the line is actually doing in C.

I/O

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.

Heads Ups

• Register Rule #1. You are offered with limited registers: $zero, $at, $v0, $a0 - $a3, $t0 - $t3, $s0 - $s3, $sp, and $ra. We banned some t registers to keep your minds sharp or you might get drowned in a sea of registers.
• Register Rule #2. Do understand and employ the registers' convention which is another way to keep you from feeling dizzy. If you are not sure about them, here we listed them below:
  • Use $zero instead of $0;
  • use $v0 for system call;
  • use $s0 - $s3 as saved value;
  • use $a0 - $a3 as function parameters;
  • use $t0 - $t3 as temporary registers;
  • you can't mess up with $ra, $sp, etc. anyway :)
• Comment Rule. You need to have MEANINGFUL comments not less than 50% of the total lines of code you wrote. A comment is defined by a sentence followed by a comment symbol(aka. #)
• IMPORTANT! Failure to comply to the Register Rules(rule #1 and #2) will cost you at least 30% of scores of this homework. 50% of this homework's total scores will also be deducted if you can't write enough meaningful comments according to comment rule.

Submission