TITLE hw10_06: Bubble Sort
;* author:     Curtis Caldwell
;* course:     CSC220 Assemblers
;* date:       14 September 2003
;*
;* PURPOSE: Page 203, Programming Exercise 6.
;*
;* To sort an array A of N elements by the bubblesort method, 
;* we proceed as follows:
;*
;* Pass 1.  For j=2...N, if A[j]<A[j-1] then swap A[j] and A[j-1].
;*          This will place the largest element in position N.
;* Pass 2.  For j=2...N-1, if A[j]<A[j-1] then swap A[j] and A[j-1].
;*          This will place the second largest element in position N-1.
;* ...
;* Pass N-1. If A[2]<A[1], then swap A[2] and A[1]. 
;*           At this point, the array is sorted.
;*
;* Demonstration
;* initial data	7	5	3	9	1
;* pass 1	5	3	7	1	9
;* pass 2	3	5	1	7	9
;* pass 3	3	1	5	7	9
;* pass 4	1	3	5	7	9
;*
;* ASSIGNMENT:
;* Write a procedure BUBBLE to sort a byte [or word] array 
;*   by the bubblesort algorithm.
;* The procedure 
;*   (1) receives the offset address of array in SI, and
;*   (2) the number of elements in BX.
;* Write a program that
;*   (3) lets the user type 
;*       (a) a list of single-digit numbers,
;*       (b) with one blank between numbers,
;*   (4) calls BUBBLE to sort them, and
;*   (5) prints 
;*       (a) the sorted list
;*       (b) on the next line.
;*   (6) Your program should be able to handle an array with only one element.
;*
;* EXAMPLE
;* ?2 1 6 5 3 7
;* 1 2 3 5 6 7
;*
;*----------------
;*
;* ALGORITHM: Bubble Sort
;*   For K = N-2 to 1
;*     For J = 1 to K-1
;*       if A(J) < A(J-1) then swap A(J) and A(J-1)
;*       Next J
;*     Next K
;*
;*--------------------------------------
;*
;* ASSUMPTIONS,LIMITATIONS,RESTRICTIONS:
;*   100 word limit
;*
;*   AX: new element to check
;*   BX: array + displacement
;*   CX: counter to use with LOOP instruction
;*   DX: old element to test against
;*
;*----------------
;*
;* ERRORS CHECKED:
;*
;*
;*----------------
;*
;* I/O:
;*   Input: Keyboard
;*   Output: DOS window
;*
;*----------------
;*
;* INPUT PARAMETERS:
;*   Input divident M and divisor N.
;*
;*-------------------
;*
;* OUTPUT PARAMETERS:
;*   Output GCD
;*
;*
;*-----------------
;*
;* PROCEDURES USED:
;*   MAIN
;*   INDEC
;*   OUTDEC
;*
;*------------------
;*
;* PROCESS STRATEGY:
;*
;*******************
.MODEL SMALL
DATA_SEGMENT                 SEGMENT

;*                             <constants>

  CR	EQU 0Dh
  LF	EQU 0Ah

  MSG1	DB  CR,LF,'Input the number of elements in the array: $'
  MSG2  DB  CR,LF,'Input signed integer array numbers separated by blanks.',CR,LF,'$'
  MSG3  DB  CR,LF,'The sorted array is: ',CR,LF,'$'
  MSG4  DB  CR,LF,'$'

;*                               <types>

;*                             <variables>

  N	  DW   ?				;Filled array size
  K	  DW   ?				;Outer loop base index
  
  ARRAY	  DW   ? ;5,7,4,6,2,8,3,1
          DW   100 DUP (?)			;Declare array of 100 words

;*                          <external modules>

DATA_SEGMENT                 ENDS

STACK_SEGMENT                SEGMENT STACK
          DW   100 dup(?)
  TOS     DW   0             			;TOS is 'top of stack'
STACK_SEGMENT                ENDS

CODE_SEGMENT                 SEGMENT

  ASSUME CS:CODE_SEGMENT, DS:DATA_SEGMENT, SS:STACK_SEGMENT

;  At this point in the entry of the program
;  CS:IP points to label START
;  DS, ES, and SS are not pointing to their proper segments.
;      DS and ES point to the program segment prefix.
;  AL contains 00h if first file name on command line is valid, otherwise ffh.
;  AH contains 00h if second file name on command line is valid, else ffh.
;  DTA has been set to point to program segment prefix offset 80h.

MAIN     PROC

 START: MOV  AX,DATA_SEGMENT    ;get data segment
        MOV  DS,AX              ;initialize DS
        MOV  ES,AX              ;initialize ES
        MOV  AX,STACK_SEGMENT   ;get stack segment
        MOV  SS,AX              ;initialize SS
        MOV  SP,OFFSET TOS      ;initialize SP to Bottom of Stack

;prompt to input array of signed integers
	LEA  DX,MSG1
	MOV  AH,9
	INT  21h

;input array size
	LEA  BX,ARRAY
	CALL INDEC		;fetch stored array size
	MOV  N,AX		;save array size
	MOV  CX,AX		;set up loop to read array

;input array elements
	LEA  DX,MSG2
	MOV  AH,9
	INT  21h
  ARRAY_IN:
	CALL INDEC
	MOV  [BX],AX
	INC  BX
	INC  BX
	LOOP ARRAY_IN

;set up to call Bubble Sort
	LEA  SI,ARRAY
	MOV  BX,N
	CALL BUBBLE

;output loop
	LEA  DX,MSG3
	MOV  AH,9
	INT  21h

	MOV  CX,N
	LEA  BX,ARRAY

 OUTLOOP:
	MOV  AX,[BX]
	CALL OUTDEC
	MOV  DL,20H		;ASCII blank into DL
	MOV  AH,2
	INT  21H
	INC  BX
	INC  BX			;WORD variable
	LOOP OUTLOOP

	LEA  DX,MSG4
	MOV  AH,9
	INT  21h

;exit to DOS
	MOV  AH,4CH
	INT  21H

MAIN    ENDP                    ;ENDP ends a procedure


BUBBLE   PROC
;Array base address is passed in register SI.
;Array size N is passed in register BX.
	JMP   BUBBLE_ENTRY  ;jump over locally declared variables
  ARRAYLOC    DW  0
  SORTSIZE    DW  0

BUBBLE_ENTRY:
        PUSH  AX          ;save registers
        PUSH  BX
        PUSH  CX
        PUSH  DX

;initialization for bubble sort

	MOV  ARRAYLOC,SI
	DEC  BX
	MOV  SORTSIZE,BX

 BASE_LOOP:
	CMP  SORTSIZE,1
	JLE  SORT_END
	MOV  CX,SORTSIZE
	MOV  SI,ARRAYLOC
	MOV  DX,[SI]
 SWAP_LOOP:
	INC  SI
	INC  SI			;Array is a WORD variable
	MOV  AX,[SI]
	CMP  AX,DX
	JGE  SWAP_OVER
	XCHG AX,DX
 SWAP_OVER:
	MOV  [SI-2],DX		;REMEMBER: These are WORD variables
	MOV  DX,AX
	LOOP SWAP_LOOP
	MOV  [SI],DX
	DEC  SORTSIZE
	JMP  BASE_LOOP

 SORT_END:			;bubble sort finished

        POP   DX          ;restore registers
        POP   CX
        POP   BX
        POP   AX
	RET

BUBBLE  ENDP



INCLUDE INDEC.ASM
INCLUDE OUTDEC.ASM

CODE_SEGMENT                 ENDS

        END  MAIN               ;END ends the source program