Попытка внедрить Flag Bubble Sort в MIPS

Question

Я пытаюсь реализовать алгоритм сортировки помеченных пузырьков в MIPS, следуя следующему коду C ++:

void bubbleSortV2(int a[ ], int n)    //  flagged bubble sort
{
    int i, temp, comps, sorted = 0; //  sorted is initially false
    comps = n – 1;

    while ( !sorted )           //  comps reduces on each pass
    {
        sorted = 1;     //  set true for each pass
        for  (i = 0; i < comps; i++)‏
        {
            if  (a[i] > a[i + 1])‏
            {
                temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
                sorted = 0; //  not yet sorted
            }
        }   //  end of each pass
        comps--;
    }   //  end all passes
}

Моя попытка в MIPS:

    li $v0, 0
    la $t1, array

    li $s3, 0 #i=0
    move $s4, $t0 #n
    sub $s4, $s4, 1 #n--
    li $s7, 0; #flag=0
    start:
        beq $s7, 0, stop #flag==1 we stop
        sort:
            li $s7, 1; #set flag=1
            bge $s3, $s4, endsort # while i<n
            lw $t2, 0($t1) #load first element
            lw $t3, 4($t1) #load second element
            bge $t2, $t3, swap #if first > second swap
        go_next:
            add $t1, $t1, 4 #next element
            sub $s4, $s4, 1 #n--
            bgtz $s4, start #if s4>0 we do it again
            swap:
                sw $s5, 4($t1) # swap elements
                sw $s6, 0($t1) #swap elements
                li $s7, 0; #set flag 0
        j go_next # next element
                add $s3, $s3, 1 #i++
        j sort # sort
        endsort:
    stop:

Я старался изо всех сил, чтобы следуйте кодексу высокого языка, но он не работает. Выход совпадает с входом. Могу ли я получить помощь?

Answer 1

У вас есть как минимум четыре проблемы:

Во-первых, в вашем коде для for (i = 0; i < comps; i++) отсутствует часть i = 0. Хотя у вас где-то есть i = 0, иметь его в неправильном месте не считается. Он есть вне всех циклов, и, как вы можете видеть, for находится внутри while - поэтому код C делает i = 0 внутри while l oop, но ваша сборка этого не делает, поэтому он не будет вести себя так же.

Во-вторых, ваш оператор if-then не соответствует хорошей схеме сборки. Хороший шаблон для if-then в стиле if-goto-label сборки:

Pseudo C code:

if ( condition ) {
    do something;
}
// if statement completed, on to whatever statement comes next

---

в стиле if-goto-label сборки ( хотя все еще используется псевдо C):

    if ( ! condition ) goto ifEnd;
    do something;
ifEnd:
    // if statement completed, on to whatever statement comes next

Подробно опишите точный поток управления кода C и сделайте, чтобы ваша сборка имела тот же поток управления. Не пытайтесь использовать альтернативный поток управления из кода C.

---

Существуют и другие шаблоны для реализации if-then, но большинство альтернативных форм позволяют очень легко потерять правильную перспективу, что это if-then вложен в for для l oop - и именно эта вложенность в коде C определяет, какой оператор (фрагмент) следует после if-then , запускается ли if-then или нет . Надеюсь, вы можете увидеть, используете ли вы выше шаблон в стиле if-goto-label сборки, что правильный оператор next будет выполняться next независимо от того, сработает ли if .

---

while Ваш код не так уж далек от правильности, не бойтесь начинать все сначала. Если вы используете больше строгости - придерживайтесь кода C и его вложенных конструкций (if должен быть полностью внутри for, что будет после if-then, et c).

Придерживайтесь выполнения составных частей в том же порядке, в котором их выполняет код C - не пытайтесь переставлять составные части кода (пока вы не узнаете, что делаете).

Не делайте застрять, думая, что ваш единственный вариант - угадать, как исправить испорченный код сборки, поскольку это может быть очень сложно.

---

Вы используете регистры $s5 и $s6, но никогда не помещать в них ничего.

---

Любой код между безусловной ветвью и следующей меткой недоступен,

    j somewhere123

    li $v0, 4
    la $a0, helloworld
    syscall

somelabel456:

В приведенном выше коде системного вызова между j somewhere123 и somelabel456: определенно недоступен и, следовательно, «мертв», т.е. никогда не используется; не может служить цели.