逆転を狙う工大生の日々

絶賛留年中の落ちこぼれがなんとか頑張ろうとしている日記です

アセンブリで挿入ソート〜完成版〜

いろいろ調べてようやくできたので貼り付けておきます。ソート部分以外はほとんどいろんなサイトを参考にしながらの構成となってしまった。英語読めるようになれば調べるのも楽になるのかな。


         .data
array_elem_num: .asciiz"array_elem_num : "
bracket_1: .asciiz "["
bracket_2: .asciiz "]"
input:  .asciiz"input"
output: .asciiz"output"
equal:  .asciiz"="
line:   .asciiz"--------result--------"
eol:    .asciiz"\n"

        .text
        .globl main

main:
        jal     read
        li      $v0,    4
        la      $a0,    line
        syscall
	li	$v0,	4
	la	$a0,	eol
	syscall
        jal     sort
        jal     print
        j       main

read:   # 「$s0 = 配列の先頭アドレス」「$s1 = 配列のサイズ」
        # 配列の大きさを読み込むためのメッセージ
        li      $v0,    4
        la      $a0,    array_elem_num
        syscall

        # 配列の大きさの入力を受け付ける
        li      $v0,    5
        syscall

        # 配列のサイズを$1に取り込む
        move    $s1,    $v0

        # 配列を生成して先頭アドレスを受け取る
        sll     $a0,    $v0,    2
        li      $v0,    9
        syscall

        # 生成した配列の先頭アドレスを$s0に保存
        move    $s0,    $v0

        # 配列のオフセット用のレジスタとして$t0を初期化する
        move    $t0,    $zero

        loop:

        # "input[0]="~"input[array_elem_num]="と表示する
        li      $v0,    4
        la      $a0,    input
        syscall
        la      $a0,    bracket_1
        syscall
        li      $v0,    1
        move    $a0,    $t0
        syscall
        li      $v0,    4
        la      $a0,    bracket_2
        syscall
	li	$v0,	4
	la	$a0,	equal
	syscall

        # 設定する配列要素の値を受け取る
        li      $v0,    5
        syscall

        # 取り込んだ値を保存する
        sll     $t1,    $t0,    2
        add     $t1,    $t1,    $s0
        sw      $v0,    0($t1)

        # オフセットをインクリメントする
        addi    $t0,    $t0,    1

        # 入力し終えたかチェック
        bne     $t0,    $s1,    loop

        # 改行する
        li      $v0,    4
        la      $a0,    eol
        syscall

        jr      $ra

sort:   # 挿入ソート「$s2 = i」「$s3 = j」とする
        # i = 1
        li    $s2,    1
       
        # for(i=1;「i < array_elem_num」; i++)
        loop1:
	beq	$s2,	$s1,	loop1_end

	# j = i
	move	$s3,	$s2
	
        # for(j=i; 「j >= 1」; j-- )
        loop2:
        beq     $s3,    $zero,	loop2_end                      

        # $t1 = a[j]
        sll     $t0,    $s3,    2
        add     $t0,    $t0,    $s0
        lw      $t2,    0($t0)

        # $t2 = a[j-1]
        addi    $t1,    $s3,    -1
        sll     $t1,    $t1,    2
        add     $t1,    $t1,    $s0
        lw      $t3,    0($t1)

        # a[j-1] > a[j]ならswapする
        # swap 
	ble	$t3,	$t2,	swap_end
        sw      $t2     0($t1)
        sw      $t3     0($t0)
        swap_end:
       
        # j--してjループの先頭に
        addi    $s3,    $s3,    -1
        j       loop2

	# i++してiループの先頭に
        loop2_end:
        addi    $s2,    $s2,    1
        j       loop1

        loop1_end:
        jr      $ra

print:
        # 配列のオフセットとして$t0を初期化
        move    $t0,    $zero

        # output[0]~output[array_elem_num]をread部分同様プリントする
        loop_p:
        li      $v0,    4
        la      $a0,    output
        syscall
        li      $v0,    4
        la      $a0,    bracket_1
        syscall
        li      $v0,    1
        move    $a0,    $t0
        syscall
        li      $v0,    4
        la      $a0,    bracket_2
        syscall
        li      $v0,    4
        la      $a0,    equal
        syscall

        # 配列の値を読み込んで出力
        sll     $t1,    $t0,    2
        add     $t1,    $t1,    $s0
        li      $v0,    1
        lw      $a0,    0($t1)
        syscall
       
        # 改行
        li      $v0,    4
        la      $a0,    eol
        syscall

        # オフセットをインクリメント
        addi    $t0,    $t0,    1
       
        # すべて出力して無ければ戻る
        bne     $t0,    $s1,    loop_p

        # 改行
        li      $v0,    4
        la      $a0,    eol
        syscall

        jr      $ra
 

こんな感じです。未完成のほうの記事は消すつもりだったのですが、あとで比較するのも面白いかなと思ったので残しときます。こちらは実行結果。ずっと繰り返します。提出前には0を入力すると終了するようにしときます。

f:id:ikuth:20140513111017p:plain