逆転を狙う工大生の日々

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

アセンブリで挿入ソート~未完成ver~

ひだまりスケッチ一挙放送に時間を取られました。よかったです。

再履修の科目で、MIPSアセンブリでプログラム作成という課題がそのうち出ます。二つあって、去年のその片方はソートアルゴリズムを一つ実装してくださいという内容でした。去年は途中で投げ出しましたが、心を入れ替えた僕は強いのであらかじめやっておこうと。挿入ソートを選択した理由は、ソートする配列の要素はコンソール上の手入力という指定なので、そこまで大きなデータは取り扱わないと思い、実装の容易さと計算量的には妥当な落としどころだと思ったからです。

 

クイックソートが出来る気がしないというのはナイショで

 

それでいざ書き終えたのは良かったのですが、自宅のPCspimだとなんかうまくいかないので明日大学のでやってみます。英語読めないから分かんないです。コンパイルは通ったのでソースだけ貼っつけときますが、結果はどうなるのでしょうか。


	.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
	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,	5
	syscall

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

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

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

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

	jr	$ra

sort:	# 挿入ソート「$s2 = i」「$s3 = j」とする
	# i = 0
	move	$s2,	$zero
	
	# for(i=0;「i < array_elem_num」; i++)
	loop1:
	slt	$t5,	$s2,	$s1
	bne	$t5,	$zero,	loop1_end

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

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

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

	# a[j-1] > a[j]ならswapする
	ble	$t2,	$t1	swap_end	

	# swap 
	lw	$t3	0($t1)
	lw	$t4	0($t2)
	sw	$t3	0($t2)
	sw	$t4	0($t1)
	swap_end:
	
	# j--してループの先頭に
	addi	$s3,	$s3,	-1
	j	loop2
	
	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	$s0,	$s1,	loop_p

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

	jr	$ra

ポインタとか参照とかもそうだけど、やっぱり逐一図にしないと整理できないです。命令自体はシンプルだけどやっぱ引数の名前がまぎらわしい。このソースだと多分うまく動かないです。動かなくても、というか動かないこと前提で明日からデバッグ作業します!それではまた明日!