arrays – Bubble sort algorithm in MIPS

arrays – Bubble sort algorithm in MIPS

I just finished an assignment with the same objective; doing a bubble-sort on user input with the assumption that the user input is a string of ten characters that are letters. I commented the crap out of it so feel free to use as a reference. The assignment hasnt been graded yet, I just hope they wont think I cheated because they found this on the web.

####################################################################################################################################
#   Data
####################################################################################################################################
.data
prompt: .asciiz  nnEnter up to 10 characters:   # Prompt asking for user input
newLine: .asciiz n                               # Newline character
theString: .asciiz                                # A ten character string initially filled with whitespace

####################################################################################################################################
#   Text
####################################################################################################################################
.text 

################################################################################################################
#####   Procedure: Main
#####   Info:      Asks user for input, gets input, and then call 
#####              procedures to manipulate the input and output.
################################################################################################################
main:
    ############################################################
    #  Print Prompt
    ############################################################
    la $a0, prompt   # Load address of prompt from memory into $a0
    li $v0, 4        # Load Opcode: 4 (print string) 
    syscall          # Init syscall


    #############################################
    #  Read User Input into address of theString
    #############################################
    la $a0,theString  # Load address of theString into syscall argument a0
    li $a1,11         # Load sizeOfInput+1 into syscall argument a1
    li $v0,8          # Load Opcode: 8 (Read String)
    syscall

    ##############################
    #  Define total num of chars
    ##############################
    li $s7,10           # s7 upper index

    ##############################
    #  Call procedures 
    ##############################
    jal uppercase  
    jal sort
    jal print
    j exit
################################################################################################################
############################################# main END   #######################################################
################################################################################################################


################################################################################################################
#####   Procedure: uppercase
#####   Info:      Loops through the ten elements of chars gathered from 
#####              user input and if ascii is in range between 97  
#####              and 122, it will subtract 32 and store back
################################################################################################################
uppercase:

    la $s0, theString    # Load base address to theString into $t0
    add $t6,$zero,$zero  # Set index i = 0 ($t6)



    lupper:
        #####################################
        #  Check for sentinal val and if true
        #  branch to done to jump back to ra
        #####################################
        beq $t6,$s7,done 

        #####################################
        #  Load Array[i]
        #####################################
        add $s2,$s0,$t6 #
        lb  $t1,0($s2)

        #####################################
        #  if char is within lowercase 
        #  range.
        #####################################
        sgt  $t2,$t1,96
        slti $t3,$t1,123
        and $t3,$t2,$t3
        #####################################
        #  else, dont store byte
        #####################################
        beq $t3,$zero,isUpper
        addi $t1,$t1,-32
        sb   $t1, 0($s2)

        isUpper:
        #####################################
        #  increment and Jump back 
        #####################################
        addi $t6,$t6,1
        j lupper
################################################################################################################
############################################# uppercase END   ##################################################
################################################################################################################



################################################################################################################
#####   Procedure: sort
#####   Info:      Bubble sorts whatever is contained within 
#####              theString based on ascii values
################################################################################################################
sort:   
    ####################################
    #  Initialize incrementer for outer
    #  loop
    ####################################
    add $t0,$zero,$zero 

    ####################################
    #  Outer Loop
    #################################### 
    loop:
        #####################################
        #  Check for sentinal val and if true
        #  branch to done
        #####################################
        beq $t0,$s7,done

        ####################################
        #  Initialize upper bound of inner
        #  loop ( 10 - i - 1 ) 
        ####################################
        sub $t7,$s7,$t0
        addi $t7,$t7,-1

        ####################################
        #  Initialize incrementer for inner
        #  loop
        ####################################
        add $t1,$zero,$zero

        ####################################
        #  Inner Loop
        #################################### 
        jLoop:
            #####################################
            #  Check for sentinal val and if true
            #  branch to continue
            #####################################
            beq $t1,$t7,continue

            ####################################
            #  Load Array[i] and Array[i+1]
            ####################################
            add $t6,$s0,$t1
            lb  $s1,0($t6)
            lb  $s2,1($t6)

            #########################################
            #  If ascii(Array[i]) > ascii(Array[i+1])
            #  then swap and store
            #########################################
            sgt $t2, $s1,$s2
            #########################################
            #  Else,  dont swap and store
            #########################################
            beq $t2, $zero, good
            sb  $s2,0($t6)
            sb  $s1,1($t6)

            good:
            #########################################
            #  increment and Jump back 
            #########################################
            addi $t1,$t1,1
            j jLoop

        continue:
        #####################################
        #  increment and Jump back 
        #####################################
        addi $t0,$t0,1
        j loop
################################################################################################################
############################################# sort END   #######################################################
################################################################################################################




################################################################################################################
#####   Procedure: Print
#####   Info:      Prints whatever is stored inside theString
#####              
################################################################################################################
print:

    ####################################
    # Print a new line
    ####################################
    la $a0,newLine
    li $v0,4
    syscall 

    ####################################
    #  Initialize incrementer for loop
    ####################################
    add $t6,$zero,$zero # Set index i = 0 $t6

    lprint:
        #####################################
        #  Check for sentinal val and if true
        #  branch to done
        #####################################
        beq $t6,$s7,done  

        ####################################
        #  Load Array[i] into t1 and print
        ####################################
        add $t1,$s0,$t6 
        lb $a0, 0($t1)  # Load argument
        li $v0, 11      # Load opcode
        syscall         # Call syscall

        #########################################
        #  increment and Jump back 
        #########################################
        addi $t6,$t6,1  
        j lprint
################################################################################################################
############################################# print END   ######################################################
################################################################################################################


################################################################################################################    
#####  Procedure: done
#####       Info: Jumps to $ra. Only one procedure is needed to jump back to ra
################################################################################################################

done:
    jr $ra
exit:

line 30: You are moving step by step in your array and modifying your array pointer.

After the first and all subsequent forloops you need to reload the address of your array before executing forloop again otherwise it is pointing at the wrong place.

arrays – Bubble sort algorithm in MIPS

Here is a piece of code for Bubble sort in MIPS. Feed in 10 unsorted number and this will print back the sorted array. Hope this helps 🙂

.text
.globl main
main:
     la $t1,array
     li $s1,10

L1: beq $s1,$s2,L2
li $v0,5
syscall
sw $v0,0($t1)
addi $t1,$t1,4
addi $s2,$s2,1
j L1
li $s1,40
li $s2,0
li $s3,4

L2: beq $s1,$s2,printf
add $t1,$t1,$s2
lw $t0,0($t1)   #a[i]
L3: beq $s3,$s1,incc
add $t1,$t1,$s3
lw $t2,0($t1)   #a[j]
slt $t3,$t0,$t2
beq $t3,$0,swap
L4: addi $s3,$s3,4
j L3

swap:   
sw $t0,0($t1)
sub $t1,$t1,$s2
sw $t2,0($t1)
j L4

incc:
addi $s2,$s2,4
j L2


printf:
la $t1,array
li $t0,0
li $v0,4
la $a0,print
syscall
li $s2,0
li $s1,10
L5: beq $s1,$s2,out
li $v0,1
lw $t0,0($t1)
move $a0,$t0
syscall
li $v0,4
la $a0,space
syscall
addi $s2,$s2,1
addi $t1,$t1,4
j L5

out:
li $v0,10
syscall
.end

.data

array: .word 0,0,0,0,0,0,0,0,0,0
print: .asciiz nthe sorted array : 
space: .asciiz  

Leave a Reply

Your email address will not be published.