Assembly - bubble sort for sorting string

Question

I am writing a program in assembly using tasm. My task is to write a program that will use bubble sort to sort entered string alphabetically. Ex. if you enter "hello" it should write "ehllo". I have writened the begging to enter string and to sort it (I think it works okey until the end where it should print out the result, but at the end it just writes my .data once and the finisheds its work) P.S sorry for bad english

.model small
.stack 100h

.data
request     db 'This program is using bubblesort to get alphabetical order of your enterd string', 0Dh, 0Ah, 'Enter your string:', 0Dh, 0Ah, '$'
result      db 0Dh, 0Ah, 'Result:', 0Dh, 0Ah, '$'
buffer      db 100, ?, 100 dup (0)

.code

start:
MOV ax, @data                   
MOV ds, ax                      


MOV ah, 09h
MOV dx, offset request
int 21h


MOV dx, offset buffer           
MOV ah, 0Ah                     
INT 21h                         


MOV si, offset buffer           
INC si                          
MOV bh, [si]                    
INC si                          

sort:
mov cx, [si] 
mov bx, [si]     

nextelement:
mov ax, [bx+si]     
cmp ax, [bx+si+1]   
jge noswap          
xchg ax, [bx+si+1]
mov ax, [bx+si]

noswap:
inc si              
cmp cx, si          
jl nextelement      
loop nextelement 



MOV ah, 09h
MOV dx, offset result
int 21h


char:
LODSB                           
MOV ah, 2                       
MOV dl, al                      
INT 21h                        

DEC bh                          
JZ ending                       
JMP char                        


ending:
MOV ax, 4c00h               
INT 21h                         

end start

Note that the bh register shares the upper 8 bits with bx, so if you load the latter, the former gets overwritten too. — 500 - Internal Server Error, Oct 11 '14 at 19:09

rkhb · Accepted Answer · 2017-04-08T12:40:22.020

3

1) For bubble sort you need two nested loops. The outer loop resets the start parameters for the inner loop until there is nothing left to swap.

2) You sort characters. That are 8-bit values (bytes). You can't load them directly into a 16-bit register (mov ax, [bx+si]).

3) [bx+si] & [bx+si+1]: this is so wrong that I cannot explain the error :-) .

Instead of correcting your code I wrote an example "from scratch": following the illustration in http://en.wikipedia.org/wiki/Bubble_sort:

Bubble sort animation

.MODEL small
.STACK 1000h                        ; Don't skimp with stack!

.DATA
    Struct0A EQU $                  ; Buffer for INT 21h/0Ah (max,got,buf)
        max db 100                  ; Maximum characters buffer can hold (incl. CR (0Dh))
        got db 0                    ; Number of characters actually read, (excl. CR (0Dh))
        buf db 100 dup (0)          ; Actual characters read, including the final carriage return (0Dh)
    Linefeed db 13, 10, '$'
    GetString   db 'Enter string: $'

.CODE
start:
    mov ax, @DATA                           ; Initialize DS
    mov ds, ax

    ; Input String
    mov ah, 09h
    mov dx, OFFSET GetString
    int 21h
    mov dx, OFFSET Struct0A
    mov ah, 0Ah
    INT 21h

    mov si, OFFSET buf                      ; Base for [si + bx] 
    xor bx, bx                              ; Prepare BX for following byte load
    mov bl, got                             ; Load length of string = 0Dh at the end
    mov BYTE PTR [si + bx], '$'             ; Delimiter for int 21h / 09h

    outer:
    dec bx                                  ; The last character is already at the right place
    jz done                                 ; No characters left = done
    mov cx, bx                              ; CX: loop variable
    mov si, OFFSET buf
    xor dl, dl                              ; DL (hasSwapped) = false

    inner:
    mov ax, [si]                            ; Load **two** characters
    cmp al, ah                              ; AL: 1. char, AH: 2. char
    jbe S1                                  ; AL <= AH - no change
    mov dl, 1                               ; hasSwapped = true
    xchg al, ah                             ; Swap characters
    mov [si], ax                            ; Store swapped characters
    S1:
    inc si                                  ; Next pair of characters
    loop inner

    test dl, dl                             ; hasSwapped == true?
    jnz outer                               ; yes: once more
    done:

    ; Print result
    mov dx, OFFSET Linefeed
    mov ah, 09h
    int 21h
    mov dx, OFFSET buf
    mov ah, 09h
    int 21h

    mov ax, 4C00h
    int 21h

END start

And here is another "animated" illustration:

https://www.youtube.com/watch?v=lyZQPjUT5B4

edited Apr 08 '17 at 12:40

answered Oct 12 '14 at 11:27

rkhb

14,159
7
32
60

I am really grateful for the help. I understand how bubble sort looks and how to program it in other language it is just I really don't understand Assembler. Also thanks for spending your time to write full program :) – Lukas Karmanovas Oct 12 '14 at 19:37
On some CPUs, it could be a win to avoid cache-line splits / unaligned loads by always swapping and making just the store conditional. e.g. `mov al, [si]` / `rol ax,8` / `cmp/jbe`. You could even use `lodsb` (but on modern CPUs that's slower than `mov` / `inc`). This creates a loop-carried dependency on AX, but OTOH if a lot of swaps are needed it avoids store-forwarding stalls from the store to the partially-overlapping load. But the only reason to bubble sort in the first place is compact code-size, not performance, so I won't complain too much about using a slow `loop` instruction. – Peter Cordes Nov 22 '17 at 07:49
@PeterCordes : If targeting 8086 `rol ax, 8` is not available. – Michael Petch Nov 25 '17 at 10:56
@MichaelPetch: Correct. This is tagged x86-16 with TASM, not emu8086. There are registers to spare, so you could keep `8` in `cl` for 8086, though. (Of course, `rol` by 8 would be much slower than `xchg` on a real 8086.) Also, I think I read that emu8086 supports immediate-count shifts/rotates, unlike real 8086, in case anyone cares about that target. – Peter Cordes Nov 25 '17 at 11:03
I didn't say anything about emu8086. I said the 8086. Didn't see any tag or mention of emu8086 (or x86-16) in this question. I was making the observation that with an 8086 it isn't supported. Using `cl` and loading it with the shift is an option - that would be supported for an 8086. Note: emu8086 is a bastardized variant of 80186 and will silently convert your rotate with 8 rol instructions – Michael Petch Nov 25 '17 at 15:26
@MichaelPetch: o.O, I didn't realize emu8086 treated immediate-shifts as pseudo-instructions instead of just supporting the imm8 machine-code. (I know *you* didn't say emu8086 either, sorry I brought it up. :P But I was thinking that most people that think they want 8086 really just want code that works in emu8086.) – Peter Cordes Nov 25 '17 at 15:28
[code-golf: x86-16 BubbleSort in 20 bytes of machine code](https://codegolf.stackexchange.com/questions/77836/sort-an-integer-list/149038#149038). I feel like there might be room to improve on the inner loop's loop condition. – Peter Cordes Nov 25 '17 at 15:29
@PeterCordes : TASM by default will support your instruction (just like emu8086) and it emits 8 separate rotate instructions if one looks at the actual instructions that are generated. You can change that behaviour by placing the `.186` directive at the top. NASM of course doesn't have any way of distinguishing between 8086 and 80186. – Michael Petch Nov 25 '17 at 15:33
1

@PeterCordes : If you are curious what happens by default in TASM when you push an immediate value this is the type of code it generates: `push ax` `push bp` `mov bp, sp` `mov word ptr [bp+2], 33h` `pop bp` would be generated if the instruction `push 33h` was used. Most people don't realize this if they never debug their code or generate a listing file. Without a directive in the file or override on the command line TASM will do these types of conversions silently because it defaults to 8086 code gen. – Michael Petch Nov 25 '17 at 17:54
@MichaelPetch: wow. I knew about 8086 missing immediate rotate, but I didn't realize it was missing immediate push. I think I'd rather have the assembler just error out instead of emit that, unless I used a special TASM macro that assembled to `push` on later models, or that on 8086. If I had interrupts disabled and was assuming that memory below `sp` was thus safe from async clobber, this pseudo-instruction would break my code! – Peter Cordes Nov 25 '17 at 23:09
1

@PeterCordes : Not sure there is a way to turn that off in TASM. It was always something I kept in mind when developing using TASM and targeting real mode code without specifying `.186` or higher. MASM on the other hand will error out if you try to use an unsupported instruction when targeting 8086 rather than silently generate equivalent code. – Michael Petch Nov 26 '17 at 10:44

Assembly - bubble sort for sorting string

1 Answers1

Linked