assemblyx86-16bubble-sortemu8086

How does this 8086 code of ascending-sort work?


I am currently learning 8086 programming and this one was demonstrated in our lab on a 8086 kit. The following code sorts sequence of numbers to ascending order:

mov si, 2000
mov cl, [si]
dec cl
loop1: mov si, 2000
       mov ch, [si]
       dec ch
       inc si
       loop2: mov al, [si]
              inc si
              cmp al, [si]
              
              jc loop3

              xchg al, [si]
              dec si
              xchg di, [si]
              inc si

       loop3: dec ch
              jnz loop2
       dec cl
       jnz loop1
int a5

How exactly does this function?

Say we have an array of N numbers d1, d2, ..., dN as follows:

Address |2000|2001|2002|2003|...|2000+N|...|
Data    |N   |d1  |d2  |d3  |...|dN    |...|
        |si  |

cl <-- [si]
{cl:N --> N-1}

LOOP 1:

ch <-- [si]
{ch:N --> N-1}
si --> si+1
Address |2000|2001|2002|2003|...|2000+N|...|
Data    |N   |d1  |d2  |d3  |...|dN    |...|
             |si  |

LOOP 2:

al <-- [si] = d1
si --> si+1
Address |2000|2001|2002|2003|...|2000+N|...|
Data    |N   |d1  |d2  |d3  |...|dN    |...|
                  |si  |
Compare [si] = d2 with al = d1.
If d1 > d2, jump to LOOP 3,
else d1 <= d2 and exchange d1 in al with d2 at si = 2002.
al = d2
Address |2000|2001|2002|2003|...|2000+N|...|
Data    |N   |d1  |d1  |d3  |...|dN    |...|
                  |si  |
si --> si - 1
[di] = d1 (at 2001) 

LOOP 3:

{ch:N-1 --> N-2}
If ch is not zero then jump to LOOP 2.
al <-- [si] = d2 and so on.

At this point I feel like I am losing track of how the code really works. So, how does this work? Am I missing something? The example demonstrated was:

Address |2000|2001|2002|2003|2004|2005|...|
Input   |5   |04  |03  |01  |00  |02  |...|
Output  |5   |00  |01  |02  |03  |04  |...|

Solution

  • The troubles in this ascending bubble sort

    At this point I feel like I am losing track of how the code really works. So, how does this work? Am I missing something?

    You are mis-interpreting the conditional jump in:

    cmp al, [si]      <<<< AL = d1, [si], d2
    jc loop3
    

    when you state:

    If d1 > d2, jump to LOOP 3,
    else d1 <= d2 and exchange d1 in al with d2 at si = 2002.
    

    The jc instruction should have been written as jb that has exactly the same encoding but that better conveys what it does: "If AL is below the byte at [si] then jump to LOOP3". So if d1 < d2 which is just the opposite of what you stated ("if d1 > d2").
    Incidently, LOOP3 is a really bad name for this label! A more suitable name could be SKIP.

    I would be so grateful if you could post a better-version of this code that is easy to understand.

           mov  si, 2000  ; Where the count resides
           mov  cl, [si]  ; CL is number of elements
           dec  cl        ; CL is number of iterations outer loop
    Outer: mov  si, 2001  ; Where the first element resides
           mov  ch, cl    ; Ever smaller number of iterations inner loop (*)
    Inner: mov  al, [si]
           inc  si
           cmp  al, [si]  ; Compare two adjacent elements
           jb   Skip      ; Skip the Swap if ordered fine already
    Swap:  xchg al, [si]
           mov  [si-1], al
    Skip:  dec  ch
           jnz  Inner     ; Iterate on the Inner loop
           dec  cl
           jnz  Outer     ; Iterate on the Outer loop
    

    (*) This is the magic that makes bubble sort somewhat acceptable as a sorting method for small arrays!

    More about writing a bubble sort code can be found at Sort 10 integer numbers read from keyboard and display in ascending order.