Vfrdtyky

I've created a procedure to selection sort a word vector but there's a problem: the sorting is totally wrong.

My vector: 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

Before call selection sort procedure: 2 7 0 1 4 8 9 3 6 5

After call selection sort procedure: 5 2 7 0 1 4 8 9 3 6

Where is the error? Can somebody help me?

Problem

When you don't need to swap 2 elements, you still need to raise the lower bound in CX. The cmp cx, bx je SLC_LOOP_FORA neglects this. Moreover it leaves you with an unbalanced stack (popping more than was pushed).

Solution:

The problem (included the stack un-balance) is easily corrected by introducing an extra label:

    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

Consider

; AX = j & aux      CX = i

; BX = offset/min   DX = data and others

PUSH 0                              ; to initialize i

MOV SI, [OFFSET VET_2]

If you were willing to re-assign registers, you could enormously simplify this program.

With register assignments like

; AX = j & aux      DI = i

; SI = offset/min   DX = data and others

PUSH 0                              ; to initialize i

MOV BX, OFFSET VET_2

the swap code e.g. would become just these 3 instructions:

mov  ax, [bx+si]

xchg ax, [bx+di]

mov  [bx+si], ax

MOV SI, [OFFSET VET_2]

I've never seen an assembler that would do it this way! The above sets the SI register equal to the contents of the first array element, so SI=2. Not really useful.

Acceptable instructions to get the address of your vector are:

mov si, offset VET_2

or

lea si, [VET_2]

or

lea si, VET_2

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

Hope this works. Thanks.