c - MIPS/C 中的钻石排序

Question

假设我们有一个菱形(13*13 数组中有 85 个元素)每个元素有两个参数，a/b我们需要对钻石进行排序，以便:

1. 每列中的 [a] 参数都会增加。
2. 每行中的 [b] 参数都会增加。

我们想要得到的是这样的:(*是内存中没有定义的部分)

(这是一个简单的 5*5 数组中的 13 个元素)

原文:

*    *   4/3   *   *
*   1/3  2/3  4/5  *
1/2 3/1  2/5  3/6 2/7
*   2/3  1/2  5/2  *
*    *   6/1   *   *

排序:

*    *   1/3   *   *
*   1/2  2/3  2/5  *
1/2 2/3  4/5  3/6 2/7
*   3/1  5/2  4/3  *
*    *   6/1   *   *

我的算法是对所有值进行冒泡排序(根据a)，然后根据b参数对每一行进行排序。这工作得很好，但动态指令将超过 80000 条(应该是 O[n^2])。冒泡排序在 MIPS 中很糟糕，因为你需要 >10 个指令。每张支票(在气泡中)。

我想知道是否有更好的算法可以将动态指令减少到14000以下。顺便说一句，仅使用<=15个寄存器和<=66个静态指令(即66行代码)。

findnum:    addi    $27, $27, 4
            lw  $21, 0($27)
            beq $21, $0, findnum    # find the next nonzero number


bsort:      lw  $20, 0($25)             # load first number            
            slt $12, $21, $20       # if second < first $12=1
            bne $12, $15,  back     # $15 is constant 1
            sw  $21, 0($25)
            sw  $20, 0($27)
back:       addi    $25, $27, 0     # now second number is first number
            bne $27, $26, findnum   # $27 not the end then continue         



loop:       addi    $25, $01, 24
            addi    $27, $25, 0     # reinitialize the number
            addi    $10, $10, 1     # i++
            bne     $10, $11, findnum   # if i not equal to 85 jump back    

这是我的代码的核心部分。 $25 和 $27 被初始化为数组第一个值的地址。 $26 是最后一个值的地址。

非常感谢!

Answer 1

允许您证明 2D 结构的一种方法是转换您的值，将它们填充到 1D 数组中，对它们进行排序，将它们填充回 2D 并将它们转换回来。

因此，在您的简化示例中，通过以下转换，4/3 将变为数字:403:

n(x/y) = 100*x + y

将 2D 数组填充到 1D 数组是一个简单的(嵌套)for 循环，然后再返回。

[403, 103, 203, 405 ...]

然后，一旦一维数组中有这样的数字，只需对其进行排序即可，例如通过快速排序。

为了将 1D 复制回 2D，您应该有一个规则来确定哪个数字属于哪一行。返回数字的转换为:

(x/y) = ( floor(n/100) / n%100 )

使用一般标准对二维结构进行一般排序可能并不那么容易。但在这种情况下，这种方法会起作用。它已被用于其他场合:

Sorting with 2D Arrays