quick sort

////////////////////////////////////////////////////////////////////////////////
// Lab 6
////////////////////////////////////////////////////////////////////////////////

// Include the checkoff program:
.include "checkoff.uasm"

// Leave the following as zero to run ALL the test cases, and get your solution
//   validated if all pass.  If you have trouble with test case N, set it to N
//   to run JUST that test case (for easier debugging):
TestCase:       LONG(2)

// Quicksort-in-place code.  We include the C/Python version here as a comment;
// you can use this as a model for your Beta assembly version:

//def partition(array,left,right):
//    # choose middle element of array as pivot
//    pivotIndex = (left+right) >> 1;
//    pivotValue = array[pivotIndex]
//
//    # swap array[right] and array[pivotIndex]
//    # note that we already store array[pivotIndex] in pivotValue
//    array[pivotIndex] = array[right]
//
//    # elements <= the pivot are moved to the left (smaller indices)
//    storeIndex = left
//    for i in xrange(left,right):  # don't include array[right]
//        temp = array[i]
//        if temp <= pivotValue:
//            array[i] = array[storeIndex]
//            array[storeIndex] = temp
//            storeIndex += 1
//
//    # move pivot to its final place
//    array[right] = array[storeIndex]
//    array[storeIndex] = pivotValue;
//    return storeIndex;

partition:
        PUSH(LP)
        PUSH(BP)
        MOVE(SP, BP)

// Fill in your code here...
        p_index = R2
        p_value = R3
        p_array = R4
        p_left = R5
        p_right = R6
        p_i = R7
        store_index = R8
        temp = R9
        p_t = R10
		p_idx = R11

        PUSH(p_index)
        PUSH(p_value)
        PUSH(p_array)
        PUSH(p_left)
        PUSH(p_right)
        PUSH(p_i)
        PUSH(store_index)
        PUSH(temp)
        PUSH(p_t)
		PUSH(p_idx)

        LD(BP, -12, p_array)
        LD(BP, -16, p_left)
        LD(BP, -20, p_right)
 
        //.breakpoint
        ADD(p_left, p_right, p_t)
        SRAC(p_t, 1, p_index)
        MULC(p_left, 4, p_left)
        MULC(p_right, 4, p_right)
        MULC(p_index, 4, p_index)
        ADD(p_array, p_index, p_idx)
        LD(p_idx, 0, p_value)

        ADD(p_array, p_right, p_idx)
        LD(p_idx, 0, p_t)
        ADD(p_array, p_index, p_idx)
        ST(p_t, 0, p_idx)

        MOVE(p_left, store_index)
        MOVE(p_left, p_i)

_LOOP:
        ADD(p_array, p_i, p_idx)
        LD(p_idx, 0, temp)
        CMPLE(temp, p_value, p_t) // temp <= value t = 1
        BEQ(p_t, _ELSE)
        ADD(p_array, store_index, p_idx)
        LD(p_idx, 0, p_t)
        ADD(p_array, p_i, p_idx)
        ST(p_t, 0, p_idx)
        ADD(p_array, store_index, p_idx)
        ST(temp, 0, p_idx)
        ADDC(store_index, 4, store_index)
_ELSE:
        ADDC(p_i, 4, p_i)
        CMPLT(p_i, p_right, p_t) // i < right t = 1
        BNE(p_t, _LOOP)

        ADD(p_array, store_index, p_idx)
        LD(p_idx, 0, p_t)
        ADD(p_array, p_right, p_idx)
        ST(p_t, 0, p_idx)
        ADD(p_array, store_index, p_idx)
        ST(p_value, 0, p_idx)
        SRAC(store_index, 2, R0)

        POP(p_idx)
        POP(p_t)
        POP(temp)
        POP(store_index)
        POP(p_i)
        POP(p_right)
        POP(p_left)
        POP(p_array)
        POP(p_value)
        POP(p_index)

        MOVE(BP, SP)
        POP(BP)
        POP(LP)
        JMP(LP)


//def quicksort(array, left, right):
//    if left < right:
//        pivotIndex = partition(array,left,right)
//        quicksort(array,left,pivotIndex-1)
//        quicksort(array,pivotIndex+1,right)

// quicksort(ArrayBase, left, right)
quicksort:
        PUSH(LP)
        PUSH(BP)
        MOVE(SP, BP)

// Fill in your code here...
        q_array=R2
        q_left=R3
        q_right=R4
        q_pivot=R5
        q_t=R6
        
        PUSH(q_array)
        PUSH(q_left)
        PUSH(q_right)
        PUSH(q_pivot)
        PUSH(q_t)
        
        LD(BP, -12, q_array)
        LD(BP, -16, q_left)
        LD(BP, -20, q_right)
        CMPLE(q_right, q_left, q_t) // right <= left t=1
        BNE(q_t, EmptyArrayLoc)
        .breakpoint
        
        PUSH(q_right)
        PUSH(q_left)
        PUSH(q_array)
        BR(partition, LP)
        DEALLOCATE(3)
        MOVE(R0, q_pivot)
        
        SUBC(q_pivot, 1, q_t)
        PUSH(q_t)
        PUSH(q_left)
        PUSH(q_array)
        BR(quicksort, LP)
        DEALLOCATE(3)
        .breakpoint
        
        ADDC(q_pivot, 1, q_t)
        PUSH(q_right)
        PUSH(q_t)
        PUSH(q_array)
        BR(quicksort, LP)
        DEALLOCATE(3)
        .breakpoint
        
EmptyArrayLoc:
        POP(q_t)
        POP(q_pivot)
        POP(q_right)
        POP(q_left)
        POP(q_array)
        
        MOVE(BP, SP)
        POP(BP)
        POP(LP)
        JMP(LP)

// Allocate a stack: SP is initialized by checkoff code.
StackBasePtr:
        LONG(StackArea)

.unprotect

StackArea:
        STORAGE(1000)