assembly - 使用 MIPS 进行冒泡排序

Question

我已经创建了进行比较和交换的内部循环，但我很难实现将根据元素数量运行的外部循环。

.data
Arr: .word 5, 4, 3, 2, 1

.text
.globl main 
 main:
 la   $a0, Arr      # Pass the base address of the array Arr to input   argument register $a0
addi $a1, $zero, 5 # initialze the value of sorting loop ($al=5)
li   $t1, 0        # initialize the value of outer loop (t1=0)


sort:
lw  $s1, 0($a0)     # Load first element in s1 
lw  $s2, 4($a0)     # Load second element in s2
bgt $s1, $s2, swap  # if (s1 > s2) go to swap


sorting_loop:
addiu $a0, $a0, 4  # move pointer to next element
subiu $a1, $a1, 1  # decrement the value of inner loop ($a1)
bgtz  $a1, sort    # loop till value of inner loop is not equal to zero

j end              

swap:
sw   $s1, 4($a0) # put value of [i+1] in s1
sw   $s2, 0($a0) # put value of [i] in s2
j    sorting_loop

end: # End the program
li $v0, 10
syscall

Answer 1

你的内部传球看起来很不错，但 [我认为] 它会用 4($a0) 结束一次(例如，对于 5 的数组，循环计数必须是 4 ).我已经解决了。

我添加了外循环。请原谅不必要的样式清理，但这是我在添加之前理解您的逻辑的方式。我重命名了您的一些标签，这样它们对我来说更有意义。

当我添加外层循环时，我将您的内层循环转换为由外层循环调用的函数[那样看起来更清晰]。

我添加了两个优化:递减传递计数和“提前退出”标志 [如果给定的传递没有交换]。

我还添加了一些注释。代码可能并不完美，但我认为它会帮助您更接近。

# bubble sort

    .data
Arr:        .word       5,4,3,2,1

    .text
    .globl  main
main:
    li      $t1,5                   # get total number of array elements

# main_loop -- do multiple passes through array
main_loop:
    subi    $a1,$t1,1               # get count for this pass (must be one less)
    blez    $a1,main_done           # are we done? if yes, fly

    la      $a0,Arr                 # get address of array
    li      $t2,0                   # clear the "did swap" flag

    jal     pass_loop               # do a single sort pass

    # NOTES:
    # (1) if we make no swaps on a given pass, everything is in sort and we
    #     can stop
    # (2) after a pass the last element is now highest, so there is no need
    #     to compare it again
    # (3) a standard optimization is that each subsequent pass shortens the
    #     pass count by 1
    # (4) by bumping down the outer loop count here, this serves both _us_ and
    #     the single pass routine [with a single register]

    beqz    $t2,main_done           # if no swaps on current pass, we are done

    subi    $t1,$t1,1               # bump down number of remaining passes
    b       main_loop

# everything is sorted
# do whatever with the sorted data ...
main_done:
    j       end                     # terminate program

# pass_loop -- do single pass through array
#   a0 -- address of array
#   a1 -- number of loops to perform (must be one less than array size because
#         of the 4($a0) below)
pass_loop:
    lw      $s1,0($a0)              # Load first element in s1
    lw      $s2,4($a0)              # Load second element in s2
    bgt     $s1,$s2,pass_swap       # if (s1 > s2) swap elements

pass_next:
    addiu   $a0,$a0,4               # move pointer to next element
    subiu   $a1,$a1,1               # decrement number of loops remaining
    bgtz    $a1,pass_loop           # swap pass done? if no, loop
    jr      $ra                     # yes, return

pass_swap:
    sw      $s1,4($a0)              # put value of [i+1] in s1
    sw      $s2,0($a0)              # put value of [i] in s2
    li      $t2,1                   # tell main loop that we did a swap
    j       pass_next

# End the program
end:
    li      $v0,10
    syscall