Проблемы в цикле сортировки выбора - PullRequest
Новая
       86

Проблемы в цикле сортировки выбора

0 голосов
/ 27 мая 2020

У меня проблемы с реализацией метода сортировки выбора в сборке.

Я все еще не понимаю, где я ошибаюсь. Любая помощь приветствуется.

Возможно, я ошибаюсь, когда выделяю число в векторе, а затем сравниваю его.

Следуйте коду в 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

1 Ответ

1 голос
/ 27 мая 2020

Давайте посмотрим на поток управления для оператора for, сначала в псевдокоде: 

for ( int i = 0; i < n; i++ ) {
    ...body...
}
  1. сначала мы выполняем i=0 один раз за пределами l oop.
  2. затем мы начинаем l oop с проверки i<n, чтобы увидеть, закончили ли мы с l oop,
  3. , затем код для ...body..., а затем
  4. приращение i++ и, наконец,
  5. , чтобы повторить l oop: go вернуться к шагу 2.

Когда (с использованием программирования структуры ) мы вкладываем другой управляющий оператор в тело l oop, мы по-прежнему следуем тому же шаблону без изменений: 

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

Итак, здесь тело - это просто if-оператор. Таким образом:

  1. сначала делаем i=0, один раз, за ​​пределами l oop.
  2. затем, мы начинаем l oop с проверкой i<n, чтобы увидеть если мы закончили с l oop,
  3. , затем ...body..., что здесь if-выражение:
    • test a захват b = a
  4. приращение i++ и, наконец,
  5. , чтобы повторить l oop: go вернуться к шагу 2.

Видите ли вы, как срабатывает вложенный оператор if или нет? Следующее, что нужно сделать, это приращение оператора for i++?

Вы случайно переместили инкремент j++ внутрь then-части, внутри вложенного оператора if. Ваш код не следует правильному шаблону для вложенных структур управления - оператор if не должен мешать оператору for, в который он вложен. Таким образом, вместо того, чтобы делать j++ независимо от того, что делает оператор if, вы делаете j++ только тогда, когда срабатывает оператор if. Таким образом, это неправильный перевод псевдокода, и он просто не будет работать должным образом.

Далее, когда вы меняете местами, вы используете 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
...