assembly - MASM x86 中的冒泡排序在几次迭代后未排序

Question

所以，我尝试使用此代码作为模板来实现 BubbleSort:

    int n = arr.length;  
    int temp = 0;  
     for(int i=0; i < n; i++){  
             for(int j=1; j < (n-i); j++){  
                      if(arr[j-1] > arr[j]){  
                             //swap elements  
                             temp = arr[j-1];  
                             arr[j-1] = arr[j];  
                             arr[j] = temp;  

但是，我的汇编代码仅对前 1 - 2 次进行排序，并且产生错误的结果。我尝试运行调试器，多次单步执行，但我天真的眼睛无法发现翻译中的任何错误。

.data
arr DWORD 3,2,1,4,5
temp DWORD 0
arr_j DWORD 0
; Bubble Sort
.code
main proc
mov esi, OFFSET arr
mov eax, 0 ; for outer loop
mov ebx, 1 ; for inner loop

OuterLoop:

     InnerLoop:

        ; swap elements
        ; referencing j in array
        call MULTIPLY
        add edx, esi ; edx = esi + 4*ebx that is *arr[j]
        mov edi, [edx]
        mov [arr_j], edi ; store arr[j]
        sub edx, 4
        mov edi, [edx] ; store arr[j - 1]

        cmp edi, [arr_j] ; if(arr[j-1] > arr[j]) -> swap elements
        jle FAIL_SWAP

        ; swap elements here
        mov [temp], edi
        mov edi, [arr_j]
        mov ebp, [temp]
        mov [edx], edi ; arr[j - 1] < arr[j]
        add edx, 4
        mov [edx], ebp

        FAIL_SWAP:

     inc ebx
     mov ecx, LENGTHOF arr
     sub ecx, eax
     cmp ebx, ecx
     jl InnerLoop

inc eax
cmp eax, LENGTHOF arr
jl OuterLoop     


invoke ExitProcess,0
main ENDP

MULTIPLY PROC ; multiply 4 with ebx, store at edx
    push esi

    xor esi, esi
    mov esi, 1

    mov edx, ebx

    LOOPER:
    add edx, ebx

    inc esi
    cmp esi, 4
    jl LOOPER

    pop esi
    ret
MULTIPLY ENDP
END main

非常感谢任何帮助。谢谢。

Answer 1

int n = arr.length;  
  int temp = 0;  
    for(int i=0; i < n; i++){  
      for(int j=1; j < (n-i); j++){
        ...

此模板代码已有错误。外循环执行 1 次迭代太多了!
考虑一个 2 元素数组，其中 n 为 2。完整的冒泡排序将包含一次比较，但外部循环将执行 2 次迭代(i=0 和 i=1)。显然是错误的。

mov eax, 0 ; for outer loop
mov ebx, 1 ; for inner loop
OuterLoop:
    InnerLoop:

您的 InnerLoop 第一次运行一切正常，但第二次它以 BX=5 开头，因为这是值 BX到达循环的末尾。每次InnerLoop开始运行时，您都需要将BX寄存器重置为1。

mov eax, 0 ; for outer loop
OuterLoop:
    mov ebx, 1 ; for inner loop
    InnerLoop:

一个更简单的解决方案使用EAX作为递减计数器:

mov eax, LENGTHOF arr
dec eax
OuterLoop:
    mov ebx, 1 ; for inner loop
    InnerLoop:
        ...
        inc ebx
        cmp ebx, eax
        jbe InnerLoop
    dec eax
    jnz OuterLoop

这些将是 5 元素数组的 AX 和 BX 的值:

AX   BX
4    1 to 4
3    1 to 3
2    1 to 2
1    1 to 1

其余代码虽然正确，但过于复杂且效率低下。请参阅 Peter Cordes 的评论。