Quick Sort

Instructions

In this task you will be writing a quick sort using RISC-V. We have written 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 RISC-V
• Patience!
• Usually it is quite helpful to write the according C code first and then translate it into RISC-V.
• Use the comments to note what the line is actually doing in C.

What you should do

• You should take your algorithm on a array which contains 10 integers. The array has been allocated space on static partition in line 40. You can change that array to whatever you like but DO NOT change the line number of it and anything else around them.

• Function def_quick_sort is the quick sort function, you can write your implementation here. And in this function, you should use another function def_partition.

• In function def_partition, you should separate a list into two partition. You can choose whatever method you like for detailed implementation.

• After label exit, you should set correct parameter to the environment call, which allows exit the program with exit code 0. For more ecall information, see here.

• Finally, finish the auxiliary function print. You should print an array form the begin (its address in a1) to the end. Two numbers will be separated by space. e.g.:

  • List need sort: 678 567 456 765 876 987 543 654 684 374
  • Sorted: 374 456 543 567 654 678 684 765 876 987

• You should not change anything others.

Heads Ups

• Register Rule #1. You are offered with limited registers: zero,ra, sp, a0 - a1, a2 - a4, t3 - t6, s2 - s5. 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 x0;
  • use a0 for system call;
  • use s2 - s5 as saved value;
  • use a0 - a4 as function parameters;
  • use t3 - t6 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