Как выбрать сортировку - сборка 8086 - PullRequest
Новая
       38

Как выбрать сортировку - сборка 8086

0 голосов
/ 15 ноября 2018

Я создал процедуру для выбора сортировки вектора слов, но есть проблема: сортировка совершенно неправильная.

Мой вектор : 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

Где ошибка? Кто-нибудь может мне помочь?

Ответы [ 3 ]

0 голосов
/ 17 ноября 2018 
MOV SI, [OFFSET VET_2]

Я никогда не видел ассемблера, который бы так делал!Приведенное выше значение устанавливает регистр SI равным содержимому первого элемента массива, поэтому SI=2.Не очень полезно.

Допустимые инструкции для получения адреса вашего вектора: 

mov si, offset VET_2

или 

lea si, [VET_2]

или 

lea si, VET_2
0 голосов
/ 26 ноября 2018

Проблема

Когда вам не нужно менять 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
0 голосов
/ 16 ноября 2018 
selection_sort_i64:
    ; /*
    ; Input:
    ; RDI = long long * array
    ; RSI = length
    ;
    ; Pseudo-C code: 
    ;
    ; for (int i = 0; i < n - 1; ++i) {
    ;    min = i
    ;    for (int j = i + 1; j < n; ++j) {
    ;       if a[j] < a[min]; min = j
    ;   swap(i, min)
    ;*/

    I64_SIZE equ 8
    LG_I64_SIZE equ 3

    cmp rsi, 1
    jle .end            ; Just end it if length <= 1
    xchg rsi, rdi       ; rsi => left pointer
    mov rcx, rdi        ; rcx => length

    ; RDX will be the boundary for i: RSI + (N-1)*sizeof(int64)
    lea rdx, [rsi + rcx * LL_SIZE - LL_SIZE]

    ; /*
    ; Let's explain what's happening here.
    ; RSI will be &a[i], RDX will be it's right boundary
    ; RDI will be &a[j] (&a[i + 1]) and will loop n-i times
    ; RCX will be n-i and will be the counter for the inner loop
    ; RAX will track our minimum in the remaining of the array
    ; RBX will 
    ; */
.outer_loop:
    cmp rsi, rdx
    jge .end            ; while (i < n - 1) {
    mov rax, [rsi]      ;   min = a[i]
    mov rbx, rsi        ;   min_i = i   
    push rax

    mov rdi, rsi
    add rdi, I64_SIZE   ;   j = i + 1 // rdi => right pointer
    dec rcx             ;   // rcx = n - i, inner loop counter
    push rcx
.inner_loop:
        cmp rax, [rdi]              ; if (min > a[j])
        jle .min_less_or_equal
        mov rbx, rdi                ;   min_i = j
        mov rax, [rdi]              ;   min = a[j]
.min_less_or_equal:
        add rdi, I64_SIZE           ; j += 1
        loop .inner_loop
    pop rcx             ; // restore inner loop counter
    pop rax             ; // restore a[i]

    cmp rsi, rbx        ; // swap if minimum found
    jz .no_min          ;   if (i != min_i) 
    mov rdi, [rbx]      ;       temp = a[min]
    mov [rbx], rax      ;       a[min] = a[i]
    mov [rsi], rdi      ;       a[i] = temp
.no_min:
    add rsi, I64_SIZE   ;   i += 1
    jmp .outer_loop     ;   } // end outer loop
.end:
    ret

Надеюсь, это работает.Благодаря.

...