Bubble sort algorithm in MIPS
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
Related videos on Youtube
Abdullah Alharbi
Updated on April 03, 2021Comments
-
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 loadsarray[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 loads0
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