# CS 110 Spring 2019 hw3
# quick_sort.s

#========================================================================================
#                              Quick Sort RISC-V
#                                   README
#========================================================================================
# In this file you will be implementing the def_quick_sort and def_partition 
# function, which form the most important part of this code.
#
# You should sort a 10-integer array. These arrays was reserved in static
# partition of memory. You can change to any 10 numbers you want to sort for
# testing and we will change them to our test case for grading.
# 
# We give you the choice to test your code using predefined array: in line 41.
# You can decomment it and use array to test your code.
# 
# 
#                               IMPORTANT!!!
# Our asembler will support the following registers:
# 
# zero, ra, sp, a0 - a1, a2-a4, t3-t6 and s2-s5
# The name x0 can be used in lieu of zero. Other register numbers 
# (eg. x1, x2, etc.) are not supported.
# 
# We will manually check whether you use registers properly after the ddl.
# So the grade on your autolab is not the final grade of your homework.
#======================================================================================

.data
    space:                  .asciiz  " "                # a space string.
    line:                   .asciiz "\n"                # a newline string.
    colonsp:                .asciiz ": "                # a colon string with space.
    .align                  2                           # make data aligned in word
    size:                   .word  10                   # the size of the array                           
    inputstring:            .asciiz "List need sort: "  # the origin array
    sorted_array_string:    .asciiz "Sorted:         "  # the output array
    
#=================================================     Reserved Array     ===========================================|
    array:          .word 0 0 0 0 0 0 0 0 0 0           # array to be sorted                                        |
    #array:           .word 678 567 456 765 876 987 543 654 684 374 # use this line if you want to test this array    |
#====================================================================================================================|                                 

.text
.globl  main
main:
    j receive_values_end           # print the testing array            

    receive_values_end:
        li    a0, 4                # 4 = print_string ecall.
        la    a1, inputstring        
        ecall
        la    a1, array
        jal   print                # print user input values

    # Set up the main quick_sort call.
    # Arrays are    
    la       a1, array             # a1 adrs of the array
    li       a2, 0                 # left val
    lw       a3, size              # right val
    addi     a3, a3, -1            # make a3 the higher index
    jal      def_quick_sort  
    
    li       a0, 4                 # 4 = print_string ecall.
    la       a1, sorted_array_string   
    ecall
    la       a1, array
    jal      print                  # print out the sorted list

    j        exit


########################################################
####################your code here######################
########################################################

# In this part you will implemente quick sort and partition seperately.
# You should learn how to use stack and function call before implemente.
# WARNING: using registers properly or you will get 30% deduction after ddl.
#      50% meaningful comments is needed or you will get 50% deduction after ddl.


def_quick_sort:
    # your code


def_partition:
    # your code
    

# programs ends
# 
exit:
    # your code
    ecall                     # system call


###       Printing array
print:
    print_loop_prep:
        mv      t3, a1
        lw      t4, size
        li      t5, 0
    print_loop:
        # your code
    print_end:
        li      a0, 4
        la      a1, line
        ecall
        jr      ra

########################################################
####################End of your code####################
########################################################