;----------------------------------------------------------------------
; QSORT.ASM --- General Purpose QuickSort
; Copyright (c) 1988 Ziff Communications Co.
; PC Magazine * Ray Duncan * 12-13-88
;----------------------------------------------------------------------
; Call with: DS:SI = address of first item to sort
; DS:DI = address of last item to sort
; ES:BX = address of compare routine
; AX = length of each item
;
; Returns: nothing
;
; Uses: nothing
;
; The external compare routine must be declared as 'proc far'
; and it must accept the following parameters:
; DS:SI = address of 1st item to compare
; ES:DI = address of 2nd item to compare
; CX = length to compare
; It must return DS:SI and ES:DI unchanged and the result
; of the comparison in the CPU flags as follows:
; Z = T if item 1 = item 2
; Z = F, S = T if item 1 < item 2
; Z = F, S = F if item 1 > item 2
;----------------------------------------------------------------------
_TEXT segment word public 'CODE'
assume cs:_TEXT,ds:NOTHING,es:NOTHING
; stack variables
compare equ dword ptr [bp-4]; address of compare routine
itemsiz equ [bp-6] ; bytes per item
left equ [bp-8] ; first item to sort
right equ [bp-10] ; last item to sort
public qsort ; make visible to Linker
qsort proc near
cmp di,si ; if right <= left
jna qsort5 ; just exit
push bp ; set up stack frame
mov bp,sp ; and local variables
push es ; save address of
push bx ; compare routine
push ax ; save bytes per item
push si ; offset first item
push di ; offset last item
push cx ; save remaining registers
push dx
push ds ; make data addressable by
pop es ; ES for exchange routine
sub si,itemsiz ; SI = i = left - 1
; DI = right
mov bx,di ; BX = j = right
qsort1: ; partition array on value of rightmost item
qsort2: ; scan right for item >= partitioning value
add si,itemsiz ; i++
mov cx,itemsiz
call compare ; while(items[i] < items[right])
jl qsort2
xchg bx,si ; SI = j, BX = i, DI = right
qsort3: ; scan left for item <= partitioning value
sub si,itemsiz ; j--
cmp si,left ; while(items[j] > items[right]
jna qsort4 ; && (j > left)
mov cx,itemsiz
call compare
jg qsort3
qsort4: xchg bx,di ; SI = j, DI = i, BX = right
mov cx,itemsiz
call exch ; exchange the items
xchg si,di ; SI = i, DI = j, BX = right
xchg di,bx ; SI = i, DI = right, BX = j
cmp bx,si ; while(j > i)
ja qsort1 ; (do until pointers cross)
xchg bx,di ; SI = i, DI = j, BX = right
mov cx,itemsiz
call exch ; undo the last exchange
xchg bx,di ; SI = i, DI = right, BX = j
mov cx,itemsiz
call exch ; put partitioning element into position
push si ; save i
mov di,si ; qsort(left, i-1)
sub di,itemsiz
mov si,left
les bx,compare
mov ax,itemsiz
call qsort
pop si ; qsort(i+1, right)
add si,itemsiz
mov di,right
les bx,compare
mov ax,itemsiz
call qsort
pop dx ; restore registers
pop cx
pop di
pop si
pop ax
pop bx
pop es
pop bp
qsort5: ret ; return to caller
qsort endp
;----------------------------------------------------------------------
; EXCH: exchange two items
;
; Call with: DS:SI = address of first item
; DS:DI = address of second item
; CX = item length
;
; Returns: nothing
;
; Uses: AX, CX
;----------------------------------------------------------------------
exch proc near
cmp cx,2 ; are items words?
jne exch1 ; no, jump
mov ax,[di] ; items are words,
xchg ax,[si] ; exchange them quickly
mov [di],ax
ret
exch1: push si ; save addresses
push di
exch2: mov al,[di] ; exchange items
xchg al,[si] ; byte by byte
mov [di],al
inc si
inc di
loop exch2
pop di ; restore addresses
pop si
ret
exch endp
_TEXT ends
end
