Search code examples
sortingassemblyx86bubble-sorta86

Assembly A86 - Bubble Sort

I am working on an Assembly program to take in a string of characters, sort them with Bubble Sort, and output the sorted string. I do not have access to a debugger, which is why I'm having to ask for help. My program seems to be getting stuck in an infinite loop in the BSORT subroutine and I can't seem to track down what's causing it. This is for an assignment, so I'd rather get explanations of where I'm going wrong/what I'm doing wrong rather than just be handed solutions.

Here is my code:

TITLE   BSORT   
PAGE    60, 132

;   This program gets a string of input
;   and sorts it by ASCII value, then outputs
;   the sorted string to the monitor
;
;   Define constants
;
CR  EQU     0DH     ;define carriage return
LF  EQU     0AH     ;define line feed
EOM EQU     '$'     ;define end of message marker
NULL    EQU     00H     ;define NULL byte
;
;   Define variables
;
JMP START
PROMPT  DB      CR, LF, "Enter a string of characters (max 100): ", EOM
INBUF   DB      100, ?, 100 DUP ?
MESSAGE DB      CR, LF, "The sorted string is: ", CR, LF, CR, LF, EOM
;
;
;   Program Code
;           
;   
BSORT:  
;|——————————
;| CX holds count
;| SI points to first item
;|____________

    MOV BX, CX      ;BX will be inner loop variable
    DEC BX      ;last value will be EOM marker

OUTER:  DEC CX
    JZ  DONE        ;when the count is zero, we’re done

    XOR DL, DL      ;DL (hasSwapped) = false
    MOV SI, DI      ;reset SI

INNER:  MOV AX, [SI]    ;load 2 characters
    CMP AL, AH      ;first char is in AL, second is AH
    JBE NOSWAP      ;if AL <= AH, no swap needed
    MOV DL, 1       ;else, hasSwapped = true
    XCHG    AL, AH      ;swap first and second chars
    MOV [SI], AX    ;put swapped chars back in string

NOSWAP: INC SI      ;next chars
    CMP SI, BX
    JL  INNER
    TEST    DL, DL      ;else, did we swap?
    JNZ OUTER       ;if yes, loop again

DONE:   RET         ;if done, return to main program
;End subroutine

READ MACRO
 MOV     AH, 0AH
 LEA     DX, #1
 INT     21H
 #EM


WRITE MACRO
 MOV     AH, 09H
 LEA     DX, #1
 INT     21H
 #EM
;
;main
START:  WRITE PROMPT
        READ INBUF

        LEA SI, INBUF+2 ;point SI to beginning of array
        MOV CX, SI      ;save SI in the CX register
        ADD CL, B[SI-1] ;add the count that the OS records to the CL register
        ADC CH, 0       ;if carry, add to upper bits
        MOV SI, CX      ;move back to SI and see what it points to
        MOV B[SI], '$'  ;replace carriage return with end of text marker
        MOV CX, SI  ;put count in CX

        LEA SI, INBUF+2 ;point SI to beginning of array
        LEA DI, INBUF+2 ;copy of beginning of array 
        CALL BSORT

        WRITE MESSAGE
        WRITE [INBUF+2]

        MOV AX, 2C00H
        INT 21H ;return control to OS
;
;   Program End
;
        END START

When it's run, it prints the prompt and takes in the string without apparent issue, but then it never prints the message or the sorted string. Previously, I got it to print the message and the string (don't know what I changed that made it stop), but it wasn't sorting it completely.

Any help/guidance is much appreciated.

EDIT 1: Okay, good news is, I found my issue in the loop that was causing infinite loop (I think). But the sorting isn't happening and now I'm getting some really interesting output, too. Here's the output when it's run:

Any ideas?

Any ideas?

EDIT 2: IT'S SORTING! :D

BUT, it's still inserting a lowercase d and the spades character at the beginning of my string. Once I find where that's coming from, I think it'll be solved! Code above is updated.

Here is my output now:

update output

EDIT 3: Found my weird characters - I was printing all of [INBUF], instead of just the string [INBUF+2]. Thank you both for your help! :)

Solution

  • I believe you don't reset SI register. After it finishes the first iteration of the inner loop, SI will never be less or equal to BX. See if that's the problem.

    MOV BX, CX              ;BX will be inner loop variable

OUTER:  DEC CX
JZ  DONE                ;when the count is zero, we’re done

XOR DL, DL              ;DL (hasSwapped) = false
                        ;You should see if resetting SI here will solve the infinite loop.

INNER:  MOV AX, [SI]    ;load 2 characters
                        ;What happens in the second iteration ?
CMP AL, AH              ;first char is in AL, second is AH
JBE NOSWAP              ;if AL <= AH, no swap needed
MOV DL, 1               ;else, hasSwapped = true
XCHG    AL, AH          ;swap first and second chars
MOV [SI], AX            ;put swapped chars back in string

NOSWAP: INC SI          ;next chars
CMP SI, BX              ;In the first iteration of the inner loop that should be ok.
JLE INNER
                        ;At this point SI kept its value
TEST    DL, DL          ;else, did we swap?
JNZ OUTER               ;if yes, loop again