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 的评论。

MASM x86 中的冒泡排序在几次迭代后不排序

Bubble Sort in MASM x86 Not Sorting After Few Interations

x86

assembly

masm

bubble-sort