选择排序循环中的问题

Question

我在程序集中执行选择排序方法时遇到问题。

我还是不明白我哪里错了。欢迎任何帮助。

可能我在向量中分配数字然后比较它时错了。

按照 C# 中的代码，然后按照我在汇编中所做的。

public static void selecao(int[] vet)
{
   int i, j, min, temp;
   for (i = 0; i < vet.Length - 1; i++)
   {
      min = i;
   for (j = i + 1; j < vet.Length; j++)
   {
      if (vet[j] < vet[min])
      {
         min = j;
      }
   }
   temp = vet[i];
   vet[i] = vet[min];
   vet[min] = temp;
   }
}

大会

addi $t0, $zero, 0 
addi $t1, $zero, 0  
sub $s1, $s0, 1     
addi $s2, $zero, 0  
addi $t1, $zero, 0 
forS1:
slt $t2, $t0, $s1 (i < size v - 1)
beq $t2, $zero, fimForS1

addi $s2, $t0, 0

addi $t3, $t0, 1 
forS2:
slt $t4, $t3, $s0
beq $t4, $zero, fimForS2

add $s6, $s6, 1 
mul $t3, $t3, 4 
lw $s3, vetor($t3)      # vet[j]
mul $s2, $s2, 4
lw $s4, vetor($s2)      # vet[min]
slt $t5, $s3, $s4       # vet[j] < vet[min]
beq $t5, $zero, forS2
add $s7, $s7, 1 
add $s2, $t3, 0         # min = j
addi $t3, $t3, 1 
j forS2

fimForS2:
lw $t6, vetor($t1)      # vet[i]
mul $s5, $s2, 2         # posicao do vet[min]
lw $t7, vetor($s2)      # vet[min]  
addi $t8, $t6, 0        # temp = vet[i]
sw $t6, vetor($s2)          # vet[i] = vet[min];
sw $t7, vetor($t1)          # vet[min] = temp;
addi $t1, $t1, 4 
addi $t0, $t0, 1 

j forS1

Answer 1

让我们看一下 for 语句的控制流程，首先是伪代码：

for ( int i = 0; i < n; i++ ) {
    ...body...
}

首先我们在循环外执行 i=0，一次。
接下来，我们开始循环检查 i<n 看看我们是否完成了循环，
接下来是 ...body... 的代码，然后是
增量i++，最后，
重复循环：返回步骤 2。

当（使用结构化编程）我们在循环体中嵌套另一个控制语句时，我们仍然遵循相同的模式，没有改变：

for ( int i = 0; i < n; i++ ) {
    if ( a < b ) {
         b = a;
    }
}

所以，这里的主体只是一个 if 语句。因此：

首先我们在循环外执行 i=0，一次。
接下来，我们开始循环检查 i<n 看看我们是否完成了循环，
在 ...body... 之后，这里是 if 语句：
- 测试 a < b，如果不是，则跳到 4。
- 夺取b=a
增量i++，最后，
重复循环：返回步骤 2。

你知道嵌套的 if 语句是如何触发还是不触发吗，接下来正确的事情是 for 语句增量 i++？

您不小心将 j++ 增量移动到嵌套 if 语句内的 then 部分内。您的代码没有遵循嵌套控制结构的正确模式——if 语句不应干扰它嵌套在其中的 for 语句。因此，不是不管 if 语句做什么都执行 j++，而是仅当 if 语句触发时才执行 j++。所以，这是伪代码的错误翻译，根本无法正常工作。

在下方，当您交换时，您正在使用 vet[min] 但您的数组索引已关闭。

查看内联说明：

addi $t0, $zero, 0 
addi $t1, $zero, 0  
sub $s1, $s0, 1     
addi $s2, $zero, 0  
addi $t1, $zero, 0    <--- unnecessary, already done above
forS1:
slt $t2, $t0, $s1 (i < size v - 1)
beq $t2, $zero, fimForS1

addi $s2, $t0, 0

addi $t3, $t0, 1 
forS2:
slt $t4, $t3, $s0
beq $t4, $zero, fimForS2

add $s6, $s6, 1 
mul $t3, $t3, 4 
lw $s3, vetor($t3)      # vet[j]
mul $s2, $s2, 4
lw $s4, vetor($s2)      # vet[min]
slt $t5, $s3, $s4       # vet[j] < vet[min]

beq $t5, $zero, forS2   <--- this if statement skips the then part (good)
                             ***** but also skip the j++ (bad) *****

+------------------------------- this it the then part
add $s7, $s7, 1 
add $s2, $t3, 0         # min = j
addi $t3, $t3, 1        <--- this is j++
+-------------------------------
j forS2

fimForS2:
lw $t6, vetor($t1)      # vet[i]
mul $s5, $s2, 2         # posicao do vet[min]  <--- multiply by 2 (why 2??)
                                                    ***** $s5 is never used *****
lw $t7, vetor($s2)      # vet[min]         <--- here using $s2, min (bad)
                                           ***** you want min*4 instead *****
addi $t8, $t6, 0        # temp = vet[i]
sw $t6, vetor($s2)          # vet[i] = vet[min];
sw $t7, vetor($t1)          # vet[min] = temp;
addi $t1, $t1, 4 
addi $t0, $t0, 1 

j forS1

选择排序循环中的问题

Problems in the selection sort loop

assembly

mips

nested-loops

selection-sort