Сортировка массива в MIPS с указателем стека - PullRequest
Новая
       23

Сортировка массива в MIPS с указателем стека

0 голосов
/ 07 апреля 2019

Я хочу отсортировать заранее определенный массив с помощью функции подкачки в MIPS Assembly, но я застрял при написании кода подкачки.

Также я должен использовать указатель стека.

это код C ++ для него: 

for (i=0; i<n; i+=1) {
    for (j=i-1; j>=0 && v[j] > v[j+1]; j-=1) {
    swap (v,j);
    }
}

это код.я пытался использовать jal и jr и запутался. 

.data
.align 2
ARRAY: .word 12, 4, 23, 2, 5, 26, 13, 42, 41, 18
msg1: .asciiz " "

.text
.globl main
main:
la $a0, ARRAY
addi $a1, $zero, 10     #array length

sort:
addi $sp, $sp, -20
sw $ra, 16($sp)
sw $s3, 12($sp)
sw $s2, 8($sp)
sw $s1, 4($sp)
sw $s0, 0($sp)

add $s0, $zero, $zero
add $s2, $a0, $zero
add $s3, $a1, $zero

loop1:
slt $t0, $s0, $s3
beq $t0, $zero, exit1
addi $s1, $s0, -1

loop2:
slt $t0, $s1, $zero
bne $t0, $zero, exit2
sll $t1, $s1, 2
add $t2, $s2, $t1
lw $t3, 0($t2)
lw $t4, 4($t2)
slt $t0, $t4, $t3
beq $t0, $zero, exit2

add $a0, $s2, $zero
add $a1, $s3, $zero

swap:
?

addi $s1, $s1, -1
j loop2

exit2:
addi $s0, $s0, 1
j loop1

exit1:
lw $s0, 0($sp)
lw $s1, 4($sp)
lw $s2, 8($sp)
lw $s3, 12($sp)
lw $ra, 16($sp)
addi $sp, $sp, 20

exit:
li $v0, 10
syscall

что мне нужно сделать, чтобы поменять младший на больший, чтобы я мог отсортировать массив?

1 Ответ

0 голосов
/ 07 апреля 2019

Вы не должны реализовывать циклы, как вы делаете, с тестом на входе в цикл.Вам нужна дополнительная ветвь, которая менее эффективна и затрудняет понимание кода.

Если у вас есть цикл 

for(initial; test; increment) { body }

Просто переведите его на: 

   initial
loop:
   body
   increment
   test -> loop

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

Кроме того, начните с написания кода C с указателями для облегчения перевода 

for (i=0; i<n; i+=1) {
    for (j=i-1, parray=array[i-1]; j>=0 ; j-=1, parray--) {
       if(*parray > *(parray+1)) 
         swap (parray); // the pointer is sufficient
    }
}

Что касается операции подкачки, почему выхотите подпрограмму?Вы сохранили значения массивов [j] и array [j + 1] в регистрах, и вам просто нужно записать их обратно в правильные позиции.

Вот возможный переход (пропуская начало и конецостаются неизменными) 

...
sort:
addi $sp, $sp, -20
sw $ra, 16($sp)
sw $s3, 12($sp)
sw $s2, 8($sp)
sw $s1, 4($sp)
sw $s0, 0($sp)

   add $s0, $zero, $zero # i=0
   add $s2, $a0, $zero   # @array
   add $s3, $a1, $zero   # N

loop1:
    addi $s1, $s0, -1    # j=i-1
    sll $t1, $s1, 2
    add $t2, $s2, $t1    # @array[j]

loop2:
    lw $t3, 0($t2)         # $t3 array[j]
    lw $t4, 4($t2)         # $t4 array[j+1]
    sgt $t0, $t3, $t4      # array[j] > array[j+1]?
    bne $t0, $zero, noswap # no? -> noswap

swap:
    # just exchange the loaded values of array[j] and array[j+1]
    sw $t3, 4($t2)
    sw $t4, 0($t2)

noswap:

    addi $s1, $s1, -1   # j--
    addi $t2, $t2, -4   # array--
    sge $t0, $s1, $zero # j>=0?
    bne $t0, $zero, loop2

    addi $s0, $s0, 1  #i++
    slt $t0, $s0, $s3 #i<N?
    bne $t0, $zero, loop1

exit1:
...

Количество загрузок может быть уменьшено, так как на каждой итерации у вас уже есть массив [i], уже загруженный.

...