3
\$\begingroup\$

I tried to implement bubble sort in Assembly 8086.

datasg      SEGMENT BYTE 'data'
array       DB 1, 3, 2, 5, 4
n           DW 5
datasg      ENDS
stacksg     SEGMENT BYTE STACK 'stack'
            DW 12 DUP(?)
stacksg     ENDS
codesg      SEGMENT PARA 'code'
            ASSUME CS:codesg, DS:datasg, SS:stacksg
MAIN        PROC FAR

; Pushing the previous data segment to keep it secure.
            PUSH DS
            XOR AX, AX
            PUSH AX
            MOV AX, datasg
            MOV DS, AX
;SI = i
            XOR SI, SI
            MOV CX, n
            DEC CX
out:        PUSH CX; Pushing CX to the stack before entering the second for loop
            XOR DI, DI
            MOV CX, n
            DEC CX
            SUB CX, SI
in:         MOV AH, array[DI]
            CMP AH, array[DI+1]
            JLE if_end
            XCHG AH, array[DI+1]
            MOV array[DI], AH
if_end:     INC DI
            LOOP in
            POP CX
            INC SI
            LOOP out
            XOR SI, SI
; Some garbage code to move array elements to AL register one by one to see them while debugging.
            MOV AL, array[SI]
            INC SI
            MOV AL, array[SI]
            INC SI
            MOV AL, array[SI]
            INC SI
            MOV AL, array[SI]
            INC SI
            MOV AL, array[SI]
            RETF
MAIN        ENDP
codesg      ENDS
            END MAIN

It seems to be working for the given example in the above code. I also tried it with different arrays and they all seem to work. I just want to learn if there is a way to improve it? Improvements like changing JMP codes to decrease the size of code or using AX with XCHG because that is faster.

I also can't comprehend the idea of pushing CX to stack for using nested-for loops. If you would give some suggestion about it I would be very happy.

\$\endgroup\$
  • 1
    \$\begingroup\$ Great, but also drop bubble sort. If you're attempting a low-level, optimised implementation, best to use an algorithm that doesn't have implicit glaring performance issues. \$\endgroup\$ – Reinderien Nov 19 at 22:52
1
\$\begingroup\$
  • On your array that has 5 elements
    the 1st iteration of the outerloop (CX=4) has to do 4 compares in the innerloop
    the 2nd iteration of the outerloop (CX=3) has to do 3 compares in the innerloop
    the 3rd iteration of the outerloop (CX=2) has to do 2 compares in the innerloop
    the 4th iteration of the outerloop (CX=1) has to do 1 compare in the innerloop

    In your code you have initialized the outerloop counter correctly but you should see that the current value of the outerloop counter can serve as the initial value of the innerloop counter. You don't need to re-compute this!

  • When it comes to speed, XCHG with a memory operand is bad. Normally we would load 2 successive elements in 2 different registers, compare those, and if necessary write them back switched.
    However because your array contains byte-sized elements, you can load 2 elements in 1 word-sized register, compare its low and high byte-sized halves, and if necessary xchg the halves and write the word register back. That's how I did it in below code.

  • The LOOP instruction has become infamous for being slow these days. You can easily replace it by the pair of instructions dec cx jnz ....

    mov   cx, n
    dec   cx             ; Max number of compares is (n - 1)
outerloop:
    push  cx             ; (1) Preserve outerloop counter CX

    xor   di, di
innerloop:
    mov   ax, array[di]
    cmp   al, ah
    jle   if_end
    xchg  al, ah
    mov   array[di], ax
if_end:
    inc   di
    dec   cx
    jnz   innerloop

    pop   cx             ; (1) Restore outerloop counter CX
    dec   cx
    jnz   outerloop

I also can't comprehend the idea of pushing CX to stack for using nested-for loops. If you would give some suggestion about it I would be very happy.

Pushing the outerloop counter CX is only necessary if the innerloop wants to use and change the CX register for its own purposes. We can easily re-write the above code and use e.g. BX to control the innerloop. Then we don't need to push cx or pop cx.

    mov   cx, n
    dec   cx             ; Max number of compares is (n - 1)
outerloop:

    mov   bx, cx
    xor   di, di
innerloop:
    mov   ax, array[di]
    cmp   al, ah
    jle   if_end
    xchg  al, ah
    mov   array[di], ax
if_end:
    inc   di
    dec   bx
    jnz   innerloop

    dec   cx
    jnz   outerloop

And while we're optimizing this, we can even write the innerloop without using a special loop counter. We can use the index register DI at the same time for indexing the memory and for counting. This method also speeds things up since the combo cmp di, cx jb innerloop can macro-fuse and give us some extra speed.

    mov   cx, n
    dec   cx             ; Max number of compares is (n - 1)
outerloop:

    xor   di, di
innerloop:
    mov   ax, array[di]
    cmp   al, ah
    jle   if_end
    xchg  al, ah
    mov   array[di], ax
if_end:
    inc   di
    cmp   di, cx
    jb    innerloop

    dec   cx
    jnz   outerloop

stacksg     SEGMENT BYTE STACK 'stack'
            DW 12 DUP(?)
stacksg     ENDS

Might I further suggest you set the stack to a more realistic value like 128 words?

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.