0

I'm trying to do a bubble sort function in assembly 8086 but for some reason it gives the wrong answer and I can't find out why.

I cant use any .code, .data and any of those because we haven't learn it yet and I don't know how to use it.

The swap function I used works as far as I know of. 

org  100h

jmp main

    string      db  'm', 'a', 'g', 's', 'h', 'i', 'm', 'i', 'm', 'v', 'e', 'n', 'e', 'h', 'e', 'n', 'i', 'm' ,0Dh,0Ah,'$'

main:
    lea di,string
    push di
    call bubbleSort         

    mov     ax, 0
    mov     ah, 0 
    int     16h 
ret    

swap proc
    push bp
    mov bp, sp

    mov bx, [bp + 4]
    mov al, [bx]
    mov di, [bp + 6]
    mov cl, [di]
    mov [di], al
    mov [bx], cl 

    mov sp, bp
    pop bp   

    retn 4
swap endp

bubbleSort proc
   push bp
   mov bp, sp

   mov si, [bp + 4]

   mov cx, 18
   outer_loop:
        mov si, [bp + 4]
        lea di, [si + 2]

        mov bx, cx
        mov cx, 18 
        inner_loop:
            cmp si, di
            ja finish:    

            ;swap
            pusha
            push si
            push di
            call swap
            popa         

            finish:
            inc si
            inc di

            loop inner_loop
            mov cx, bx
   loop outer_loop      


   mov sp, bp
   pop bp
   retn 2  
bubbleSort endp

(edited) ok, what do you think about this code i understude some of my mistake, the code works right now but I think I move (touch) the '$' sign

bubbleSort proc
   push bp
   mov bp, sp

   mov si, [bp + 4]

   mov cx, 18
   outer_loop:
        mov si, [bp + 4]

        mov bx, cx
        mov cx, 18 
        inner_loop:
            mov al, [si]
            mov ah, 0h
            mov dl, [si + 1]
            mov dh, 0h
            cmp dl, al
            ja finish:    

            ;swap
            mov [si + 1], al
            mov [si], dl    

            finish:
            inc si

            loop inner_loop
            mov cx, bx
   loop outer_loop      


   mov sp, bp
   pop bp
   retn 2  
bubbleSort endp
Adir
  • 29
  • 2
  • 9
  • "it doesn't work" isn't enough description of what's wrong. See [mcve]. Does it crash? Does it give a wrong answer? Use a debugger to see if register values are what you expect. Also, putting `swap` in a separate function makes your code a lot more complicated. – Peter Cordes Nov 25 '17 at 04:11
  • I can see at least 1 problem: you compare `si` and `di` instead of the data they point to. – Peter Cordes Nov 25 '17 at 04:14
  • Working [8086 bubble sort implementation](https://stackoverflow.com/questions/26318043/assembly-bubble-sort-for-sorting-string/26324630#26324630), for 8-bit elements. – Peter Cordes Nov 25 '17 at 04:18
  • Read [mcve] again. What answer *does* it give? It's a lot easier to figure out what might be wrong if we know that e.g. it leaves the last few elements unsorted for some inputs, or the first few, or IDK what. – Peter Cordes Nov 25 '17 at 10:41

1 Answers1

2

The reasons why it gives wrong answer:

mov cx, 18 - both of them, if you want to sort 18 elements, don't sort 19 of them ([i] vs [i+1], 0 <= i < 18 → [17] vs [18] is bug). Plus after each outer loop it is enough to sort one less element in inner loop, as the last one contains already highest value, but that's just inefficiency, not bug.

lea di, [si + 2] - why? What did you really want to do? How big is single element in memory?

cmp si, di - as di = si+2, this cmp will be always "below". Don't compare addresses, but you need values. (and if you need values for compare, it would make sense to write "swap" directly after that, instead of calling some other function and reading the values from memory *again*).

BTW loop is slow.

Swap function is ok.

Ped7g
  • 16,236
  • 3
  • 26
  • 63
  • Related: [x86-16 bubble sort in 20 bytes of machine code (code golf)](https://codegolf.stackexchange.com/questions/77836/sort-an-integer-list/149038#149038). All these crappy bloated bubble-sort implementations were making me crazy. – Peter Cordes Nov 26 '17 at 00:42
  • @PeterCordes I don't require code golf solution exactly to please my eyes, but this one was exceptionally painful with the stack calling convention and weird split of functionality into sort loop / swap... now I'm trying to forget what I have seen here... – Ped7g Nov 26 '17 at 01:14