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:

  1. 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. ;-)

    ReplyDelete
  2. Anonymous23/1/09

    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.

    ReplyDelete
  3. Alessandro Casella26/5/09

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

    Can you help me? thanks

    ReplyDelete
  4. 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.

    ReplyDelete
  5. Alessandro Casella26/5/09

    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 :)

    ReplyDelete
  6. 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.

    ReplyDelete
  7. danica14/3/10

    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 :)

    ReplyDelete
  8. vagelis29/12/10

    se eyharistw poly!
    thanks a lot!

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

    ReplyDelete