3/3/08

MIPS Bubble sort

Here is an implementation of the well known bubble sort algorithm. Reads six integer from user, saves them in a table and the sorts them. It is in MIPS assembly language which you can test using a MIPS simulator. I suggest SPIM which can be found at http://pages.cs.wisc.edu/~larus/spim.html and is free. SPIM works on windows too.

This the code of bubble sort. You just copy and paste in a file and run it using SPIM.

#########################################################
###### BUBBLE SORT ###
#########################################################
.data
.align 4
Table: .space 24
msg1: .asciiz "Please insert an integer: "
msg2: .asciiz " "
msg3: .asciiz "\nVector contents: "
.text
.globl main
main:

addi $s0,$zero,5
addi $t0,$zero,0
in:
li $v0,4
la $a0,msg1
syscall
li $v0,5
syscall
add $t1,$t0,$zero
sll $t1,$t0,2
add $t3,$v0,$zero
sw $t3,Table ( $t1 )
addi $t0,$t0,1
slt $t1,$s0,$t0
beq $t1,$zero,in

la $a0,Table
addi $a1,$s0,1 #a1=6
#call buble_sort
jal buble_sort

#print table
li $v0,4
la $a0,msg3
syscall
la $t0,Table
#s0=5
add $t1,$zero,$zero
printtable:
lw $a0,0($t0)
li $v0,1
syscall
li $v0,4
la $a0,msg2
syscall
addi $t0,$t0,4
addi $t1,$t1,1
slt $t2,$s0,$t1
beq $t2,$zero,printtable

li $v0,10
syscall

buble_sort:
#a0=address of table
#a1=sizeof table
add $t0,$zero,$zero #counter1( i )=0

loop1:
addi $t0,$t0,1 #i++
bgt $t0,$a1,endloop1 #if t0 < a1 break;

add $t1,$a1,$zero #counter2=size=6
loop2:

bge $t0,$t1,loop1 #j < = i

#slt $t3,$t1,$t0
#bne $t3,$zero,loop1

addi $t1,$t1,-1 #j--

mul $t4,$t1,4 #t4+a0=table[j]
addi $t3,$t4,-4 #t3+a0=table[j-1]
add $t7,$t4,$a0 #t7=table[j]
add $t8,$t3,$a0 #t8=table[j-1]
lw $t5,0($t7)
lw $t6,0($t8)

bgt $t5,$t6,loop2

#switch t5,t6
sw $t5,0($t8)
sw $t6,0($t7)
j loop2

endloop1:
jr $ra
##########################################################
###### BUBBLE SORT END ###
##########################################################


Maybe you would like to see simple MIPS counter.

9 comments:

Matech said...

Hi, thanks again for your code, it's very well done! I got your email reply...in the meantime I've been working on 2 different versions of the code, one with characters and the other with floating point numbers. But I still have some problems...mainly this is what I did:
for the char I used
addi $a1,$zero,2
li $v0,8
in order to insert a single char without pressing enter and then it sorts ok but the output is still in integer format (int corresponding value of the hex ASCII char code) while if I output with
li $v0,4 (as string)
it gives the following
(null)
i think it's something "string related"...but don't know how to figure it out... do you have any ideas?
Thanks!!

PS: as soon as i finish a bit of the floating point version i'll post that too...and when it works I can post the full code if you like. ;-)

Anonymous said...

Hi,
Thank you very much for your comments.
I believe my post about how to Reverse a string - MIPS will be helpful for you.
Thank you for visiting.

Alessandro Casella said...

hi, i 'm trying to print the vector after every cycle of bubble sort... without success...

Can you help me? thanks

Another Computers Blog said...

First of all thank you for visiting and reading my blog.

To print table on every loop you should make a function printtable or something

the code is from the comment
#print table to the line above li $v0,10

make this a function (copy paste the code, give a label
(e.g. printmytable) and add jr $ra at the end
Now in bubble sort code add jal printmytable in every loop
(after loop1: or loop2: depends on what you want)

I hope this will help you.

Thank you again.

Alessandro Casella said...

I've solved =)

.data
.align 4
Table: .space 24
msg1: .asciiz "Insert integer value : "
msg2: .asciiz " "
msg3: .asciiz "\nTable values: "
msg4: .asciiz "\nOrdered Table values: "
.text
.globl main
main:
li $t9,4
addi $s0,$zero,5
addi $t0,$zero,0
in:
li $v0,4
la $a0,msg1
syscall
li $v0,5
syscall
add $t1,$t0,$zero
sll $t1,$t0,2
add $t3,$v0,$zero
sw $t3,Table ( $t1 )
addi $t0,$t0,1
slt $t1,$s0,$t0
beq $t1,$zero,in

la $a2,Table
addi $a3,$s0,1
#richiama bubble_sort
jal buble_sort
fine:
li $v0,4
la $a0,msg4
syscall
la $t0,Table
add $t1,$zero,$zero
printtable:
lw $a0,0($t0)
li $v0,1
syscall
li $v0,4
la $a0,msg2
syscall
addi $t0,$t0,4
addi $t1,$t1,1
slt $t2,$s0,$t1
beq $t2,$zero,printtable

li $v0,10
syscall

buble_sort:
add $t0,$zero,$zero

loop1:
jal printmytable
addi $t0,$t0,1

bgt $t0,$a3,endloop1 #se t0 < a1

add $t1,$a3,$zer
loop2:

bge $t0,$t1,loop1 #j < = i

#slt $t3,$t1,$t0
#bne $t3,$zero,loop1

addi $t1,$t1,-1

mul $t4,$t1,$t9 #t4+a0=table[j]
addi $t3,$t4,-4 #t3+a0=table[j-1]
add $t7,$t4,$a2 #t7=table[j]
add $t8,$t3,$a2 #t8=table[j-1]
lw $t5,0($t7)
lw $t6,0($t8)

bgt $t5,$t6,loop2

#switch t5,t6
sw $t5,0($t8)
sw $t6,0($t7)
j loop2

endloop1:
jr $ra

printmytable
li $v0,4
la $a0,msg3
syscall
la $s2,Table
#s0=5
add $s3,$zero,$zero
printtable2:
lw $a0,0($s2)
li $v0,1
syscall
li $v0,4
la $a0,msg2
syscall
addi $s2,$s2,4
addi $s3,$s3,1
slt $s4,$s0,$s3
beq $s4,$zero,printtable2
jr $ra


Thanks a lot =)
...
if this can be useful for someone I'm very happy for your fantastic blog.

Greetings :)

Another Computers Blog said...

Very good. :-)
I'm glad I helped you.

Thank you for the code Alessandro,
I haven't try it but with a first look it seems ok.

Thank you for sharing it.
Happy to see you again around.

danica said...

thanks for the code. but how can this be done using floats as inputs? how can i store them in an array/stack then sort them? thanks :)

vagelis said...

se eyharistw poly!
thanks a lot!

Unknown said...

if i want to sort them from the max value to the minimum value how can i do it?