Assembly - bubble sort for sorting string

Lukas Karmanovas picture Lukas Karmanovas · Oct 11, 2014 · Viewed 9k times · Source

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

Answer

rkhb picture rkhb · Oct 12, 2014

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