Thursday, May 21, 2020

Median of a sorted array in MIPS

This is a simple MIPS program that finds the median of a sorted array of integers. The code is fully explained and documented.

Launch EzMIPSthe MIPS assembler simulator, copy the following MIPS code and paste it into EzMIPS. Assemble, Run.

# --- Median of a sorted array of integer values of even length -- #
# ---------------------------------------------------------------- #

# median (for an even length array) = ( array[len/2] + array[len/2-1] ) / 2

# ----------------------- Data Declarations ---------------------- #
.data
array:  .word  1,  3,  5,  7,  9
        .word 11, 20, 25, 77, 89

length: .word 10
median: .word 0

# ------------------------- text/code section -------------------- #

.text

main:
    la $t0, array         # load starting address of the array into $t0
    lw $t1, length        # load the array length into $t1
    
    srl $t2, $t1, 1       # $t2 = length/2 = $t1/2 = $t1>>1 = 5

    # convert index into offset
    sll $t3, $t2, 2       # $t3 = $t2 * 4  = $t2<<2 = 20    
    
    # add base address of array to the offset
    add $t4, $t0, $t3     # $t4 = $t0 + $t3

    # get value of array[len/2]
    lw $t5, ($t4)         # $t5 = array[len/2]

    # address of previous value
    addi $t4, $t4, -4

    # get value of array[len/2-1]
    lw $t6, ($t4)         # $t6 = array[len/2-1]

    add $t7, $t6, $t5     # $t7 = array[len/2-1] + array[len/2]

    srl $t8, $t7, 1       # $t8 = $t7 /2 = $t7>>1
    sw $t8, median        # save median

    # .............................................................#

    # Done, terminate program
    li $v0, 10            # terminate
    syscall               # system call

# ---------------------------------------------------------------- #

Please let me know of any suggestions or bugs regarding the code above.

Regards,

Antonis

No comments:

Post a Comment