sorting array in mips (assembly)

Question

im in a class learning assembly using mips. I am working on sorting an array of numbers and i think that I have the method working correctly, but just a bit of trouble. I do not know how to check when im sorted fully. Im using a pretty rudimentary method for sorting, but that is all that we have learned thus far. Also, i do not know how to output the numbers to check to see if it is sorted. Im used to Java and such so assembly is kinda throwing me for a spin. Here is my code thus far:

    .text
    .globl main
main:       la  $a0, Array             # sets the base address of the array to $a0
loop:       lw  $t0, 0($a0)             # sets $t0 to the current element in array
            lw  $t1, 4($a0)         # sets $t1 to the next element in array
            blt $t1, $t0, swap      # if the following value is greater, swap them
            addi    $a0, $a0, 4     # advance the array to start at the next location from last time
            j   loop                  # jump back to loop so we can compare next two elements

swap:       sw  $t0, 4($a0)         # store the greater numbers contents in the higher position in array (swap)
            sw  $t1, 0($a0)         # store the lesser numbers contents in the lower position in array (swap)
            li  $a0, 0                 # resets the value of $a0 back to zero so we can start from beginning of array
            j   loop                  # jump back to the loop so we can go through and find next swap

            .data

Array:      .word   14, 12, 13, 5, 9, 11, 3, 6, 7, 10, 2, 4, 8, 1 

thanks for any help guys!

Answer 1

Coding direct in assembly is a pain. What I do instead is start with an algorithm (psuedocode or actual code) then translate systematically, as if I am a compiler. I will ignore the input and output stuff and focus on a function that sorts.

You would call in a high-level lanaguage like C as:

insertionsort(data, N);

where data is an integer array and N the number of elements (there are no size attributes at machine level).

Since the function calls nothing, it needs no stack frame. Observe the standard MIPS conventions of using $t registers so you are not trashing anything anyone else relies on and pass in parameters in $a0 and $a1 in that order.

Step 1: get an algorithm. Here’s one from [Wikipedia][1] for insertion sort:

i ← 1
while i < length(A)
    x ← A[i]
    j ← i - 1
    while j >= 0 and A[j] > x
        A[j+1] ← A[j]
        j ← j - 1
    end while
    A[j+1] ← x
    i ← i + 1
end while

Step 2: paste into a text file, turn all lines into comments and systematically convert to assembly. I use templates for things like loops that take the guess work out of coding (see my free book for examples). I will just give the finished product here; to call it, you need to put the start address of the array into $a0 and its size in $a1, then jal insertionsort:

# algorithm for insertion sort
# from https://en.wikipedia.org/wiki/Insertion_sort
# usage: insertionsort (a,N)
# pass array start in $a0, size in elements, N in $a1
# Philip Machanick
# 30 April 2018

            .globl insertionsort

            .text

# leaf function, no stack frame needed
# Registers:
#   $a0: base address; $a1: N
#   $t0: i
#   $t1: j
#   $t2: value of A[i] or A[j]
#   $t3: value of x (current A[i])
#   $t4: current offset of A[i] or A[j] as needed
insertionsort:
# i ← 1
       li $t0, 1
# while i < N
       j Wnext001        # test before 1st iteration
Wbody001:                # body of loop here
      sll $t4, $t0, 2    # scale index i to offset
      add $t4, $a0, $t4  # address of a[i]
#     x ← A[i]
      lw $t3, 0($t4)
#     j ← i - 1
      addi $t1, $t0, -1
#     while j >= 0 and A[j] > x
       j Wnext002        # test before 1st iteration
Wbody002:                # body of loop here
#         A[j+1] ← A[j]
          sll  $t4, $t1, 2        # scale index j to offset
          add $t4, $a0, $t4       # address of a[j]
          lw $t2, 0($t4)          # get value of A[j]
          addi $t4, $t4, 4        # offset of A[j+1]
          sw $t2, 0($t4)          # assign to A[j+1]
#         j ← j - 1
          addi $t1, $t1, -1
#     end while
Wnext002: # construct condition, j >= 0 and A[j] > x
          blt $t1, $zero Wdone002 # convert to: if j < 0 break from loop #####
          sll  $t4, $t1, 2        # scale index j to offset
          add $t4, $a0, $t4       # address of a[j]
          lw $t2, 0($t4)          # A[j]
          bgt $t2, $t3, Wbody002  # no need to test j >= 0, broke from loop already if false
Wdone002:                         # branch here to short-circuit and
#     A[j+1] ← x
          add  $t4, $t1, 1        # scale index j+1 to offset
          sll  $t4, $t4, 2        # scale index j to offset
          add $t4, $a0, $t4       # address of a[j+1]
          sw $t3, 0($t4)          # A[j+1] becomes x
#     i ← i + 1
          addi $t0, $t0, 1
# end while
Wnext001: blt $t0,$a1, Wbody001  # i < N easy this time
          jr $ra                 # return to caller

Longer than the other examples – but if you start from an algorithm and translate you are less likely to go wrong. This can go in a separate file if your assembler respects the .globl directive, which makes the name visible in other files.

[1]: https://en.wikipedia.org/wiki/Insertion_sort – actually from Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 2.1: Insertion sort". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 15–21

Answer 2

.data

value: .word 0x3

Array: .word 0x14, 0x12, 0x13, 0x05

.text

.globl main

main: la $a0, Array

   lw  $t3,value  

l1: lw $t0, 0($a0)

   lw  $t1, 4($a0)     

   blt $t1, $t0, swap   

   addi    $a0, $a0, 4

   addi $t3,$t3,-1     

   bne  $t3,$zero,l1

   jr $ra

swap: sw $t0, 4($a0)

    sw  $t1, 0($a0)    

    j   l1

Answer 3

This link explains how to print to the screen in a MIPS simulator like QTSPIM or MARS.

As for the code, there were a few bugs. The line li $a0, 0 is overwriting the work done by the initial la $a0, Array instruction because the li is setting the base address of your array to 0. Instead, you should move the la instruction into the loop so that $a0 is properly reset to the base address of Array after iterating over the entire array, and remove the li instruction. You also will need to add in a condition for when your program has completed the sort. I would suggest the following revisions (tested with SPIM):

main:
    la  $t0, Array      # Copy the base address of your array into $t1
    add $t0, $t0, 40    # 4 bytes per int * 10 ints = 40 bytes                              
outterLoop:             # Used to determine when we are done iterating over the Array
    add $t1, $0, $0     # $t1 holds a flag to determine when the list is sorted
    la  $a0, Array      # Set $a0 to the base address of the Array
innerLoop:                  # The inner loop will iterate over the Array checking if a swap is needed
    lw  $t2, 0($a0)         # sets $t0 to the current element in array
    lw  $t3, 4($a0)         # sets $t1 to the next element in array
    slt $t5, $t2, $t3       # $t5 = 1 if $t0 < $t1
    beq $t5, $0, continue   # if $t5 = 1, then swap them
    add $t1, $0, 1          # if we need to swap, we need to check the list again
    sw  $t2, 4($a0)         # store the greater numbers contents in the higher position in array (swap)
    sw  $t3, 0($a0)         # store the lesser numbers contents in the lower position in array (swap)
continue:
    addi $a0, $a0, 4            # advance the array to start at the next location from last time
    bne  $a0, $t0, innerLoop    # If $a0 != the end of Array, jump back to innerLoop
    bne  $t1, $0, outterLoop    # $t1 = 1, another pass is needed, jump back to outterLoop

Be sure to check out this link for additional examples and explanations on what each MIPS instruction does.