bubble sort in emu8086

Question

The flowchart below is used to sort in ascending order an array of length N = 100h starting at address [200h], following the principle:

Principle:

Sort each pair of successive values in the array (if they are not sorted in ascending order, swap them).

For each value of the secondary counter DX, the values to be sorted are pointed to by [SI] and [SI + 1]. Since the array has N values and the first pass is done comparing between the second-to-last and the last value, the primary counter CX will have to traverse (N - 1) values, i.e., CX = N - 1, N - 2, ..., 2, 1. This solution allows stopping the process when it is observed that the array is already sorted after one pass of the secondary counter DX through all its relevant values, even before reaching the limit of the primary counter (CX = 1).

For each pass (i) (meaning for each value of the primary counter CX = N - i), SI varies from its initial value (200h) to the value (200h + N - i - 1), giving (N - i) values. Therefore, the counter DX will take the following (N - i) values:

This translates to:

DX = N - i, N - i - 1, N - i - 2, ..., 2, 1
DX = CX, CX - 1, CX - 2, ..., 2, 1

The flowchart:

start 
cx=n-1
 
 etq:
 dx=cx
 si=200h
 bl=0
 
 al=[si]
 
 bcl:
 al<=[si+1]
   if yes:
     si=si+1
     dx=dx-1
   if no:
     permute al,[si+1]
     si=al
     bl=bl+1
     si=si+1
     dx=dx-1
    
  zf=1 ?
      if yes:
        bl=0?
          if yes:
            end
          if no:
            cx=cx-1
            z=1?
            if yes:
               end
            if no:
               etq      
      if no:
        bcl 

i tried translating it to the code below:

; multi-segment executable file template.

data segment
    tab db 30h,35h,23h,37h,38h,39h,31h
    n dw 7
ends

stack segment
    dw   128  dup(0)
ends

code segment
start:
; set segment registers:
    mov ax, data
    mov ds, ax
    mov es, ax
    
    sub n,1
    mov cx,n 
    etq:
    mov dx,cx
    mov si,200h
    mov bl,0  
    
    mov al,[si]
    bcl:
    cmp al,[si+1]
    jbe con
    
    mov dl,al
    mov al,[si+1]
    mov [si+1],dl  
    
    mov si,ax
    inc bl
    
    con:
    inc si
    dec dx
        
    jnz bcl
    
    cmp bl,0
    je fin
    dec cx
    
    jnz bcl 
   
    fin:
    mov ax, 4c00h ; exit to operating system.
    int 21h    
ends

end start ; set entry point and stop the assembler.
           

but it doesn't change anything.

Answer 1

Sort each pair of successive values in the array (if they are not sorted in ascending order, swap them).

Because you erroneously keep mov al,[si] outside of the bcl loop, you are not processing pairs of successive values. You end up comparing between non-adjacent elements.

Sort each pair of successive values in the array (if they are not sorted in ascending order, swap them).

Because you erroneously use mov si,ax based on an error in the pseudo code, the pointer SI gets destroyed and there's no telling what the results will be. The correct instruction is mov [si], al.

dec cx
jnz bcl

Here the pseudo code had it right, but you erroneously wrote bcl instead of etq. I find these names bcl (boucle) and etq (étiquette) a bit too generic. Might I suggest InnerLoop and OuterLoop ?

mov dl,al

You shouldn't use the DL register within the inner loop since you are already using DX as the inner loop counter. Remember that DL is the low byte of DX, just like DH is the high byte of DX.

One solution

    dec  n
    mov  cx, n 
OuterLoop:
    mov  dx, cx
    mov  si, 0200h
    mov  bl, 0  
InnerLoop:
    mov  ax, [si]     ; Read two adjacent byte-sized elements
    cmp  al, ah       ; Compare
    jbe  con
    mov  [si+1], al   ; Swap low -> high
    mov  [si], ah     ; Swap high -> low
    mov  bl, 1        ; Testify the swap
con:
    inc  si
    dec  dx
    jnz  InnerLoop
    
    test bl, bl
    jz   fin
    dec  cx
    jnz  OuterLoop
fin:

I have replaced your inc bl by mov bl, 1. Both instructions are the same length, but the inc bl could backfire on you (producing a so-called 'false positive') in case the number of swap operations happens to be a multiple of 256.

[edit]

the elements didn't really change their order.

The task description talks about an array located at address 200h, but the program that you have written has placed the array behind its own label and that happens to be at offset address 0 in the data segment.
Either you satisfy the task description by adding a filler:

    db 200h dup(0)
tab db 30h,35h,23h,37h,38h,39h,31h
n   dw 7

or you don't add a filler and just replace mov si, 0200h by mov si, OFFSET tab.

Answer 2

In the flowchart pseudo code, that si=al is wrong, si is a pointer whereas al is a character — so that is a type mismatch and a logic error.  That translates into a very problematic mov si,ax.

Starting with broken pseudo code makes writing assembly code very difficult.

---

You also made a valid optimization of the first if yes:, eliminating it and moving the then-part to after the if no: (aka else) part.  This is a good optimization, though I would have first made such an optimization in the pseudo code rather than during transcription to assembly code.

I would also prefer my pseudo code to be in C so that I can actually run it and test it, especially after making optimizations like that.

---

Also, the pseudo code uses zf=1? in one place and z=1? in another.  This is another reason that I like to use C for pseudo code, you can compile it and find typo's and such.

C supports structured statements, but still using C you can also translate structured statements into if-goto-label.  Since C supports that form you can actually run & test your if-goto-label version to verify that it is also correct.

So, a simple while loop in C using if-goto-label looks as you might expect:

    i = 0;
    max = 0;
Loop1:
    if ( i > 10  ) goto Loop1End;
    if ( a[i] <= max ) goto EndIf1;
    max = a[i];
EndIf1:
    i++;
    goto Loop1;
 Loop1End:
    ...

This C if-goto-label is a compile-able, executable, and testable intermediate pseudo code form that is closer to assembly code.