MIPS—冒泡排序

SORT

使用冒泡排序对整数数组进行排序，这种排序虽然不是最快的，但却是最简单的。

C语言代码

 1 #include<stdio.h>
 2 #include<iostream>
 3 using namespace std;
 4 
 5 void swap(int v[], int k)
 6 {
 7     int tmp;
 8     tmp = v[k];
 9     v[k] = v[k + 1];
10     v[k + 1] = tmp;
11 }
12 
13 void sort(int v[], int n)
14 {
15     int i, j;
16     for (i = 0; i < n; i += 1)
17         for (j = i - 1; j >= 0 && v[j] > v[j + 1]; j -= 1)
18             swap(v, j);
19 }
20 
21 int arr[10] = { 3,10,8,2,5,2,3 };
22 
23 int main()
24 {
25     sort(arr, 7);
26     for (int i = 0; i < 7; i++)
27         printf("%d ", arr[i]);
28     return 0;
29 }

MIPS代码

  1 #sort
  2 .data
  3     array: .word  3,10,8,2,5,2,3
  4     str_old:    .asciiz "old array:
"
  5     str_new:    .asciiz "new array:
"
  6     blank:      .asciiz " "
  7     enter:      .asciiz "
"
  8 .text
  9 .globl main
 10 main:
 11      la $a0,str_old  
 12     li $v0,4
 13     syscall                    #print str_old string
 14     jal print_array            #print old arrry
 15     
 16     la $a0,array               #array name
 17     li $a1,7                   #array length
 18     jal sort
 19     
 20     la $a0,str_new   
 21     li $v0,4
 22     syscall                    #print  str_new string
 23     jal print_array            #print new arrry
 24     
 25     li $v0,10
 26     syscall                    # exit
 27 
 28 print_array:
 29     li $a1, 7       
 30     la $a2, array   
 31 loop1:  blez $a1, over1       
 32     lw   $a0, 0($a2)       
 33     li   $v0, 1          
 34     syscall
 35 
 36     la $a0, blank              
 37     li $v0, 4
 38     syscall
 39 
 40     addi $a2, $a2, 4        
 41     addi $a1, $a1, -1     
 42     j loop1
 43 over1:
 44     la $a0, enter           
 45     li $v0, 4
 46     syscall
 47     jr $ra
 48 
 49 #$a0: arrry
 50 #$a1: k
 51 swap:
 52     sll $t1,$a1,2             #reg $t1 = k * 4
 53     add $t1,$a0,$t1           #reg $t1 = v + k * 4
 54     
 55     lw $t0,0($t1)             #reg $t0(tmp) = v[k]
 56     lw $t2,4($t1)             #reg $t2 = v[k + 1]
 57     
 58     sw $t2,0($t1)             #v[k] = v[k + 1]
 59     sw $t0,4($t1)             #v[k+ 1] = tmp(v[k])    
 60     jr $ra
 61 #$a0: v
 62 #$a1: n
 63 #$s0: i
 64 #$s1: j
 65 sort:
 66     addi $sp,$sp,-20        #make room on stack for 5 registers
 67     sw $ra,16($sp)                
 68     sw $s3,12($sp)
 69     sw $s2,8($sp)
 70     sw $s1,4($sp)
 71     sw $s0,0($sp)
 72     
 73     move $s2,$a0            #save v
 74     move $s3,$a1            #save n
 75     
 76     move $s0,$zero          #i = 0
 77 for1tst:
 78     slt $t0,$s0,$s3     #if(i < n),reg $t0 = 1
 79     beq $t0,$zero,exit1
 80     
 81     addi $s1,$s0,-1
 82 for2tst:
 83     slti $t0,$s1,0            #if(j < 0),reg $t0 = 1
 84     bnez $t0,exit2            #go to exit2 if(j < 0)
 85     sll $t1,$s1,2             #$t1 = j * 4
 86     add $t2,$s2,$t1           #$t2 = v + j * 4
 87     lw  $t3,0($t2)            #$t3 = v[j]
 88     lw  $t4,4($t2)            #$t4 = v[j + 1]
 89     slt $t0,$t4,$t3           #if(v[j + 1] < v[j]),reg $t0 = 1
 90     beq $t0,$zero,exit2       #go to exit2 if(v[j + 1] >= v[j])
 91     
 92     move $a0,$s2              #first parameter is v
 93     move $a1,$s1              #second parameter is j
 94     jal swap
 95     
 96     addi $s1,$s1,-1           #j--
 97     j for2tst                 #continue inner loop
 98 exit2:
 99     addi $s0,$s0,1
100     j for1tst
101 exit1:
102     lw $s0,0($sp)
103     lw $s1,4($sp)
104     lw $s2,8($sp)
105     lw $s3,12($sp)
106     lw $ra,16($sp)
107     addi $sp,$sp,20
108     jr $ra

参考链接：wang22ti.com/2018/04/20/《计算机体系结构》实验2-1-MIPS指令集编程之冒泡排序/