assembly - 如何选择排序 - assembly 8086

Question

我创建了一个对词向量进行选择排序的过程，但有一个问题:排序完全错误。

我的向量:VET_2 DW 2, 7, 0, 1, 4, 8, 9, 3, 6, 5

; Selection Sort
SELECTION_SORT PROC
    ; AX = j & aux      CX = i
    ; BX = offset/min   DX = data and others
    PUSH 0                              ; to initialize i
    MOV SI, [OFFSET VET_2]
    ; ----- start for(int i = 0; i < n-1; i++) -----
    SLC_LOOP_FORA:                      ; outer loop
        CALL RESET_REGIST               ; reset some AX, BX, CX & DX
        CALL RESET_VAR                  ; used to reset AUX

        POP CX                          ; initialize i
        CMP CX, 18                      ; check if it's smaller than n-1 (20-2=18)
        JGE SLC_FIM                     ; if bigger, goes to the end 

        MOV BX, CX                      ; offset receive i, the position of the smaller
        ; ----- start j = i+1 -----
        MOV AX, CX                      ; AX = j.
        ADD AX, 2                       ; j = i+1
        ; ----- end j = i+1 -----

        ; ----- start for(int j = i+1; j < n; j++) -----
        SLC_LOOP_DENTRO:                ; inner loop
            MOV DX, [SI+BX]             ; move the smaller element to DX
            MOV BX, AX                  ; offset receives j

            CMP DX, [SI+BX]             ; compare if VET_2[min]<=VET_2[j]
            JL SLC_DENTRO_PULAR         ; if lesser, ignore the code below

            MOV BX, AX                  ; offset receive j, position of the smaller element

            SLC_DENTRO_PULAR:
                ADD AX, 2               ; inc 2 in j
                CMP AX, 20              ; compare j (ax) with n
            JL SLC_LOOP_DENTRO          ; if it's smaller, repeat inner loop
        ; ----- end for(int j = n+1; j < n; j++) -----

        CMP CX, BX                      ; compare i with the position of the smaller element
        JE SLC_LOOP_FORA                ; if equals, repeat outer loop, otherwise do the swap

        PUSH BX                         ; position of the smaller element
        PUSH [SI+BX]                    ; put vet[min] top of the stack

        ; ----- start aux = vet[i] -----
        MOV BX, CX                      ; offset (BX) receives i
        MOV DX, [SI+BX]                 ; DX receives vet_2[i]
        MOV AUX, DX                     ; AUX receives DX
        ; ----- end aux = vet[i] -----

        ; ----- start vet[i] = vet[min] -----
        POP AX                          ; AX receives the top of the stack (vet_2[min])
        MOV [SI+BX], AX                 ; vet_2[i] receives DX (smaller element)
        ; ----- end vet[i] = vet[min] -----

        ; ----- start vet[min] = aux -----
        POP BX                          ; offset (BX) receives the position of the smaller element from the stack
        MOV DX, AUX                     ; DX receives AUX
        MOV [SI+BX], DX                 ; vet_2[min] receives DX
        ; ----- end vet[min] = aux -----
        ADD CX, 2                       ; INC 2 on i
        PUSH CX                         ; put in the stack
        JMP SLC_LOOP_FORA               repeat outer loop
    ; ----- end for(int i = 0; i < n-1; i++) -----
    SLC_FIM:                            ; end the procedure
        RET
SELECTION_SORT ENDP

调用选择排序过程之前:2 7 0 1 4 8 9 3 6 5

调用后选择排序过程:5 2 7 0 1 4 8 9 3 6

哪里出错了？有人可以帮助我吗？

Answer 1

问题

当不需要交换2个元素时，仍然需要提高CX中的下限。 cmp cx, bx je SLC_LOOP_FORA 忽略了这一点。此外，它还会导致堆栈不平衡(弹出的内容多于推送的内容)。

解决方案:

通过引入额外的标签可以轻松纠正问题(包括堆栈不平衡):

    PUSH 0                 ; to initialize i
    MOV SI, OFFSET VET_2
SLC_LOOP_FORA:             ; outer loop

    ...

    CMP CX, BX             ; compare i with the position of the smaller element
    JE NO_SWAP             ; if equals, repeat outer loop, otherwise do the swap

    ...

NO_SWAP:
    ADD CX, 2              ; INC 2 on i
    PUSH CX                ; put in the stack
    JMP SLC_LOOP_FORA      ; repeat outer loop

考虑

; AX = j & aux      CX = i
; BX = offset/min   DX = data and others
PUSH 0                              ; to initialize i
MOV SI, [OFFSET VET_2]

如果您愿意重新分配寄存器，您可以极大地简化这个程序。

使用寄存器分配，例如

; AX = j & aux      DI = i
; SI = offset/min   DX = data and others
PUSH 0                              ; to initialize i
MOV BX, OFFSET VET_2

交换代码，例如将变成这 3 条指令:

mov  ax, [bx+si]
xchg ax, [bx+di]
mov  [bx+si], ax