アセンブリ言語(MIPS)でソート

大学の課題用 **(再　履　修)**
メモリ解放の仕方が分からなかったので確保したスペース放置してる

![ss (2014-05-03 at 10.35.37).png](https://qiita-image-store.s3.amazonaws.com/0/25060/63902d95-ea8c-d931-83fd-fbd88de2df44.png)

こんな感じで **[SPIM](http://spimsimulator.sourceforge.net/)** コンソール上で動いてくれます

# `.data` セクション

## 文字列の定義

```zsh
bracket_start: .asciiz "["
bracket_end: .asciiz "]: "
input_message_0: .asciiz "Number of integers: "
input_message_1: .asciiz "Input"
output_message_0: .asciiz "Sorted results: "
output_message_1: .asciiz "Output"
error_message: .asciiz "Number of integers must be positive"
eol: .asciiz "\n"
```

## 固定的に使うレジスタの定義

- ***$s0***<br />→ 配列
- ***$s1***<br />→ 配列のサイズ

# `.text` セクション

## `main` ルーチン

「入力」→「ソート」→「出力」を繰り返す

```zsh:バブルソート用の実装
main:

	jal read
	jal sort
	jal print
	j main
```


```zsh:クイックソート用の実装
main:

	jal read

	# sort(0, N - 1);
	move $a0, $zero
	move $a1, $s1
	addi $a1, $a1, -1
	jal sort

	jal print
	j main
```

## `read` ルーチン

ユーザー入力を受け付けて配列 ***$s0*** に格納する

```zsh
read:
	
	# "Number of integers:"　と表示する
	li $v0, 4
	la $a0, input_message_0
	syscall
	
	# 生成する配列のサイズを$v0に受け取る
	li $v0, 5
	syscall
	
	# 正の数であればread_prepareにジャンプする
	bgt $v0, $zero, read_prepare
	
	# "Number of integers must be positive\n" と表示する
	li $v0, 4
	la $a0, error_message
	syscall
	la $a0, eol
	syscall
	
	# リトライさせる
	j read
	
	read_prepare:
	
	# 生成する配列のサイズを$s1に保存する
	move $s1, $v0
	
	# 配列を生成して先頭アドレスを$v0に受け取る
	sll $a0, $v0, 2
	li $v0, 9
	syscall
	
	# 生成した配列の先頭アドレスを$s0に保存する
	move $s0, $v0
	
	# 配列のオフセット用レジスタとして$t0を初期化する
	move $t0, $zero
	
	read_loop:
	
	# "Input[{$t0}]:" と表示する
	li $v0, 4
	la $a0, input_message_1
	syscall
	la $a0, bracket_start
	syscall
	li $v0, 1
	move $a0, $t0
	syscall
	li $v0, 4
	la $a0, bracket_end
	syscall
	
	# 設定する配列要素の値を$v0に受け取る
	li $v0, 5
	syscall
	
	# 実際に保存する
	sll $t1, $t0, 2
	add $t1, $t1, $s0
	sw $v0, 0($t1)
	
	# オフセットをインクリメントする
	addi $t0, $t0, 1
	
	# 作成した配列にまだ空きがあればread_loopにジャンプする
	bne $t0, $s1, read_loop
	
	# "\n" と表示する
	li $v0, 4
	la $a0, eol
	syscall
	
	# 復帰する
	jr $ra
```

## `print` ルーチン 

配列 ***$s0*** の値を出力する

```zsh
print:
	
	# 配列のオフセット用レジスタとして$t0を初期化する
	move $t0, $zero
	
	# "Sorting results:" と表示する
	li $v0, 4
	la $a0, output_message_0
	syscall
	la $a0, eol
	syscall
	
	print_loop:
	
	# "Output[{$t0}]:" と表示する
	li $v0, 4
	la $a0, output_message_1
	syscall
	la $a0, bracket_start
	syscall
	li $v0, 1
	move $a0, $t0
	syscall
	li $v0, 4
	la $a0, bracket_end
	syscall
	
	# 格納されている値を取り出して表示する
	sll $t1, $t0, 2
	add $t1, $t1, $s0
	li $v0, 1
	lw $a0, 0($t1)
	syscall
	
	# "\n" と表示する
	li $v0, 4
	la $a0, eol
	syscall
	
	# オフセットをインクリメントさせる
	addi $t0, $t0, 1
	
	# 配列要素の巡回がまだ済んでいなければprint_loopにジャンプする
	bne $t0, $s1, print_loop
	
	# "\n" と表示する
	li $v0, 4
	la $a0, eol
	syscall
	
	# 復帰する
	jr $ra
```	

## `sort` ルーチン

```zsh:バブルソート用の実装
sort:
	
	# i = 0;
	move $s2, $zero;
	
	# while (i < N) {
	loop_i_start:
	bge $s2, $s1, loop_i_end
	
	# j = N - 1;
	add $s3, $s1, -1
	
	# while (j > i) {
	loop_j_start:
	ble $s3, $s2, loop_j_end
	
	# if (x[j] < x[j - 1]) swap(&x[j], &x[j - 1]);
	add $t1, $s3, -1
	sll $t0, $s3, 2
	sll $t1, $t1, 2
	add $t0, $t0, $s0
	add $t1, $t1, $s0
	lw $t2, 0($t0)
	lw $t3, 0($t1)
	bge $t2, $t3, skip_swap
	sw $t2, 0($t1)
	sw $t3, 0($t0)
	skip_swap:
	
	# --j;
	addi $s3, $s3, -1
	
	# }
	j loop_j_start
	loop_j_end:
	
	# ++i;
	addi $s2, $s2, 1
	
	# }
	j loop_i_start
	loop_i_end:
	
	# return;
	jr $ra
```

```zsh:クイックソート用の実装
sort:
	
	# スタックへの退避
	addi $sp, $sp, -20
	sw $ra, 16($sp)
	sw $s5, 12($sp)
	sw $s4, 8($sp)
	sw $s3, 4($sp)
	sw $s2, 0($sp)
	move $s2, $a0
	move $s3, $a1
	
	# i = left;
	move $s4, $s2
	
	# j = right;
	move $s5, $s3
	
	# pivot = x[(left + right) / 2];
	add $t0, $s2, $s3
	li $t1, 2 
	div $t0, $t1
	mflo $t0
	sll $t0, $t0, 2
	add $t0, $t0, $s0
	lw $t0, 0($t0)
	
	# while (1) {
	loop_start:
	
	# while (x[i] < pivot) ++i;
	loop_i_start:
	move $t1, $s4
	sll $t1, $t1, 2
	add $t1, $t1, $s0
	lw $t1, 0($t1)
	bge $t1, $t0, loop_i_end
	addi $s4, $s4, 1

	# }
	j loop_i_start
	loop_i_end:
	
	# while (pivot < x[j]) --j;
	loop_j_start:
	move $t1, $s5
	sll $t1, $t1, 2
	add $t1, $t1, $s0
	lw $t1, 0($t1)
	bge $t0, $t1, loop_j_end
	addi $s5, $s5, -1

	# }
	j loop_j_start
	loop_j_end:
	
	# if (i >= j) break;
	bge $s4, $s5, loop_end
	
	# swap(&x[i], &x[j]);
	move $t1, $s4
	move $t2, $s5
	sll $t1, $t1, 2
	sll $t2, $t2, 2
	add $t1, $t1, $s0
	add $t2, $t2, $s0
	lw $t3, 0($t1)
	lw $t4, 0($t2)
	sw $t3, 0($t2)
	sw $t4, 0($t1)
	
	# ++i
	addi $s4, $s4, 1
	
	# --j
	addi $s5, $s5, -1
	
	# }
	j loop_start;
	loop_end:
	
	# if (left < i - 1) sort(left, i - 1);
	move $t0, $s4
	addi $t0, $t0, -1
	bge $s2, $t0, skip_left_sort
	move $a0, $s2
	move $a1, $t0
	jal sort
	skip_left_sort:
	
	# if (j + 1 < right) sort(j + 1, right);
	move $t0, $s5
	addi $t0, $t0, 1
	bge $t0, $s3, skip_right_sort
	move $a0, $t0
	move $a1, $s3
	jal sort
	skip_right_sort:
	
	# スタックからの復元
	lw $s2, 0($sp)
	lw $s3, 4($sp)
	lw $s4, 8($sp)
	lw $s5, 12($sp)
	lw $ra, 16($sp)
	addi $sp, $sp, 20
	
	# return;
	jr $ra
```