2013-03-26 08:41:00Morris
[MIPS] 泡泡排序 Bubble Sort
題目內容： Bubble sort and Finding median
首先宣告一個 11 個 word 大小的記憶體區段做為 array 使用
.data
array: .word 0,0,0,0,0,0,0,0,0,0,0
size: .word 11
其中 array 中有 11 個零，代表 array 中 11 個變數的初始值；
而 size 代表 array 中有幾個變數。
之後 array 中的 11 個數字須由 使用者輸入，輸入完 11 個數字後，在 console 中印出 bubble sort 後的結果(由小排到大)，以及 11 個數字的中位數
泡泡排序的 C/C++ 片段 (sort function 的原版)
i = n-1;
while(i >= 0) {
j = 0;
for(j = 0; j < i; j++) {
if(array[j] < array[j+1])
goto end;
swap(array[j], array[j+1]);
end:;
}
i--;
}
輸出格式的 C/C++ 片段 (Outputi 的原版)
for(i = 0; i < 11; i++) {
if(i == 0)
goto notdot;
putchar(',');
notdot:
printf("%d", array[i]);
}
puts("");
#Write Bubble Sort by MIPS instruction
#read 11 numbers to sort(small to larger)
.text
.globl main
main: #start process
addi $sp, $sp, -12
sw $ra, 0($sp)
sw $s0, 4($sp)
sw $s1, 8($sp)
move $s0, $zero # i = 0
li $t0, 0 # j = 0
la $t1, array # load $t1 = &array
lw $t2, size # load $t2 = size
inputi: #start readinput
li $v0, 5 # $v0 function result, call readInt
syscall # ReadInt(& $v0)
add $t3, $t0, $t1 # $t3 = array + $t0 (array+j)
sw $v0, 0($t3) # array+t3 = v0
addi $t0, $t0, 4 # 4 bytes(word)
addi $s0, $s0, 1 # i = i+1
bne $s0, $t2, inputi
#end readinput
la $a0, array
lw $a1, size
jal sort
#start output
move $s0, $zero # i = 0
li $t0, 0 # j = 0
la $t1, array # load $t1 = &array
lw $t2, size # load $t2 = size
li $v0, 4 # printString("Sorting ...")
la $a0, resmsg
syscall
outputi:
beq $s0, $zero, notprintdot
li $v0, 4 # printString(",")
la $a0, dotmsg
syscall
notprintdot:
li $v0, 1 # $v0 function result, call printInt
add $t3, $t0, $t1 # $t2 = array + $t0
lw $a0, 0($t3) # printInt($a0)
syscall
addi $t0, $t0, 4 # j += 4, 4 bytes(word)
addi $s0, $s0, 1 # i = i+1
bne $s0, $t2, outputi
# outputi loop end
li $v0, 4 # printString("\n")
la $a0, nl
syscall
li $v0, 4 # printString("Median:")
la $a0, midmsg
syscall
lw $t0, size # $t0 = size
la $t1, array # $t1 = &array
srl $t0, $t0, 1 # $t0 = size>>1 (index)
sll $t0, $t0, 2 # $t0 = $t0 * 4 (array+t0)
add $t0, $t0, $t1 # $t0 = array+t0
li $v0, 1 # printInt($a0)
lw $a0, 0($t0) # $a0 = mem[0($t0)]
syscall
#end output
lw $s1, 8($sp)
lw $s0, 4($sp)
lw $ra, 0($sp)
addi $sp, $sp, 12
jr $ra
#end process
#function sort(array, n) => ($a0, $a1) begin
sort: addi $sp, $sp, -20 # make room on stack for 5 registers
sw $ra, 16($sp)
sw $s3, 12($sp)
sw $s2, 8($sp)
sw $s1, 4($sp)
sw $s0, 0($sp)
move $s2, $a0 # $s2 = &array
move $s3, $a1 # $s3 = n(array_size)
move $s0, $s3 # $s0 = i = n
addi $s0, $s0, -1 # $s0 = n-1
for1tst:
slt $t0, $s0, $zero # while(i >= 0)
bne $t0, $zero, exit1# t0 = 1, i < 0
move $s1, $zero # $s1 = j = 0
for2tst:
slt $t0, $s1, $s0 # while(j < i)
beq $t0, $zero, exit2# t0 = 0, j >= i
sll $t1, $s1, 2 # $t1 = 4 * j
add $t2, $s2, $t1 # $t2 = &array[j] = $s2 + 4*j
lw $t3, 0($t2) # $t3 = array[j]
lw $t4, 4($t2) # $t4 = array[j+1]
slt $t0, $t3, $t4 # if(array[j] > array[j+1]) swap()
bne $t0, $zero, for2end# t0 = 1, array[j] < array[j+1]
move $a0, $s2 # call swap(array, j)
move $a1, $s1
jal swap
for2end:
addi $s1, $s1, 1 # j++
j for2tst
exit2:
addi $s0, $s0, -1 # i--
j for1tst
exit1:
lw $s0, 0($sp)
lw $s1, 4($sp)
lw $s2, 8($sp)
lw $s3, 12($sp)
lw $ra, 16($sp)
addi $sp, $sp, 20
jr $ra # return to call routine
#function sort(array, n) end
#function swap(array, j) => ($a0, $a1)begin // swap(array[j], array[j+1])
swap:
sll $t1, $a1, 2 # $t1 = j*4
add $t1, $a0, $t1 # $t1 = &array[j] = $a0 + j*4
lw $t0, 0($t1) # $t0 = array[j]
lw $t2, 4($t1) # $t2 = array[j+1]
sw $t2, 0($t1) # array[j] = $t2
sw $t0, 4($t1) # array[j+1] = $t0
jr $ra
#function swap end
#Note:
.data
array: .word 0,0,0,0,0,0,0,0,0,0,0
size: .word 11
nl: .asciiz "\n"
dotmsg: .asciiz ","
resmsg: .asciiz "Sorting result:"
midmsg: .asciiz "Median:"
首先宣告一個 11 個 word 大小的記憶體區段做為 array 使用
.data
array: .word 0,0,0,0,0,0,0,0,0,0,0
size: .word 11
其中 array 中有 11 個零，代表 array 中 11 個變數的初始值；
而 size 代表 array 中有幾個變數。
之後 array 中的 11 個數字須由 使用者輸入，輸入完 11 個數字後，在 console 中印出 bubble sort 後的結果(由小排到大)，以及 11 個數字的中位數
泡泡排序的 C/C++ 片段 (sort function 的原版)
i = n-1;
while(i >= 0) {
j = 0;
for(j = 0; j < i; j++) {
if(array[j] < array[j+1])
goto end;
swap(array[j], array[j+1]);
end:;
}
i--;
}
輸出格式的 C/C++ 片段 (Outputi 的原版)
for(i = 0; i < 11; i++) {
if(i == 0)
goto notdot;
putchar(',');
notdot:
printf("%d", array[i]);
}
puts("");
#Write Bubble Sort by MIPS instruction
#read 11 numbers to sort(small to larger)
.text
.globl main
main: #start process
addi $sp, $sp, -12
sw $ra, 0($sp)
sw $s0, 4($sp)
sw $s1, 8($sp)
move $s0, $zero # i = 0
li $t0, 0 # j = 0
la $t1, array # load $t1 = &array
lw $t2, size # load $t2 = size
inputi: #start readinput
li $v0, 5 # $v0 function result, call readInt
syscall # ReadInt(& $v0)
add $t3, $t0, $t1 # $t3 = array + $t0 (array+j)
sw $v0, 0($t3) # array+t3 = v0
addi $t0, $t0, 4 # 4 bytes(word)
addi $s0, $s0, 1 # i = i+1
bne $s0, $t2, inputi
#end readinput
la $a0, array
lw $a1, size
jal sort
#start output
move $s0, $zero # i = 0
li $t0, 0 # j = 0
la $t1, array # load $t1 = &array
lw $t2, size # load $t2 = size
li $v0, 4 # printString("Sorting ...")
la $a0, resmsg
syscall
outputi:
beq $s0, $zero, notprintdot
li $v0, 4 # printString(",")
la $a0, dotmsg
syscall
notprintdot:
li $v0, 1 # $v0 function result, call printInt
add $t3, $t0, $t1 # $t2 = array + $t0
lw $a0, 0($t3) # printInt($a0)
syscall
addi $t0, $t0, 4 # j += 4, 4 bytes(word)
addi $s0, $s0, 1 # i = i+1
bne $s0, $t2, outputi
# outputi loop end
li $v0, 4 # printString("\n")
la $a0, nl
syscall
li $v0, 4 # printString("Median:")
la $a0, midmsg
syscall
lw $t0, size # $t0 = size
la $t1, array # $t1 = &array
srl $t0, $t0, 1 # $t0 = size>>1 (index)
sll $t0, $t0, 2 # $t0 = $t0 * 4 (array+t0)
add $t0, $t0, $t1 # $t0 = array+t0
li $v0, 1 # printInt($a0)
lw $a0, 0($t0) # $a0 = mem[0($t0)]
syscall
#end output
lw $s1, 8($sp)
lw $s0, 4($sp)
lw $ra, 0($sp)
addi $sp, $sp, 12
jr $ra
#end process
#function sort(array, n) => ($a0, $a1) begin
sort: addi $sp, $sp, -20 # make room on stack for 5 registers
sw $ra, 16($sp)
sw $s3, 12($sp)
sw $s2, 8($sp)
sw $s1, 4($sp)
sw $s0, 0($sp)
move $s2, $a0 # $s2 = &array
move $s3, $a1 # $s3 = n(array_size)
move $s0, $s3 # $s0 = i = n
addi $s0, $s0, -1 # $s0 = n-1
for1tst:
slt $t0, $s0, $zero # while(i >= 0)
bne $t0, $zero, exit1# t0 = 1, i < 0
move $s1, $zero # $s1 = j = 0
for2tst:
slt $t0, $s1, $s0 # while(j < i)
beq $t0, $zero, exit2# t0 = 0, j >= i
sll $t1, $s1, 2 # $t1 = 4 * j
add $t2, $s2, $t1 # $t2 = &array[j] = $s2 + 4*j
lw $t3, 0($t2) # $t3 = array[j]
lw $t4, 4($t2) # $t4 = array[j+1]
slt $t0, $t3, $t4 # if(array[j] > array[j+1]) swap()
bne $t0, $zero, for2end# t0 = 1, array[j] < array[j+1]
move $a0, $s2 # call swap(array, j)
move $a1, $s1
jal swap
for2end:
addi $s1, $s1, 1 # j++
j for2tst
exit2:
addi $s0, $s0, -1 # i--
j for1tst
exit1:
lw $s0, 0($sp)
lw $s1, 4($sp)
lw $s2, 8($sp)
lw $s3, 12($sp)
lw $ra, 16($sp)
addi $sp, $sp, 20
jr $ra # return to call routine
#function sort(array, n) end
#function swap(array, j) => ($a0, $a1)begin // swap(array[j], array[j+1])
swap:
sll $t1, $a1, 2 # $t1 = j*4
add $t1, $a0, $t1 # $t1 = &array[j] = $a0 + j*4
lw $t0, 0($t1) # $t0 = array[j]
lw $t2, 4($t1) # $t2 = array[j+1]
sw $t2, 0($t1) # array[j] = $t2
sw $t0, 4($t1) # array[j+1] = $t0
jr $ra
#function swap end
#Note:
.data
array: .word 0,0,0,0,0,0,0,0,0,0,0
size: .word 11
nl: .asciiz "\n"
dotmsg: .asciiz ","
resmsg: .asciiz "Sorting result:"
midmsg: .asciiz "Median:"