Bubble Sorting using MIPS

Question

I have made the inner loop which is doing comparison and swapping but i am having a difficulty in implementing outer loop which will run according to the number of elements.

.data
Arr: .word 5, 4, 3, 2, 1

.text
.globl main 
 main:
 la   $a0, Arr      # Pass the base address of the array Arr to input   argument register $a0
addi $a1, $zero, 5 # initialze the value of sorting loop ($al=5)
li   $t1, 0        # initialize the value of outer loop (t1=0)


sort:
lw  $s1, 0($a0)     # Load first element in s1 
lw  $s2, 4($a0)     # Load second element in s2
bgt $s1, $s2, swap  # if (s1 > s2) go to swap


sorting_loop:
addiu $a0, $a0, 4  # move pointer to next element
subiu $a1, $a1, 1  # decrement the value of inner loop ($a1)
bgtz  $a1, sort    # loop till value of inner loop is not equal to zero

j end              

swap:
sw   $s1, 4($a0) # put value of [i+1] in s1
sw   $s2, 0($a0) # put value of [i] in s2
j    sorting_loop

end: # End the program
li $v0, 10
syscall

Answer 1

Your inner pass looked pretty good, but [I think] it was going one past the end with the 4($a0) (e.g. for an array of 5, the loop count must be 4). I've fixed that.

I've added the outer loop. Please excuse the gratuitous style cleanup, but it's how I could understand your logic before adding to it. I renamed some of your labels so they would make more sense to me.

When I added the outer loop, I converted your inner one into a function called by the outer loop [seemed cleaner that way].

I added two optimizations: decrementing the pass count and the "early escape" flag [if a given pass makes no swaps].

I've also added a number of annotations. The code may not be perfect, but I think it will help get you closer.

# bubble sort

    .data
Arr:        .word       5,4,3,2,1

    .text
    .globl  main
main:
    li      $t1,5                   # get total number of array elements

# main_loop -- do multiple passes through array
main_loop:
    subi    $a1,$t1,1               # get count for this pass (must be one less)
    blez    $a1,main_done           # are we done? if yes, fly

    la      $a0,Arr                 # get address of array
    li      $t2,0                   # clear the "did swap" flag

    jal     pass_loop               # do a single sort pass

    # NOTES:
    # (1) if we make no swaps on a given pass, everything is in sort and we
    #     can stop
    # (2) after a pass the last element is now highest, so there is no need
    #     to compare it again
    # (3) a standard optimization is that each subsequent pass shortens the
    #     pass count by 1
    # (4) by bumping down the outer loop count here, this serves both _us_ and
    #     the single pass routine [with a single register]

    beqz    $t2,main_done           # if no swaps on current pass, we are done

    subi    $t1,$t1,1               # bump down number of remaining passes
    b       main_loop

# everything is sorted
# do whatever with the sorted data ...
main_done:
    j       end                     # terminate program

# pass_loop -- do single pass through array
#   a0 -- address of array
#   a1 -- number of loops to perform (must be one less than array size because
#         of the 4($a0) below)
pass_loop:
    lw      $s1,0($a0)              # Load first element in s1
    lw      $s2,4($a0)              # Load second element in s2
    bgt     $s1,$s2,pass_swap       # if (s1 > s2) swap elements

pass_next:
    addiu   $a0,$a0,4               # move pointer to next element
    subiu   $a1,$a1,1               # decrement number of loops remaining
    bgtz    $a1,pass_loop           # swap pass done? if no, loop
    jr      $ra                     # yes, return

pass_swap:
    sw      $s1,4($a0)              # put value of [i+1] in s1
    sw      $s2,0($a0)              # put value of [i] in s2
    li      $t2,1                   # tell main loop that we did a swap
    j       pass_next

# End the program
end:
    li      $v0,10
    syscall