Bubble sort algorithm in MIPS

45,354

Solution 1

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 hasn't been graded yet, I just hope they won't think I cheated because they found this on the web.

####################################################################################################################################
#   Data
####################################################################################################################################
.data
prompt: .asciiz  "\n\nEnter 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, don't 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,  don't 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:

Solution 2

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.

Solution 3

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 " "

Solution 4

Try this bubble sort. All lines have summarized comments. Works great on qtspim.

  .data
arr: .word 10, 60, 40, 70, 20, 30, 90, 100, 0, 80, 50
  space: .asciiz " "
  .text
  .globl main

main:
  lui $s0, 0x1001                   #arr[0]
  li $t0, 0                         #i = 0
  li $t1, 0                         #j = 0
  li $s1, 11                        #n = 11
  li $s2, 11                        #n-i for inner loop
  add $t2, $zero, $s0               #for iterating addr by i
  add $t3, $zero, $s0               #for iterating addr by j

  addi $s1, $s1, -1

outer_loop:
  li  $t1, 0                        #j = 0
  addi $s2, $s2, -1                 #decreasing size for inner_loop
  add $t3, $zero, $s0               #resetting addr itr j

  inner_loop:
    lw $s3, 0($t3)                  #arr[j]
    addi $t3, $t3, 4                #addr itr j += 4
    lw $s4, 0($t3)                  #arr[j+1]
    addi $t1, $t1, 1                #j++

    slt $t4, $s3, $s4               #set $t4 = 1 if $s3 < $s4
    bne $t4, $zero, cond
    swap:
      sw $s3, 0($t3)
      sw $s4, -4($t3)
      lw $s4, 0($t3)

    cond:
      bne $t1, $s2, inner_loop      #j != n-i

    addi $t0, $t0, 1                  #i++
  bne $t0, $s1, outer_loop           #i != n

  li $t0, 0
  addi $s1, $s1, 1
print_loop:
  li $v0, 1
  lw $a0, 0($t2)
  syscall
  li $v0, 4
  la $a0, space
  syscall

  addi $t2, $t2, 4                  #addr itr i += 4
  addi $t0, $t0, 1                  #i++
  bne $t0, $s1, print_loop          #i != n

exit:
  li $v0, 10
  syscall
Share:
45,354

Related videos on Youtube

Abdullah Alharbi
Author by

Abdullah Alharbi

Updated on April 03, 2021

Comments

  • Abdullah Alharbi
    Abdullah Alharbi almost 3 years

    I'm trying to write a procedure in assembly that sorts an array using bubble-sort algorithm but I'm having a problem which is:

    In line 22, when the first iteration executed nothing is wrong, program loads array[i+1] perfectly into registrar $a1 and if the swap condition is valid, program swaps without any problem. However, in the second iteration, program always loads 0 into $a1 whatever the real value of the element was! I tried debugging it but nothing was clear and I don't know what is the cause of this.

    1.  # Procedure:    bubbleSort
    2.  # Objective:    sort an array of integer elements in nondecreasing order
    3.  # Input:        an address of an array of integers
    4.  # Output:       an array sorted in nondecreasing order
    5. 
    6.  bubbleSort:
    7. 
    8.  move    $t0, $a0     # move address of the array into $t0
    9.  li      $s0, 1      # boolean swap = false.  0 --> false, 1 --> true
    10. li      $t1, 0      # j = 0;
    11. li      $t2, 0      # i = 0;
    12. li      $s1, 9      # array length
    13. loop:
    14.     beqz    $s0, exit       # exit if swap = false
    15.     li      $s0, 0          # swap = false;
    16.     addiu   $t1, $t1, 1  # j++;
    17.     move    $t2, $0      # i = 0;
    18.     subu    $s2, $s1, $t1  # s2 = length - j
    19.     forLoop:
    20.         bge     $t2, $s2, exitForLoop   # if i>=s2, exit
    21.         lw      $a0, 0($t0)         # a0 = array[i]
    22.         lw      $a1, 4($t0)         # a1 = array[i+1]
    23.         ble     $a0, $a1, update        # if array[i]<=array[i+1] skip
    24.         sw      $a1, 0($t0)         # a[i+1] = a[i]
    25.         sw      $a0, 4($t0)         # a[i] = a[i+1]
    26.         li      $s0, 1                 # swap = true;
    27.         update:
    28.         addiu   $t2, $t2, 1         # i++
    29.         sll     $t3, $t2, 2         # t3 = i*4
    30.         addu    $t0, $t0, $t3        # point to next element -->
    31.         j       forLoop
    32.     exitForLoop:
    33.         j   loop
    34. exit:
    35.     jr      $ra