1

我正在使用 mips 进行课堂学习。我正在对一组数字进行排序，我认为我的方法可以正常工作，但有点麻烦。我不知道如何检查我何时完全排序。我使用了一种非常基本的排序方法，但这就是我们迄今为止所学到的全部内容。另外，我不知道如何输出数字以检查它是否已排序。我已经习惯了 Java，所以组装有点让我兴奋不已。到目前为止，这是我的代码：

    .text
    .globl main
main:       la  $a0, Array             # sets the base address of the array to $a0
loop:       lw  $t0, 0($a0)             # sets $t0 to the current element in array
            lw  $t1, 4($a0)         # sets $t1 to the next element in array
            blt $t1, $t0, swap      # if the following value is greater, swap them
            addi    $a0, $a0, 4     # advance the array to start at the next location from last time
            j   loop                  # jump back to loop so we can compare next two elements

swap:       sw  $t0, 4($a0)         # store the greater numbers contents in the higher position in array (swap)
            sw  $t1, 0($a0)         # store the lesser numbers contents in the lower position in array (swap)
            li  $a0, 0                 # resets the value of $a0 back to zero so we can start from beginning of array
            j   loop                  # jump back to the loop so we can go through and find next swap

            .data

Array:      .word   14, 12, 13, 5, 9, 11, 3, 6, 7, 10, 2, 4, 8, 1

感谢您的帮助！

4

3 回答 3

3

此链接说明如何在 MIPS 模拟器（如QTSPIM或MARS ）中打印到屏幕。

至于代码，有一些错误。该行正在覆盖初始指令li $a0, 0所做的工作，因为它将数组的基地址设置为 0。相反，您应该将指令移动到循环中，以便在遍历整个数组后正确重置为基地址，并删除该指令。您还需要添加程序何时完成排序的条件。我建议进行以下修订（使用 SPIM 测试）：la $a0, Arraylila$a0Arrayli

main:
    la  $t0, Array      # Copy the base address of your array into $t1
    add $t0, $t0, 40    # 4 bytes per int * 10 ints = 40 bytes                              
outterLoop:             # Used to determine when we are done iterating over the Array
    add $t1, $0, $0     # $t1 holds a flag to determine when the list is sorted
    la  $a0, Array      # Set $a0 to the base address of the Array
innerLoop:                  # The inner loop will iterate over the Array checking if a swap is needed
    lw  $t2, 0($a0)         # sets $t0 to the current element in array
    lw  $t3, 4($a0)         # sets $t1 to the next element in array
    slt $t5, $t2, $t3       # $t5 = 1 if $t0 < $t1
    beq $t5, $0, continue   # if $t5 = 1, then swap them
    add $t1, $0, 1          # if we need to swap, we need to check the list again
    sw  $t2, 4($a0)         # store the greater numbers contents in the higher position in array (swap)
    sw  $t3, 0($a0)         # store the lesser numbers contents in the lower position in array (swap)
continue:
    addi $a0, $a0, 4            # advance the array to start at the next location from last time
    bne  $a0, $t0, innerLoop    # If $a0 != the end of Array, jump back to innerLoop
    bne  $t1, $0, outterLoop    # $t1 = 1, another pass is needed, jump back to outterLoop

请务必查看此链接以获取有关每条 MIPS 指令功能的更多示例和说明。

于 2013-10-11T04:09:08.907 回答
1

直接在汇编中编码是一种痛苦。我所做的是从一个算法（伪代码或实际代码）开始，然后系统地翻译，就好像我是一个编译器一样。我将忽略输入和输出的东西并专注于排序的功能。

你会调用像 C 这样的高级语言：

insertionsort(data, N);

其中data是一个整数数组和N元素的数量（机器级别没有大小属性​​）。

由于该函数不调用任何内容，因此它不需要堆栈帧。遵守使用$t寄存器的标准 MIPS 约定，这样您就不会破坏其他任何人所依赖的任何东西，并按此顺序传入$a0参数$a1。

第一步：得到一个算法。这是 [Wikipedia][1] 中用于插入排序的一个：

i ← 1
while i < length(A)
    x ← A[i]
    j ← i - 1
    while j >= 0 and A[j] > x
        A[j+1] ← A[j]
        j ← j - 1
    end while
    A[j+1] ← x
    i ← i + 1
end while

第二步：粘贴到文本文件中，将所有行变成注释，系统地转换成汇编。我将模板用于诸如循环之类的事情，以消除编码中的猜测工作（有关示例，请参见我的免费书籍）。我这里只给出成品；要调用它，您需要将数组的起始地址$a0及其大小放入 中$a1，然后jal insertionsort：

# algorithm for insertion sort
# from https://en.wikipedia.org/wiki/Insertion_sort
# usage: insertionsort (a,N)
# pass array start in $a0, size in elements, N in $a1
# Philip Machanick
# 30 April 2018

            .globl insertionsort

            .text

# leaf function, no stack frame needed
# Registers:
#   $a0: base address; $a1: N
#   $t0: i
#   $t1: j
#   $t2: value of A[i] or A[j]
#   $t3: value of x (current A[i])
#   $t4: current offset of A[i] or A[j] as needed
insertionsort:
# i ← 1
       li $t0, 1
# while i < N
       j Wnext001        # test before 1st iteration
Wbody001:                # body of loop here
      sll $t4, $t0, 2    # scale index i to offset
      add $t4, $a0, $t4  # address of a[i]
#     x ← A[i]
      lw $t3, 0($t4)
#     j ← i - 1
      addi $t1, $t0, -1
#     while j >= 0 and A[j] > x
       j Wnext002        # test before 1st iteration
Wbody002:                # body of loop here
#         A[j+1] ← A[j]
          sll  $t4, $t1, 2        # scale index j to offset
          add $t4, $a0, $t4       # address of a[j]
          lw $t2, 0($t4)          # get value of A[j]
          addi $t4, $t4, 4        # offset of A[j+1]
          sw $t2, 0($t4)          # assign to A[j+1]
#         j ← j - 1
          addi $t1, $t1, -1
#     end while
Wnext002: # construct condition, j >= 0 and A[j] > x
          blt $t1, $zero Wdone002 # convert to: if j < 0 break from loop #####
          sll  $t4, $t1, 2        # scale index j to offset
          add $t4, $a0, $t4       # address of a[j]
          lw $t2, 0($t4)          # A[j]
          bgt $t2, $t3, Wbody002  # no need to test j >= 0, broke from loop already if false
Wdone002:                         # branch here to short-circuit and
#     A[j+1] ← x
          add  $t4, $t1, 1        # scale index j+1 to offset
          sll  $t4, $t4, 2        # scale index j to offset
          add $t4, $a0, $t4       # address of a[j+1]
          sw $t3, 0($t4)          # A[j+1] becomes x
#     i ← i + 1
          addi $t0, $t0, 1
# end while
Wnext001: blt $t0,$a1, Wbody001  # i < N easy this time
          jr $ra                 # return to caller

比其他例子更长——但如果你从一个算法开始翻译，你出错的可能性会更小。如果您的汇编程序遵守该.globl指令，这可以放在一个单独的文件中，这使得该名称在其他文件中可见。

[1]：https : //en.wikipedia.org/wiki/Insertion_sort – 实际上来自 Thomas H. 的 Cormen；莱森，查尔斯·E。里韦斯特，罗纳德 L.；斯坦，克利福德（2001 年）。“第 2.1 节：插入排序”。算法导论（第 2 版）。麻省理工学院出版社和麦格劳-希尔。第 15-21 页

于 2018-04-30T17:26:21.987 回答
-1

。数据

值：.word 0x3

数组：.word 0x14、0x12、0x13、0x05

。文本

.globl 主要

主要：la $a0，数组

   lw  $t3,value

l1: lw $t0, 0($a0)

   lw  $t1, 4($a0)     

   blt $t1, $t0, swap   

   addi    $a0, $a0, 4

   addi $t3,$t3,-1     

   bne  $t3,$zero,l1

   jr $ra

交换：sw $t0, 4($a0) 

    sw  $t1, 0($a0)    

    j   l1
于 2018-02-07T07:02:14.203 回答