Category : Files from Magazines
Archive   : VOL7N16.ZIP
Filename : QSORTI.ASM

name qsorti
title QSORTI.ASM Integer QuickSort
page 55,132
;
; QSORTI.ASM --- Integer Quicksort
;
; Copyright 1988, Ziff Communications Co.
; PC Magazine * Ray Duncan
;
; Call with: DS:SI = address of first item to sort
; DS:DI = address of last item to sort
; Assumes items are 2-byte integers
;
; Returns: Nothing, all registers unchanged.
;

itemsiz equ 2 ; bytes per integer

_TEXT segment word public 'CODE'

assume cs:_TEXT,ds:NOTHING,es:NOTHING

; stack variables
left equ [bp-8] ; first item to sort
right equ [bp-4] ; last item to sort

public qsorti ; make visible to Linker

qsorti 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
push di ; offset last item
push ds
push si ; offset first item
push dx
push cx
push bx
push ax

sub si,itemsiz ; SI = i = left - 1
; DI = j = right
mov bx,di ; BX = right

qsort1: ; partition array on
; value of rightmost item

qsort2: ; scan right for item
; >= partitioning value

add si,itemsiz ; i++

mov ax,[si] ; while(items[i] < items[right])
cmp ax,[bx] ; (guaranteed to terminate
jl qsort2 ; when i = right)

qsort3: ; scan left for item
; <= partitioning value

sub di,itemsiz ; j--

cmp di,left ; while(items[j] > items[right]
jna qsort4 ; && (j > left)
mov ax,[di]
cmp ax,[bx]
jg qsort3

qsort4: mov ax,[di] ; exchange the items
xchg ax,[si]
mov [di],ax

cmp di,si ; while(j > i)
ja qsort1 ; (do until pointers cross)

mov ax,[di] ; undo the last exchange
xchg ax,[si]
mov [di],ax

mov ax,[bx] ; put the partitioning
xchg ax,[si] ; element into position
mov [bx],ax

push si ; save i

mov di,si ; qsort(left, i-1)
sub di,itemsiz
mov si,left
call qsorti

pop si ; qsort(i+1, right)
add si,itemsiz
mov di,right
call qsorti

pop ax ; restore registers,
pop bx ; discard stack frame
pop cx
pop dx
pop si
pop ds
pop di
pop es
pop bp

qsort5: ret ; return to caller

qsorti endp

_TEXT ends

end